w12, pk niestac 2st IIsem, MZT, wykłady
[ Pobierz całość w formacie PDF ]
Sposoby tworzenia uwarunkowania wst ę pnego dla metody gradientów sprz ęż onych Û Ten fakt, ż e matematyka obliczeniowa nie daje ż adnych przepisów dla tworzenia operatora uwarunkowania wst ę pnego B , doprowadzi do tego, ż e na dzie ń dzisiejszy istnieje wielu ró ż nych sposobów twor ż enia tego na dzie ń dzisiejszy istnieje wielu ró ż nych sposobów twor ż enia tego operatora. Rozwa ż ymy kilka z nich. Incomplete Cholesky factorization (Niepełna faktoryzacja Choleckiego) Û Główna idea tego podej ś cia polega na tym, ż e je ś li A = B, zbie ż no ść do dokładnego rozwi ą zania odbywa si ę za jedn ą iteracje. Wi ę c je ś li B -1 przyj ąć jako cz ęść sfaktoryzowanej macierzy A, to B -1 jest przybli ż eniem najlepszego z punktu widzenia ilo ś ci iteracji preconditioningu A -1 . Obliczenia wysokiej wydajności w12 1 Usuni ę cie cz ęś ci elementów przy faktoryzacji macierzy A powoduje to, ż e niepełny faktor Choleckiego H zajmuje znacznie mniej miejsca w pami ę ci komputera w stosunku do pełnego faktora L i wymaga mniejszego czasu faktoryzacji. Istnieje dwie generalne idei zmniejszenia ilo ś ci elementów w niepełnym faktorze Choleckiego H. Tu B = H H T ; A = L L T . O Usuni ę cie wszystkich elementów, który powstaj ą na pozycjach zerowych elementów macierzy ź ródłowej A w trakcie faktoryzacji (ilo ść elementów w macierzy H jest tak ą sam ą jak i w macierzy A L ,gdzie A L – dolny trójk ą t macierzy A). To tak zwany „incomplete Cholesky factorization by position”. Takie podej ś cie jest proste w realizacji, ale jako ść uwarunkowania zwykłe nie jest wysok ą – dla wielu zada ń praktycznych przyspieszenie zbie ż no ś ci jest za słabe. Przy usuni ę ci cz ęś ci elementów przy niepełnej faktoryzacji cz ę sto si ę okazuje, ż e macierz przestaje by ć dodatnio okre ś lon ą . Je ś li to si ę zdarza, faktoryzacje pozostaje przerwan ą , w macierzy ź ródłowej A pozadiagonalne elementy s ą zmniejszone i faktoryzacja zaczyna si ę od pocz ą tku. O Bardziej skutecznym podej ś ciem jest incomplete Cholesky factorization by value. Uwa ż amy, ż e małymi za warto ś ci ą elementami macierzy L (pełnego faktora Choleckiego) mo ż na pomin ąć w stosunku do innych elementów: Obliczenia wysokiej wydajności w12 2 A 2 <Y A A , j = 1 ,..., N ; i = j , j + 1 ,..., N , gdzie ij ii jj - parametr rezygnacji (rejection parameter) 0 < Y < 1 Obliczenie kolumny j przy niepełnej faktoryzacji macierzy. Rezygnacja elementu A ij Po ka ż dej rezygnacji macierz H j mo ż e straci ć dodatni ą okre ś lono ść , dla tego pozostaje wprowadzona macierz poprawienia bł ę du E j : Obliczenia wysokiej wydajności w12 3 A A jj D = ii × A , D = × A j j j H = L + E ii ij jj ij A A jj ii Û Macierz L j > 0 (dodatnio okre ś lona), E j ≥ 0 (półokre ś lona), z tego wynika, ż e suma dodatnio okre ś lonej macierzy i półokre ś lonej doprowadzi do macierzy dodatnio okre ś lonej – H j jest macierz dodatnio okre ś lon ą . Û Im mniej warto ść ψ , tym lepiej wła ś ciwo ś ci uwarunkowania wst ę pnego. H ® L Y ® 0 Y ® 0 − 1 C ( B A ) ® 1 Û Z innej strony, dla małych warto ś ci ψ : O Czas niepełnej faktoryzacji d ąż y do czasu pełnej faktoryzacji Rozmiar macierzy H d ąż y do rozmiaru macierzy L – problem z RAM O Czas ka ż dej iteracji drastycznie ro ś nie O Obliczenia wysokiej wydajności w12 4 Û Wyj ś ciem z danej sytuacji jest zastosowanie technik macierzy rzadkich do niepełnej faktoryzacji Choleckiego – sparse incomplete Cholesky factorization by value. Û Specjalnie napisany solwer bezpo ś redni dla niepełnej faktoryzacji macierzy rzadkich nadaje mo ż liwo ść istotnie zmniejszy ć granice rezygnacji ψ w porównaniu z solwerem zwykłym (incomplete skyline). To istotnie przyspiesza zbie ż no ść . Obliczenia wysokiej wydajności w12 5 [ Pobierz całość w formacie PDF ] |