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: 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:
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.