 | Pobierz cały dokument mn.08.uklady.row.lin.3.metody.numeryczne.doc Rozmiar 811 KB |
MN08
Wielkie układy równań liniowych
Wraz z coraz większymi modelami pojawiającymi się w praktyce obliczeniowej, coraz częściej zachodzi potrzeba rozwiązywania zadań algebry liniowej, w której macierze są co prawda wielkiego wymiaru, ale najczęściej rozrzedzone, to znaczy jest w nich bardzo dużo zer. Bardzo często zdarza się, że macierz wymiaru
ma tylko
niezerowych elementów. Wykorzystanie tej specyficznej własności macierzy nie tylko prowadzi do algorytmów istotnie szybszych od ich analogów dla macierzy gęstych (to znaczy takich, które (w założeniu) mają
elementów), ale wręcz są jedynym sposobem na to, by niektóre zadania w ogóle stały się rozwiązywalne przy obecnym stanie techniki obliczeniowej.
Jednym ze szczególnie ważnych źródeł układów równań z macierzami rozrzedzonymi są np. równania różniczkowe cząstkowe. 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.
Przykład: Macierz z kolekcji Boeinga
Struktura niezerowych elementów macierzy bcsstk38.
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.
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).
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
Format AIJ. W tym formacie wprowadzane są macierze rzadkie do Octave'a i MATLABa:
A = sparse(I,J,V,N,N);
Jednak wewnętrznie przechowywane są w innym formacie.
Przykład. Pokażemy jak w Octave wprowadzić macierz rozrzedzoną.
<realnowiki><realnowiki><realnowiki><realnowiki>octave:10> I = [1, 1, 1, 2, 3, 1, 4];
octave:11> J = [1, 3, 2, 2, 3, 4, 4];
 | Pobierz cały dokument mn.08.uklady.row.lin.3.metody.numeryczne.doc rozmiar 811 KB |
