Macierz hierarchiczna

W matematyce numerycznej macierze hierarchiczne ( macierze H ) są używane jako rzadkie przybliżenia macierzy nierzadkich. Chociaż ${$ macierz wymiaru można skutecznie reprezentować w jednostkach pamięci, przechowując tylko jej niezerowe wpisy, nierzadka macierz wymagałaby $\ displaystyle O (n$${\ Displaystyle O (n ^ {2})}$ jednostek pamięci, a używanie tego typu macierzy do rozwiązywania dużych problemów byłoby zatem zbyt kosztowne pod względem pamięci i czasu obliczeniowego. Macierze hierarchiczne zapewniają przybliżenie wymagające tylko jednostek pamięci, gdzie $(nk \, \ log (n))$$}$ jest parametrem kontrolującym dokładność przybliżenia. W typowych zastosowaniach, np. Podczas dyskretyzacji równań całkowych, warunkowania wynikowych układów równań liniowych lub rozwiązywania eliptycznych równań różniczkowych cząstkowych, stopień proporcjonalny do ${\ Displaystyle \ log (1/\ epsilon) ^ {\ gamma}}$ z małą stałą $}$ wystarczająca do zapewnienia dokładności ${\ displaystyle \ epsilon$ . W porównaniu z wieloma innymi reprezentacjami macierzy nierzadkich z rzadkimi danymi, macierze hierarchiczne mają dużą zaletę: wyniki operacji arytmetycznych na macierzach, takich jak mnożenie macierzy, faktoryzacja lub odwracanie, można przybliżyć w ${\ Displaystyle O (nk ^ {\ alfa} \, \ log (n) ^ {\ beta})}$ , gdzie ${\ Displaystyle \ alfa, \ beta \ w \ {1,2,3 \}.}$

Podstawowy pomysł

Macierze hierarchiczne opierają się na lokalnych przybliżeniach niskiego rzędu: niech $razy J}}$ indeksów i niech $jot {$$Displaystyle G \ in {\ mathbb {R}} ^ {I$ oznaczają macierz, którą mamy przybliżyć. $zastosowaniach$ ) możemy znaleźć podzbiory że ${\ Displaystyle G | _ {t \ razy s}}$ można przybliżyć za pomocą macierzy rang - ${\ displaystyle k}$ . Przybliżenie to można przedstawić w postaci rozłożonej na czynniki ${\ Displaystyle G | _ {t \ razy s} \ około AB ^ {*}}$ z czynnikami ${\ Displaystyle A \ w {\ mathbb {R}}^{t\razy k},B\in {\mathbb {R}}^{s\razy k}}$ . Podczas gdy standardowa reprezentacja macierzy ${\ Displaystyle G | _ {t \ razy s}}$ wymaga ${\ Displaystyle O ((\ # t) (\ # s)}}$ jednostek pamięci, faktoryzacja $_$ _ jeśli ${\ displaystyle k}$ nie jest zbyt duży, wymagania dotyczące przechowywania są znacznie zmniejszone.

Aby przybliżyć całą macierz $,$ się ją na rodzinę podmacierzy. Duże podmacierze są przechowywane w reprezentacji faktoryzowanej, podczas gdy małe podmacierze są przechowywane w reprezentacji standardowej w celu poprawy wydajności.

Macierze niskiego rzędu są blisko spokrewnione ze zdegenerowanymi rozwinięciami używanymi w grupowaniu paneli i szybką metodą wielobiegunową do aproksymacji operatorów całkowych. W tym sensie macierze hierarchiczne można uznać za algebraiczne odpowiedniki tych technik.

Zastosowanie do operatorów całkowych

Macierze hierarchiczne są z powodzeniem wykorzystywane do rozwiązywania równań całkowych, np. jedno- i dwuwarstwowych operatorów potencjału występujących w metodzie elementów brzegowych . Typowy operator ma postać

${\ Displaystyle {\ mathcal {G}} [u] (x) = \ int _ {\ Omega} \ kappa (x, y) u (y) \, dy.}$

Metoda Galerkina prowadzi do wpisów macierzowych postaci

$Displaystyle g_ {ij} = \ int _ {\ Omega} \ int _ {\ Omega }\kappa (x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx,}$

gdzie ${\ Displaystyle (\ varphi _ {i}) _ {i \ w ja}}$ i ${\ Displaystyle (\ psi _ {j}) _ {j \ w J}}$ to rodziny funkcji bazowych elementów skończonych. Jeśli funkcja jądra jest wystarczająco gładka, możemy ją przybliżyć za pomocą interpolacji wielomianowej , aby uzyskać ${\ displaystyle \ kappa}$

${\ Displaystyle {\ tylda {\ kappa}} (x, y) = \ suma _ {\ nu = 1}^{k}\kappa (x,\xi _{\nu })\ell _{\nu }(y),}$

gdzie ${\ Displaystyle (\ xi _ {\ nu}) _ {\ nu = 1} ^ {k}}$ to rodzina punktów interpolacji i ${\ displaystyle (\ell _{\nu })_{\nu =1}^{k}}$ to odpowiednia rodzina wielomianów Lagrange'a . Zastąpienie ${\ displaystyle \ kappa}$ przez ${\ displaystyle \ kappa}}$ przybliżenie

${\ Displaystyle {\ tylda {g}} _ {ij} = \ int _ {\ omega} \ int _ {\Omega}{\tylda {\kappa}}(x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx=\sum _{\nu =1 }^{k}\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx\int _{\Omega}\ell _{\nu }(y)\psi _{j}(y)\,dy=\sum _{\nu =1}^{k}a_{i\nu }b_{j\nu }}$

ze współczynnikami

${\ Displaystyle a_ {i \ nu} = \ int _ {\ Omega} \ kappa (x, \ xi _ {\ nu} )\varphi _{i}(x)\,dx,}$

${\ Displaystyle b_ {j \ nu} = \ int _ {\ Omega} \ ell _ {\ nu} (y) \ psi _ {j} (y) \ dy.}$

Jeśli wybierzemy ${\ Displaystyle t \ subseteq I, s \ subseteq J}$ i użyjemy tych samych punktów interpolacji dla wszystkich ${\ Displaystyle i \ w t, j \ w s }$ , otrzymujemy ${\ Displaystyle G | _ {t \ razy s} \ około AB ^ {*}}$ .

Oczywiście każde inne przybliżenie oddzielające zmienne, np. $rozwinięcie$$wielobiegunowe ,$ podzielić podwójną całkę na dwie pojedyncze całki, a tym samym dojść do podobnego rozłożonego na czynniki niskiego - macierz rang.

Szczególnie interesujące są techniki aproksymacji krzyżowej, które wykorzystują tylko wpisy oryginalnej macierzy $skonstruowania$ aproksymacji niskiego rzędu .

Zastosowanie do eliptycznych równań różniczkowych cząstkowych

Ponieważ operator rozwiązania eliptycznego równania różniczkowego cząstkowego można wyrazić jako operator całkowy obejmujący funkcję Greena , nie jest zaskakujące, że odwrotność macierzy sztywności wynikającej z metody elementów skończonych i metody widmowej można przybliżyć macierzą hierarchiczną.

Funkcja Greena zależy od kształtu domeny obliczeniowej, dlatego zwykle nie jest znana. Niemniej jednak przybliżone operacje arytmetyczne można zastosować do obliczenia przybliżonej odwrotności bez wyraźnej znajomości funkcji.

Co zaskakujące, można udowodnić, że odwrotność można przybliżyć, nawet jeśli operator różniczkowy obejmuje niegładkie współczynniki, a zatem funkcja Greena nie jest gładka.

Działania arytmetyczne

Najważniejszą innowacją metody hierarchicznej macierzy jest opracowanie wydajnych algorytmów wykonywania (przybliżonych) operacji arytmetycznych na macierzach na macierzach nierzadkich, np. obliczania przybliżonych odwrotności, dekompozycji LU i rozwiązań równań macierzowych .

$,$$Y$ , Z i współczynnik skalarny ${\ displaystyle \ alpha}$ . Algorytm wymaga, aby podmacierze macierzy hierarchicznych były zorganizowane w strukturę drzewa blokowego i wykorzystuje właściwości faktoryzowanych macierzy niskiego rzędu do obliczenia zaktualizowanego ${\ Displaystyle Z}$ w operacjach ${\ Displaystyle O (nk ^ {2} \, \ log (n) ^ {2})} .$

Korzystając ze struktury blokowej, odwrotność można obliczyć za pomocą rekurencji do obliczenia odwrotności i uzupełnień Schura bloków ukośnych i połączenia obu za pomocą mnożenia macierz-macierz. W podobny sposób dekompozycję jednostek logicznych można skonstruować wyłącznie za pomocą rekurencji i mnożenia. $_$ operacje _

H ² - macierze

Aby rozwiązać bardzo duże problemy, można ulepszyć strukturę macierzy hierarchicznych: macierze H ² zastępują ogólną strukturę bloków niskiego rzędu hierarchiczną reprezentacją ściśle powiązaną z metodą szybkich multipolów w celu zmniejszenia złożoności przechowywania do ${\ Displaystyle O (nk)}$ .

W kontekście operatorów całkowych brzegowych zastąpienie ustalonego rzędu rangami ${\ displaystyle O (n).}$$,$ które zachowują szybkość zbieżności podstawowej metody elementu brzegowego przy złożoności

Operacje arytmetyczne, takie jak mnożenie, odwracanie i faktoryzacja Cholesky'ego lub LR macierzy H ^{2 -} mogą być realizowane w oparciu o dwie podstawowe operacje: mnożenie macierz-wektor z podmacierzami i aktualizacja podmacierzy niskiego rzędu. Podczas gdy mnożenie macierz-wektor jest proste, wdrożenie wydajnych aktualizacji niskiego rzędu z adaptacyjnie zoptymalizowanymi bazami klastrów stanowi poważne wyzwanie.

Oprogramowanie

HLib to biblioteka oprogramowania C implementująca najważniejsze algorytmy dla $-macierzy$ .

AHMED to biblioteka oprogramowania C++, którą można pobrać w celach edukacyjnych.

HLIBpro to implementacja podstawowych algorytmów macierzy hierarchicznej do zastosowań komercyjnych.

H2Lib to otwarta implementacja hierarchicznych algorytmów macierzowych przeznaczona do badań i nauczania.

awesome-hierarchical-matrices to repozytorium zawierające listę innych implementacji H-Matrices.

HierarchicalMatrices.jl to pakiet Julii implementujący macierze hierarchiczne.