W jaki sposób motywowana jest przyspieszana przez Kryłowa Multigrid (wykorzystująca MG jako warunek wstępny)?

Multigrid (MG) można zastosować do rozwiązania układu liniowego poprzez skonstruowanie początkowej domysły i powtarzanie następujących czynności dla aż do zbieżności: $Ax=b$ $x_0$ $i=0,1..$

Oblicz resztkową wartość $r_i = b-Ax_i$
Zastosuj cykl z wieloma siatkami, aby uzyskać przybliżenie , gdzie . $\Delta x_i \approx e_i$ $Ae_i = r_i$
Zaktualizuj $x_{i+1} \gets x_i + \Delta x_i$

Cykl multigrid pewna sekwencja wygładzania interpolacji restrykcyjnymi i dokładny grubej siatki rozwiązania operacje stosowane do do wytwarzania . Zazwyczaj jest to cykl V lub cykl W. Jest to operacja liniowa więc piszemy . $r_i$ $\Delta x_i$ $\Delta x_i = B r_i$

Można zinterpretować ten proces jako warunkową iterację Richardsona. Oznacza to, że aktualizujemy . $x_{i+1} \gets x_i + B r_i$

Iteracja Richardsona jest prototypową metodą podprzestrzeni Kryłowa, która sugeruje zastosowanie cykli wielosieciowych do wstępnego warunku innych metod podprzestrzeni Kryłowa. Czasami nazywa się to „przyspieszaniem” wielu sieci metodą Kryłowa, lub alternatywnie można to postrzegać jako wybór warunku wstępnego dla metody Kryłowa.

Innym sposobem rozszerzenia powyższego algorytmu jest zastosowanie Full Multigrid (FMG). Zobacz tę odpowiedź, aby uzyskać zwięzły opis.

W jakich sytuacjach MG z przyspieszeniem Kryłowa jest lepszy od MG lub FMG?

linear-algebra linear-solver multigrid krylov-method Patrick Sanan
źródło

(F) MG jest dość wrażliwe, jeśli jeden tryb nie jest odpowiednio tłumiony przez płynniejszą lub dwupoziomową korektę, całość się zawiesza. Metoda Kryłowa może pomóc w tłumieniu tych problematycznych trybów. Tak więc, o ile rozumiem, jest to głównie motywowane solidnością.

Chris

Odpowiedzi:

$b-Ax$

Jednak w wielu praktycznych przypadkach nie stosuje się optymalnej lub skutecznej metody wielosiatkowej. Może to być spowodowane tym, że

taka metoda jest nieznana lub niedostępna dla danego problemu
wygładzacze i operatory międzysieciowe nie są wystarczające do zapewnienia konwergencji podręczników
solver gruboziarnistych jest niedokładny

$BA$

Zauważ, że wybór metody suboptymalnej może skutkować znacznie „tańszym” cyklem wielosieciowym, do tego stopnia, że przyspieszenie Kryłowa się opłaca. Oznacza to, że mogą występować problemy (i systemy komputerowe), w których MG z przyspieszeniem Kryłowa może przewyższyć MG. Byłbym zainteresowany znalezieniem konkretnego przykładu tego.

(Dzięki @chris powyżej i Mattowi Knepleyowi, który wspominał niektóre z powyższych w tutorialu)

Patrick Sanan
źródło