Macierz rzadka

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

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.

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 dwiema 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ż

• metoda macierzy rzadkich