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

edytuj

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

edytuj

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

edytuj

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

edytuj

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

edytuj

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

edytuj

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ż

edytuj