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 N ma tylko O(N) niezerowych
elementów. Wykorzytanie 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ą N^2 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 (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).
Brak komentarzy:
Prześlij komentarz