Metoda macierzy rzadkich

Metoda macierzy rzadkich rozwiązuje trzy następujące problemy informatyczne:

• Oszczędny zapis tzw. macierzy rzadkiej, tzn. macierzy z dużą liczbą wyrazów zerowych, nie wymagający blokowania dużej pamięci na zapisywanie zer. Macierze takie występują często przy rozwiązywaniu praktycznych zagadnień, sprowadzających się do układu równań liniowych.
• Przeciwdziałanie zagęszczaniu macierzy w trakcie procesu rozwiązywania układu tych równań.
• Modyfikacja algorytmu rozwiązywania w celu automatycznego wyeliminowania zbędnych operacji z udziałem zer.

Metody przechowywania macierzy rzadkiej w pamięci

Przyjmuje się następujące założenia:

• Wszystkie wyrazy z głównej przekątnej macierzy Y są różne od zera: $y_{ii}\neq 0$ dla i=1,2...n

gdzie n jest liczbą niezależnych węzłów układu.

• Macierz Y ma strukturę symetryczną, co oznacza, że wyrazy na pozycjach symetrycznych względem głównej przekątnej są albo jednocześnie zerami, albo jednocześnie mają wartości ≠0 (ale niekoniecznie równe).

Zatem:

$y_{ik}=0\Rightarrow y_{ki}=0$

$y_{ik}\neq 0\Rightarrow y_{ki}\neq 0$

Metoda pamiętania wierszami

Metoda ta polega na przeglądaniu macierzy Y wierszami i zapisywaniu kolejno napotykanych niezerowych wyrazów do wektora Y. Dodatkowo tworzy się dwa wektory indeksowe typu integer. Pierwszy z nich A ma tyle pozycji co wektor Y i zawiera numery kolumn, tj. drugich indeksów odpowiednich wyrazów zapisanych w Y. Drugi wektor indeksowy F ma liczbę pozycji = liczbie wierszy macierzy Y i zawiera numery pozycji w wektorze A (lub w Y) rozpoczynające odpowiedni wiersz w macierzy Y. Innymi słowami określa on zakres pozycji w Y (lub w A) dotyczących wyrazów tego samego wiersza macierzy Y, a więc cechujących się tym samym pierwszym indeksem.

Metoda dostosowana do metody LU

Niezerowe wyrazy macierzy X zapisuje się tu w trzech oddzielnych wektorach typu „real”:

• Y0 – zawiera kolejne wyrazy głównej przekątnej macierzy Y;
• YU – zawiera niezerowe wyrazy z górnej, trójkątnej części macierzy Y przeglądanej wierszami;
• YL – zawiera niezerowe wyrazy z dolnej, trójkątnej części macierzy Y przeglądanej kolumnami.

Wykorzystując założoną symetrię strukturalną macierzy Y można użyć tylko dwóch wektorów indeksowych A i F, dotyczących zarówno wektora YU, jak i YL. A – zawiera numery kolumn (drugie indeksy) wyrazów w wektorze YU i jednocześnie numery wierszy (pierwsze indeksy) wyrazów w wektorze YL, F – zawiera numery pozycji w YU (YL) rozpoczynających kolejny wiersz (kolumnę) w Y

Porządkowanie numeracji węzłów

Celem procedury porządkowania numeracji węzłów jest minimalizacja liczby nowych wypełnień w macierzy Y, a więc przeciwdziałanie zagęszczaniu tej macierzy w trakcie realizacji jej rozkładu na iloczyn macierzy trójkątnych Y=LU. Cała ta procedura odbywa się wewnątrz macierzy Y. Początkowo zawiera ona „czystą” macierz admitancyjną, a po zakończeniu procedury rozkładu – obydwie macierze L i U.

Algorytm Berry’ego

Założenie: symetria macierzy struktury S. Podstawowa strategia algorytmu Berry’ego polega na nadawaniu najniższych możliwych numerów tym węzłom układu, dla których odpowiedni wiersz i kolumna w macierzy Y (lub S) generują najmniejszą liczbę nowych wypełnień. Z przedstawionego mechanizmu powstawania nowych wypełnień oraz założenia, że pierwotne wyrazy macierzy Y usytuowane na jej głównej przekątnej mają wartości ≠ 0 wynika, że wiersze i kolumny zawierające tylko 2 wyrazy ≠ 0 nie mogą być źródłem powstania nowych wypełnień. Zatem odpowiadającym im węzłom należy przypisać najniższe numery: 1,2,.... Po wyczerpaniu takich wierszy należy sprawdzić, który z pozostałych wierszy generuje najmniej nowych wypełnień, i odpowiadającemu mu węzłowi układu nadać kolejny najniższy numer.

Wnioski

Efektywność metody macierzy rzadkich w zakresie oszczędności pamięci jest dość oczywista i zależy ona głównie od wielkości układu równań oraz struktury i zagęszczenia macierzy współczynników. Oszczędność w zajętości pamięci dla dużych układów równań jest co najmniej kilkudziesięciokrotna. Równie znaczący jest zysk w dziedzinie czasu rozwiązania układu równań, a właściwie liczby niezbędnych operacji. Klasyczne metody wymagają liczby operacji proporcjonalnej do n³, gdzie n jest liczbą niewiadomych. W metodzie macierzy rzadkich ta liczba jest proporcjonalna do r k, gdzie r jest liczbą niezerowych wyrazów w macierzy współczynników; k natomiast jest praktycznie zawarty w przedziale 1≤ k ≤1.5 i zbliża się tym bardziej do granicy 1, im większy jest układ równań i mniejsze zagęszczenie macierzy współczynników.

Zobacz też

• macierz rzadka
• macierz wstęgowa