Macierz rzadka

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


Niektóre typy macierzy
Cechy niezależne od bazy:
macierz nieosobliwa
macierz osobliwa
macierz zerowa
macierz nilpotentna
macierz idempotentna

macierz ortogonalna
macierz symetryczna
macierz dodatnio określona
macierz antysymetryczna

macierz unitarna
macierz hermitowska

Cechy zależne od bazy:
macierz jednostkowa
macierz skalarna
macierz diagonalna
macierz trójkątna
macierz schodkowa
macierz klatkowa
macierz wstęgowa

macierz elementarna
macierz rzadka


Operacje na macierzach
operacje elementarne

mnożenie przez skalar
dodawanie i odejmowanie

mnożenie macierzy
odwracanie macierzy

transpozycja macierzy
sprzężenie macierzy
macierz dopełnień algebraicznych
macierz dołączona

diagonalizacja
postać Jordana


Inne zagadnienia
rząd macierzy
wyznacznik macierzy
ślad macierzy
minor macierzy

widmo 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 o niewielkiej liczbie niezerowych elementów rozmieszczonych na losowych miejscach najczęściej daje w wyniku gęste macierze i , dlatego w tym zagadnieniu macierz nie będzie uznana za rzadką. Jednak ta sama macierz w zagadnieniu znalezienia rozwiązania układu równań liniowych najprawdopodobniej zostanie uznana za rzadką.

Zobacz też[edytuj]