imported>Mathze: Sprachliche Straffung

2025-09-18T15:08:49Z

Sprachliche Straffung

Neue Seite

[[Datei:Finite element sparse matrix.png|mini|Besetzungsstruktur einer dünnbesetzten Matrix aus einer [[Finite-Elemente-Verfahren|Finite-Elemente-Rechnung]], Nichtnulleinträge erscheinen in Schwarz]]
In der [[Numerische Mathematik|numerischen Mathematik]] bezeichnet man als '''dünnbesetzte''' oder '''schwachbesetzte Matrix''' ({{enS|sparse matrix}}) eine [[Matrix (Mathematik)|Matrix]], bei der so viele Einträge aus Nullen bestehen, dass man nach Möglichkeiten sucht, dies insbesondere hinsichtlich [[Algorithmus|Algorithmen]] sowie [[Datenstruktur|Speicherung]] auszunutzen. Bei quadratischen Matrizen mit insgesamt <math>n^2</math> Einträgen sind dies viele Matrizen mit <math>O(n)</math> oder auch noch <math>O(n\cdot \log n)</math> Einträgen ungleich Null. Das Gegenstück zu einer dünnbesetzten Matrix wird vollbesetzte Matrix genannt. Der Begriff wurde 1971 von [[James Hardy Wilkinson]] eingeführt.<ref>Tim Davis: [https://netlib.org/na-digest-html/07/v07n12.html#1 NA-Digest, 2007, Volume 07, Issue 12]</ref> Analog dazu wird ein [[Vektor]], der zu einem Großteil aus Nullen besteht, als '''dünnbesetzter Vektor''' ({{enS|sparse vector}}) bezeichnet. Häufig sind die Zeilen- oder Spaltenvektoren einer dünnbesetzten Matrix dünnbesetzte Vektoren, es gibt aber auch dünnbesetzte Matrizen, bei denen manche Zeilen oder Spalten vollbesetzt sind.

== Verwendung ==
Die [[Diskretisierung]] von [[Partielle Differentialgleichung|partiellen Differentialgleichungen]] führt meistens auf dünnbesetzte Matrizen, etwa auf [[Bandmatrix|Bandmatrizen]], ebenfalls die Darstellung von vielen typischen [[Graph (Graphentheorie)|Graphen]] (bei beschränktem [[Grad (Graphentheorie)|Knotengrad]], [[Planarer Graph|Planarität]] o. Ä.) über ihre [[Adjazenzmatrix]]. Zu beachten ist, dass die [[Inverse Matrix|Inverse]] einer dünnbesetzten Matrix im Regelfall vollbesetzt ist, ebenso wie die [[LR-Zerlegung]]. Eine Ausnahme bilden dabei die Bandmatrizen, bei denen eine solche Zerlegung ebenfalls dünnbesetzt sein kann.

Dünnbesetzte Matrizen haben die Eigenschaft, dass sie effizient abgespeichert werden können, indem man nur Position und Wert der Nicht-Null-Einträge abspeichert. Die Position der Nichtnulleinträge wird auch als ''Besetzungsstruktur'' oder ''Sparsity Pattern'' bezeichnet. Die Auswertung eines dünnbesetzten [[Matrix-Vektor-Produkt]]s kann ebenfalls effizient erfolgen, indem die Nullen in der Berechnung des Produkts nicht berücksichtigt werden.

Dieses findet insbesondere Verwendung bei [[Krylow-Unterraum-Verfahren]] zur näherungsweisen Lösung von [[Lineares Gleichungssystem|linearen Gleichungssystemen]], die nur Skalar- und Matrix-Vektor-Produkte zur Durchführung benötigen. Da die Berechnung der vollbesetzten LR-Zerlegung <math>O(n^3)</math> Operationen benötigt, das Matrix-Vektor-Produkt einer Matrix mit <math>O(n)</math> Einträgen aber nur <math>O(n)</math>, sind diese Verfahren, falls sie nach nur wenigen Iterationen konvergieren, extrem effizient. Zur Effizienzsteigerung werden dort so genannte [[Vorkonditionierung|Vorkonditionierer]] eingesetzt. Für dünnbesetzte Matrizen ist hier die [[ILU-Zerlegung|unvollständige LU-Zerlegung]] ein verbreitetes Verfahren, das eine fehlerbehaftete LR-Zerlegung berechnet, die aber eine ähnliche Besetzungsstruktur hat wie die originale Matrix und damit nicht wesentlich mehr Speicher braucht.

CRS ([[Compressed Row Storage]]) und CCS (Compressed Column Storage) sind zwei Möglichkeiten, eine dünnbesetzte Matrix platzsparend zu speichern.

== Literatur ==
* Yousef Saad: ''Iterative Methods for Sparse Linear Systems.'' 2nd edition. SIAM Society for Industrial & Applied Mathematics, Philadelphia PA 2003, ISBN 0-89871-534-2.
* [[Wolfgang Hackbusch]]: ''Iterative Lösung großer schwachbesetzter Gleichungssysteme'' (= ''Leitfäden der angewandten Mathematik und Mechanik.'' Band 69 = ''Teubner-Studienbücher. Mathematik.''). 2., überarbeitete und erweiterte Auflage. Teubner, Stuttgart 1993, ISBN 3-519-12372-X.

== Einzelnachweise ==
<references />

{{SORTIERUNG:Dunnbesetzte Matrix}}
[[Kategorie:Matrix]]
[[Kategorie:Numerische lineare Algebra]]

Dünnbesetzte Matrix - Versionsgeschichte

imported>Mathze: Sprachliche Straffung