Jednym ze szczególnie ważnych źródeł układów równań z macierzami rozrzedzonymi są np. równania różniczkowe cząstkowe (a więc np. modele pogody, naprężeń w konstrukcji samochodu, przenikania kosmetyków do głębszych warstw skóry, itp.).
Modele wielostanowych systemów kolejkowych (np. routera obsługującego wiele komputerów) także prowadzą do gigantycznych układów równań z macierzami rozrzedzonymi o specyficznej strukturze.
Z reguły zadania liniowe wielkiego wymiaru będą miały strukturę macierzy rozrzedzonej, gdyż najczęściej związki pomiędzy niewiadomymi w równaniu nie dotyczą wszystkich, tylko wybranej grupy.
Przykład: Macierz z kolekcji Boeinga
Spójrzmy na macierz sztywności dla modelu silnika lotniczego,
wygenerowaną swego czasu w zakładach Boeinga i pochodzącą z
dyskretyzacji pewnego równania różniczkowego cząstkowego. Pochodzi z kolekcji Tima Davisa. Jest to mała macierz, wymiaru 8032 (w kolekcji spotkasz równania z milionem i więcej niewiadomych).
Jej współczynnik wypełnienia (to znaczy, stosunek liczby niezerowych do wszystkich elementów macierzy) wynosi jedynie , a więc macierz jest bardzo rozrzedzona: w każdym wierszu są średnio tylko 44 niezerowe elementy.
Jej współczynnik wypełnienia (to znaczy, stosunek liczby niezerowych do wszystkich elementów macierzy) wynosi jedynie , a więc macierz jest bardzo rozrzedzona: w każdym wierszu są średnio tylko 44 niezerowe elementy.
[Edytuj]
Reprezentacja macierzy rzadkich
Zacznijmy od sposobu przechowywania macierzy rozrzedzonych. Naturalnie, nie ma sensu przechowywać wszystkich zerowych jej elementów: wystarczy ograniczyć się do zachowania tych niezerowych! W ten sposób zmniejszamy zarówno wymagania pamięciowe, jak i liczbę operacji zmiennoprzecinkowych potrzebnych do prowadzenia działań na macierzy (np. w przypadku mnożenia macierzy przez wektor, nie będziemy mnożyć przez zera!).
[Edytuj]
Format współrzędnych
Do zapamiętania macierzy wymiaru o niezerowych elementów wykorzystujemy trzy wektory:I
,
J
--- oba typu int
--- oraz V
, typu double
,
wszystkie o długości , przy czym
A = sparse(I,J,V,N,N);
Format diagonalny
Znacznie mniej uniwersalny niż poprzednie i dlatego rzadziej spotykany. Kolejne diagonale macierzy przechowujemy w kolejnych wierszach macierzy , gdzie jest liczbą niezerowych diagonal w .Szczególnie wygodny do reprezentacji macierzy taśmowych. Wykorzystywany m.in. przez funkcję LAPACKa
DGBSV
służącą rozwiązywaniu równań z macierzami
taśmowymi.
Macierze specjalne
Zajmiemy się teraz zadaniem rozwiązywania układu równań liniowychNależy pamiętać, że z reguły najlepsze wyniki uzyskuje się, gdy konkretny algorytm dobierze się do konkretnej macierzy. W zastosowaniach pojawiają się m.in. macierze rzadkie o bardzo szczególnej strukturze, dla nich warto stosować wyspecjalizowane algorytmy.
Macierze taśmowe
Macierz taka, że dla , , nazywamy macierzą taśmową z rozstępem , o szerokości pasma .Łatwo sprawdzić, że algorytm eliminacji Gaussa (bez wyboru elementu głównego) nie spowoduje dodatkowego wypełnienia w takiej macierzy (a więc da się wykonać w miejscu). W przypadku konieczności wyboru elementu głównego, pesymistyczne oszacowanie rozstępu macierzy rozkładu LU jest równe --- tak więc, dla niezbyt dużych wciąż wynikowa macierz jest taśmowa.
W szczególności, gdy macierz jest taśmowa z pasmem o rozstępie i jednocześnie diagonalnie dominująca, wtedy rozkład LU takiej macierzy da się wykonać w miejscu kosztem , czyli liniowym względem .
W LAPACKu zaimplementowano szybki solver równań z macierzami taśmowymi,
DGBSV
, ale wymagający specjalnego sposobu
przechowywania macierzy, wykorzystującego format diagonalny.
Macierze trójdiagonalne
Szczególnym przypadkiem macierzy taśmowych są macierze trójdiagonalne, tzn. taśmowe o rozstępie :Zacznijmy jednak od stwierdzenia, kiedy macierz trójdiagonalna nie wymaga wyboru elementu głównego:
Stwierdzenie
Jeśli macierz ma słabo dominującą diagonalę, tzn.
() i przynajmniej dla jednego indeksu "" mamy powyżej
ostrą nierówność "", to algorytm przeganiania jest wykonalny bez
przestawień wierszy. Ponadto wymaga on operacji arytmetycznych,
a więc jest prawie optymalny.