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

13

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

  1. Oblicz resztkową wartość ri=bAxi
  2. Zastosuj cykl z wieloma siatkami, aby uzyskać przybliżenie , gdzie A e i = r i .ΔxieiAei=ri
  3. Zaktualizuj xi+1xi+Δxi

Cykl multigrid pewna sekwencja wygładzania interpolacji restrykcyjnymi i dokładny grubej siatki rozwiązania operacje stosowane do do wytwarzania Δ x I . Zazwyczaj jest to cykl V lub cykl W. Jest to operacja liniowa więc piszemy Δ x I = B r I .riΔxiΔxi=Bri

Można zinterpretować ten proces jako warunkową iterację Richardsona. Oznacza to, że aktualizujemy .xi+1xi+Bri

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?

Patrick Sanan
źródło
2
(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:

10

bAx

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