Wikipedia · einfach zusammengefasst · Stand
Dünnbesetzte Matrix
In der numerischen Mathematik bezeichnet man als dünnbesetzte oder schwachbesetzte Matrix (englisch sparse matrix) eine Matrix, bei der so viele Einträge …
Inhalt4 Abschnitte
Begriff und Bedeutung
Eine dünnbesetzte oder schwachbesetzte Matrix (englisch sparse matrix) ist in der numerischen Mathematik eine Matrix, deren Einträge größtenteils null sind. Diese vielen Nullen sollen bei der Speicherung und bei Algorithmen ausgenutzt werden.
Bei einer quadratischen Matrix mit insgesamt n² Einträgen gelten insbesondere Matrizen mit O(n) oder auch O(n · log n) Nichtnulleinträgen als dünnbesetzt. Das Gegenstück heißt vollbesetzte Matrix. Ein Vektor, der größtenteils aus Nullen besteht, heißt dünnbesetzter Vektor. Häufig sind die Zeilen- oder Spaltenvektoren einer dünnbesetzten Matrix dünnbesetzt; einzelne Zeilen oder Spalten können aber trotzdem vollbesetzt sein.
Typische Entstehung und Struktur
Dünnbesetzte Matrizen entstehen meist bei der Diskretisierung partieller Differentialgleichungen, zum Beispiel als Bandmatrizen. Auch viele typische Graphen lassen sich durch dünnbesetzte Adjazenzmatrizen darstellen, etwa bei beschränktem Knotengrad oder Planarität.
Die Positionen der Nichtnulleinträge heißen Besetzungsstruktur oder Sparsity Pattern. Für Berechnungen ist wichtig: Die Inverse einer dünnbesetzten Matrix und auch ihre LR-Zerlegung sind im Regelfall vollbesetzt. Bei Bandmatrizen kann die Zerlegung dagegen ebenfalls dünnbesetzt sein.
Speicherung und Berechnung
Effiziente Speicherung ist möglich, indem nur Wert und Position jedes Nichtnulleintrags gespeichert werden. CRS (Compressed Row Storage) und CCS (Compressed Column Storage) sind zwei platzsparende Speicherformen.
Auch ein Matrix-Vektor-Produkt lässt sich effizient auswerten, weil die Nulleinträge nicht berechnet werden müssen. Das ist besonders vorteilhaft, wenn eine Matrix nur O(n) Nichtnulleinträge besitzt: Dann benötigt ihr Matrix-Vektor-Produkt O(n) Operationen.
Lösung linearer Gleichungssysteme
Dünnbesetzte Matrizen werden insbesondere mit Krylow-Unterraum-Verfahren zur näherungsweisen Lösung linearer Gleichungssysteme verwendet. Diese Verfahren benötigen nur Skalarprodukte und Matrix-Vektor-Produkte.
Eine vollbesetzte LR-Zerlegung benötigt O(n³) Operationen. Krylow-Unterraum-Verfahren können daher extrem effizient sein, wenn sie nach wenigen Iterationen konvergieren. Zur weiteren Beschleunigung verwendet man Vorkonditionierer. Bei dünnbesetzten Matrizen ist die unvollständige LU-Zerlegung verbreitet: Sie berechnet eine fehlerbehaftete LR-Zerlegung, deren Besetzungsstruktur der ursprünglichen Matrix ähnlich ist und die deshalb nicht wesentlich mehr Speicher benötigt.