Z Wikipedii

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

• Oszczędny zapis tzw. macierzy rzadkiej, tzn. macierzy z dużą liczbą zer, 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.

[edytuj] 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).

Niektóre informacje zawarte w artykule wymagają weryfikacji. Do weryfikacji: założenie o symetrii jest chyba niepotrzebne, i bez dodatkowego przetwarzania macierzy współczynników spowodowałoby, że niektórych układów nie dałoby się wyliczać, bo ich macierze nie muszą mieć tej własności

Zatem:

[edytuj] 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.

[edytuj] 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

[edytuj] 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.

[edytuj] 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.

[edytuj] 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.