Wytyczne dla zagnieżdżonych warunków wstępnych

9

Rozważ sytuację, w której chcesz rozwiązać układ liniowy przy użyciu wstępnie kondycjonowanej metody Krylova, ale zastosowanie samego wstępnego kondycjonera obejmuje rozwiązanie układu pomocniczego, co odbywa się za pomocą innej wstępnie kondycjonowanej metody Kryłowa.

  • Z jednej strony możesz uruchomić wewnętrzne rozwiązanie, aby uzyskać zbieżność na każdym etapie zewnętrznego rozwiązania.

  • Z drugiej strony, nie można w ogóle wykonać wewnętrznego rozwiązania, ale zamiast tego zastąpić go wewnętrznym warunkiem wstępnym.

  • Gdzieś pośrodku możesz obciąć wewnętrzną pętlę Kryłowa po pewnej ustalonej liczbie iteracji lub po osiągnięciu pewnej tolerancji.

Empirycznie natknąłem się na sytuacje, w których pierwsza skrajność jest lepsza, i różne sytuacje, w których druga skrajność jest lepsza (pod względem całkowitego kosztu). Nie mogę jednak znaleźć wyraźnego powodu, dla którego pewne sytuacje faworyzują jedną strategię nad drugą.

Czy są jakieś wskazówki lub teorie na temat tego, kiedy te różne strategie są preferowane?

Nick Alger
źródło
4
Dla co najmniej trzeciej (pośredniej) sytuacji na liście dobrym miejscem do rozpoczęcia mogą być Simoncini i Szyld, Elastyczne metody wewnętrznej przestrzeni kosmicznej Kryłowa, SIAM J. Numer. Analny. 40 s. 2219–2239.
Andrew T. Barker,
Dzięki za referencje, ciekawi mnie, co tam mają. O dziwo, w praktyce odkryłem, że robienie różnych form sytuacji pośredniej daje zdecydowanie gorsze wyniki. Jeśli numer tolerancji / iteracji jest ustalony, zewnętrzny solver ma tendencję do zawieszania się na poziomie błędu wewnętrznej tolerancji. Zaczynając od dużej wewnętrznej tolerancji i zmniejszając ją wraz z postępem metody zewnętrznej, wydaje się również działać gorzej niż po prostu ustawianie małej wewnętrznej tolerancji na początek.
Nick Alger
Czy stosujesz elastyczne metody Kryłowa? Wyniki, które opisujesz, są tym, czego bym się nie spodziewał. Sytuacja pośrednia jest dokładnie taka, w której warunek wstępny jest (nieco) inny przy każdej iteracji, czyli wtedy, gdy wymagane są elastyczne metody Kryłowa.
Andrew T. Barker,

Odpowiedzi:

1

To pytanie było otwarte od dawna, ale myślę, że nadal zasługuje na odpowiedź.

Podstawowym problemem związanym ze stosowaniem solwerów Kryłowa w poszczególnych blokach jako wewnętrznych warunków wstępnych jest to, że nie są one operatorami liniowymi. Aby to zrozumieć, oznaczmy przezx~=K(A,P,τ,N;b) wektor otrzymany jako rozwiązanie przez uruchomienie metody przestrzeni Kryłowa K w układzie liniowym Ax=b dla co najwyżej N iteracje lub do tolerancji τ zostanie osiągnięty za pomocą warunku wstępnego PA1. Innymi słowy, możesz myślećK jako operator działający na b.

Teraz zauważ to K(A,P,0,;) jest operatorem liniowym: wymagałoby rozwiązania Ax=b dokładnie, tj. K(A,P,0,;b)=A1b, który jest liniowy w b. W wielu przypadkach uruchomienie metody przestrzeni Kryłowa dla dokładnie jednej iteracji, zaczynając od wektora zerowego, jest również operatorem liniowymb. Ale ponieważ sekwencja wektorów Kryłowa zależy od początkowej resztyr(0)=bAx(0), operator K(A,P,τ,N;) zasadniczo nie jest operatorem liniowym dla skończonego N i τ.

Oznacza to, że jeśli używasz K(A,P,τ,N;) jako część warunku wstępnego układu liniowego, w którym A jest jednym blokiem, a następnie otrzymujesz warunek wstępny, który nie działa jako operator liniowy.

Jest to w przeciwieństwie do wielu innych metod, które są stosowane do warunku wstępnego: na przykład jeden krok SSOR jest operacją liniową na wektorze, do którego go zastosujesz, podobnie jak wszystkie inne metody, które stosują jeden krok iteracji o stałym punkcie.

Podstawowym problemem jest teraz to, że większość metod kosmicznych Kryłowa wymaga, aby kondycjoner był operatorem liniowym. Po prostu nie zbiegają się, jeśli warunek wstępny nie jest liniowy, co wyjaśnia twoją obserwację. Z drugiej strony istnieją odmiany niektórych metod kosmicznych Kryłowa - zwykle poprzedzonych słowem „Elastyczny”, takich jak F-GMRES w „Elastyczny GMRES” - które działają w ten sposób i mogą poradzić sobie z warunkami wstępnymi, które nie są liniowe operatorzy. Te elastyczne warianty oryginalnych metod nadal będą zbieżne i często są potężnymi metodami w połączeniu z dobrymi (ale nieliniowymi) warunkami wstępnymi.

Wolfgang Bangerth
źródło