Macierz rzadka

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu macierze.
Macierz ikona.png


Niektóre typy macierzy
macierz diagonalna
macierz dodatnio określona
macierz elementarna
macierz hermitowska
macierz idempotentna
macierz jednostkowa
macierz klatkowa
macierz nieosobliwa
macierz nilpotentna
macierz ortogonalna
macierz osobliwa
macierz rzadka
macierz schodkowa
macierz skalarna
macierz symetryczna
macierz trójkątna
macierz unitarna
macierz wstęgowa
macierz zerowa


Operacje na macierzach
mnożenie przez skalar
dodawanie i odejmowanie
mnożenie macierzy
odwracanie macierzy
transpozycja macierzy
sprzężenie macierzy
operacje elementarne
macierz dopełnień algebraicznych
macierz dołączona
diagonalizacja
postać Jordana


Inne zagadnienia
wyznacznik macierzy
ślad macierzy
widmo macierzy
minor macierzy
rząd macierzy
wielomian charakterystyczny

edytuj ten szablon
Macierz rzadka otrzymana podczas rozwiązywania układu równań różniczkowych metodą elementów skończonych w zagadnieniu dwuwymiarowym. Czarne kropki reprezentują położenie niezerowych elementów macierzy równania.

Macierz rzadkamacierz, w której większość elementów ma wartość zero.

Macierze rzadkie z reguły odpowiadają układom, w których istnieje bardzo dużo stopni swobody, z których każdy wiąże się bezpośrednio z niewielką liczbą innych stopni swobody (tzw. luźny związek, ang. loose coupling). Przykładem takiego układu jest zestaw tysięcy kulek ułożonych w linii i połączonych sprężynami w ten sposób, że pierwsza i ostatnia kulka są unieruchomione, a każda kulka wewnętrzna połączona jest z dwoma sąsiednimi kulkami sprężyną. Układ ten stanowi model drgań struny i opisywany jest macierzą rzadką, w której w każdym wierszu i kolumnie znajdują się co najwyżej trzy elementy niezerowe. Gdyby w tym modelu założyć, że każda kulka połączona jest sprężynami ze wszystkimi innymi kulkami, otrzymalibyśmy model reprezentowany przez macierz gęstą.

Macierze rzadkie są wykorzystywane (i badane) w teorii grafów oraz dyscyplinach pochodnych, np. w teorii sieci. Ogromne macierze rzadkie często pojawiają się w badaniach naukowych i inżynierskich podczas rozwiązywania równań różniczkowych cząstkowych. Dlatego macierze rzadkie stanowią jeden z głównych obszarów zainteresowań metod numerycznych.

Do przechowywania i operacji na macierzach rzadkich w komputerach stosuje się specjalne algorytmy i struktury danych, które optymalnie wykorzystują strukturę macierzy rzadkich. Dlatego algorytmy opracowane dla macierzy rzadkich są zwykle wielokrotnie szybsze od analogicznych algorytmów dla macierzach gęstych. Dzięki zastosowaniu specjalnych struktur danych, przechowywanie i operacje na macierzach rzadkich wiążą się ze znacznie mniejszym zużyciem pamięci operacyjnej niż w przypadku macierzy gęstych o tych samych rozmiarach. Macierze rzadkie spotykane w zastosowaniach praktycznych często mają tak wielki stopień (tj. rozmiar), że jakiekolwiek operacje na nich za pomocą standardowych algorytmów byłyby zupełnie niemożliwe.

Nie istnieje ścisłe kryterium pozwalające odróżniać macierze rzadkie od gęstych. W praktyce określenie jakiejś macierzy jako rzadkiej oznacza, że opłaca się operować na niej za pomocą algorytmów przeznaczonych dla macierzy rzadkich. Zgodnie z tym kryterium zakwalifikowanie macierzy jako macierzy rzadkiej może zależeć od problemu, w którym macierz ta występuje. Np. rozkład LU niezdegenerowanej macierzy A o niewielkiej liczbie niezerowych elementów rozmieszczonych na losowych miejscach najczęściej daje w wyniku gęste macierze L i U, dlatego w tym zagadnieniu macierz A nie będzie uznana za rzadką. Jednak ta sama macierz w zagadnieniu znalezienia rozwiązania układu równań liniowych Ax = b najprawdopodobniej zostanie uznana za rzadką.

Zobacz też[edytuj | edytuj kod]