Problemy, w których gradient sprzężony działa znacznie lepiej niż GMRES

17

Interesują mnie przypadki, w których gradient sprzężony działa znacznie lepiej niż metoda GMRES.

Ogólnie rzecz biorąc, CG jest lepszym wyborem w wielu przypadkach SPD (symetrycznie-dodatnio-określony), ponieważ wymaga mniej pamięci, a teoretyczna granica szybkości konwergencji dla CG jest dwukrotnie wyższa niż GMRES. Czy są jakieś problemy z faktycznym obserwowaniem takich stawek? Czy istnieje jakakolwiek charakterystyka przypadków, w których GMRES działa lepiej lub porównywalnie do CG dla tej samej liczby spmv (rzadkie mnożenie macierzy-wektora).

piyush_sao
źródło

Odpowiedzi:

8

Jedną rzeczą, która CG ma na jej korzyść jest to, że nie jest zminimalizowanie dyskretną l2 normę dla swoich szczątkowych wielomianów (co robi GMRES). Zamiast tego minimalizuje normę indukowaną macierzą i bardzo często ta norma indukowana macierzą jest bardzo zbliżona do normy energetycznej dla dyskretyzacji problemów fizycznych, i często jest to znacznie bardziej rozsądna norma do pomiaru błędu z powodu nadchodzących właściwości konserwujących z fizyki.

Tego rodzaju efekt można osiągnąć również za pomocą GMRES, jeśli przeprowadzenie rozkładu Cholesky'ego na macierz masy nie jest zbyt drogie, można zmusić produkty wewnętrzne do uzyskania produktów energii wewnętrznej, które chcesz.

Wtedy przypadki, w których należy oczekiwać, że CG będzie działać bardzo inaczej niż GMRES, to wtedy, gdy stałe implikowane w równoważności norm są bardzo różne. To może być prawdą, na przykład w sposobie wysokiej celu widmowego Galerkina gdzie dyskretne l2 normy stosowane w GMRES traktuje wszystkich stopni swobody za równe, choć w rzeczywistości wielomianowe gradienty najostrzejsze blisko granic (stąd węzeł klasterów), a więc stałe normą równoważności pomiędzy tą normą, a mówiąc ciągłe L2 normą podane przez matrycę masa może być bardzo duża.

Reid.Atcheson
źródło
Chciałem podać tutaj przykład metody wysokiej kolejności i historii konwergencji CG, GMRES i GMRES + Cholesky trick .. ale niestety jedynym kodem, który mam pod ręką w przypadku problemów drugiego rzędu, jest DG niesymetrycznej odmiany .. więc CG nie jest nie dotyczy, chciałbym zobaczyć to w akcji.
Reid.Atcheson
3
Myślę, że twoja odpowiedź dotyczy czegoś ważnego, ale chciałbym, żebyś to wyjaśnił. W szczególności pytanie jest czystą algebrą liniową, a twoja odpowiedź mówi o normach fizycznych i macierzach masy itd. Z liczbowego PDE. Czy możemy powiedzieć coś precyzyjnego o tym, jak minimalizowanie w różnych normach w tej samej przestrzeni Kryłowa prowadzi do różnych iteracji?
Andrew T. Barker
Poza przykładami liczbowymi nie sądzę, aby doszło do dokładnego studium teoretycznego wyjaśniającego, w jaki sposób różne normy dają zasadniczo różne odpowiedzi. Myślę, że problemem jest to, że wyniki obracają się wokół asymptotyków, a dla stałego układu liniowego teoretyczne wyniki będą identycznymi współczynnikami modulo-stałymi. Jeśli istnieją jakieś badania teoretyczne, chciałbym je zobaczyć, ale po zapytaniu niektórych ekspertów numerycznej algebry liniowej w moim dziale nie wydaje się, że istnieje jeszcze dokładna analiza teoretyczna pokazująca, co dzieje się z różnymi normami.
Reid.Atcheson
4

Podejrzewam, że ogólnie nie ma dużej różnicy między GMRES i CG dla matrycy SPD.

Powiedzmy, że mamy do rozwiązywania x = b z A symetrycznego dodatnia określony i przypuszczenie począwszy x 0 = 0 oraz generowanie iteruje z CG i GMRES, nazywamy je x c k i x g k . Obie metody iteracyjne będą budować x k z tej samej przestrzeni Kryłowa K k = { b , b , 2 b , ... } . Zrobią to na nieco inne sposoby.ZAx=bZAx0=0xkdoxksolxkK.k={b,ZAb,ZA2)b,}

CG charakteryzuje się minimalizacją błędu w normie energetycznej indukowanej przez A , tak że ( A e c k , e c k ) = ( A ( x - x c k ) , x - x c k ) = min y K ( A ( x - y ) , x -mikdo=x-xkdoZA

(ZAmikdo,mikdo)=(ZA(x-xkdo),x-xkdo)=minyK.(ZA(x-y),x-y).

GMRES minimalizuje natomiast resztkowe , i robi to w dyskretnej normie 2 , tak że ( r k , r k ) = ( b - A x g k , b - A x g k ) = minimum y K ( b - r , b - Y ) .rk=b-ZAxksol2)

(rk,rk)=(b-ZAxksol,b-ZAxksol)=minyK.(b-ZAy,b-ZAy).
Teraz, korzystając z równania błędu , możemy również zapisać GMRES jako minimalizujące ( r k , r k ) = ( A e g k , A e g k ) = ( A 2 e g k , e g k ) gdzie Chcę podkreślić, że dotyczy to tylko macierzy A SPD . Następnie mamy CG minimalizującą błąd w odniesieniu do A.ZAmik=rk
(rk,rk)=(ZAmiksol,ZAmiksol)=(ZA2)miksol,miksol)
ZAZAnormą i GMRES minimalizuje błędów w odniesieniu do 2 normy. Jeśli chcemy, aby zachowywały się zupełnie inaczej, intuicyjnie potrzebowalibyśmy A, tak że te dwie normy są bardzo różne. Ale dla SPD A normy te będą zachowywać się dość podobnie.ZA2)ZAZA

Się jeszcze dokładniej, w pierwszej wersji z przestrzenią Kryłowa , zarówno CG i GMRES skonstruuje w przybliżeniu formy x 1 = α b . CG wybierze α = ( b , b )K.1={b}x1=αb i GMRES wybierze α=(Ab,b)

α=(b,b)(ZAb,b)
Jeślijest diagonalna z wejściami(ε,1,1,1,...)ib=(1,1,0,0,0,...),a następnie jakoε0pierwszy etap CG będzie dwukrotnie większe niż pierwsze GMRES krok. Prawdopodobnie możesz zbudowaćAib
α=(ZAb,b)(ZA2)b,b).
ZA(ϵ,1,1,1,)b=(1,1,0,0,0,)ϵ0ZAb tak, że ten współczynnik dwóch różnic utrzymuje się przez całą iterację, ale wątpię, żeby stało się jeszcze gorzej.
Andrew T. Barker
źródło
2
b=(1,ϵ,0,0,)|b|=1+ϵbT.ZAb=2)ϵbT.ZA2)b=ϵ1+ϵ2)αCG=ϵ-1+12)ϵ-1αGMRES=2)1+ϵ2)2)ϵ-1
3

Jedną rzeczą jest to, że GMRES nigdy nie jest stosowany wszędzie tam, gdzie można zastosować CG. Nie sądzę, żeby porównywanie tych dwóch miało sens. W przypadku matryc SPD CG jest zdecydowanie zwycięzcą ze względu na wymagania dotyczące pamięci i powody wspomniane powyżej. Ciekawym pytaniem byłoby znalezienie rozszerzenia CG, które ma zastosowanie do problemów, w których nie można zastosować CG. Istnieją metody takie jak BiCG-stab, które nie wymagają liniowego zwiększania pamięci, jak GMRES, ale zbieżność nie jest tak dobra jak GMRES (czasami nawet przy zrestartowanym GMRES).

użytkownik1964178
źródło
2
Istnieją schematy IDR, które wypełniają lukę między GMRES i BiCG pod względem oszczędności pamięci, stabilności i konwergencji: ta.twi.tudelft.nl/nw/users/gijzen/IDR.html Nie jestem pewien, czy zgadzam się, że GMRES nie powinien być stosowany, jeśli może być CG. Jeśli potrafisz dokonać drobnej faktoryzacji macierzy, która indukuje twoją normę energetyczną, możesz wprowadzić ją do symetrycznej iteracji Lanczosa i uzyskać trzyterminowe rozwiązanie rekurencyjne, które będzie zachowywać się prawie jak CG. Oczywiście CG jest łatwiejszą opcją, ale opcja jest dostępna :)
Reid.Atcheson
2
Jeśli na przykład użyjesz wygładzacza Krylowa, GMRES jest prawdopodobnie lepszy, ponieważ wykorzystuje słabszą normę, która jest ukierunkowana na większe wartości własne, które mają tendencję do wyższej częstotliwości.
Jed Brown