In der numerischen Mathematik bezeichnet man als dunnbesetzte oder schwachbesetzte Matrix ( englisch sparse matrix ) eine Matrix , bei der so viele Eintrage aus Nullen bestehen, dass man nach Moglichkeiten sucht, dies insbesondere hinsichtlich Algorithmen sowie Speicherung auszunutzen. Bei quadratischen Matrizen mit insgesamt ${\displaystyle n^{2}}$ Eintragen sind dies viele Matrizen mit ${\displaystyle O(n)}$ oder auch noch ${\displaystyle O(n\cdot \log n)}$ Eintragen ungleich Null. Das Gegenstuck zu einer dunnbesetzten Matrix wird vollbesetzte Matrix genannt. Der Begriff wurde von James Hardy Wilkinson eingefuhrt, der ihn erstmals 1971 niederschrieb. ^[1] Analog dazu wird ein Vektor , der zu einem Großteil aus Nullen besteht, als dunnbesetzter Vektor ( englisch sparse vector ) bezeichnet. Haufig sind die Zeilen- oder Spaltenvektoren einer dunnbesetzten Matrix dunnbesetzte Vektoren, es gibt aber auch dunnbesetzte Matrizen, bei denen manche Zeilen oder Spalten vollbesetzt sind.

Die Diskretisierung von partiellen Differentialgleichungen fuhrt meistens auf dunnbesetzte Matrizen, etwa auf Bandmatrizen , ebenfalls die Darstellung von vielen typischen Graphen (bei beschranktem Knotengrad , Planaritat o. A.) uber ihre Adjazenzmatrix . Zu beachten ist, dass die Inverse einer dunnbesetzten Matrix im Regelfall vollbesetzt ist, ebenso wie die LR-Zerlegung . Eine Ausnahme bilden dabei die Bandmatrizen, bei denen eine solche Zerlegung ebenfalls dunnbesetzt sein kann.

Dunnbesetzte Matrizen haben die Eigenschaft, dass sie effizient abgespeichert werden konnen, indem man nur Position und Wert der Nicht-Null-Eintrage abspeichert. Die Position der Nichtnulleintrage wird auch als Besetzungsstruktur oder Sparsity Pattern bezeichnet. Die Auswertung eines dunnbesetzten Matrix-Vektor-Produkts kann ebenfalls effizient erfolgen, indem die Nullen in der Berechnung des Produkts nicht berucksichtigt werden.

Dieses findet insbesondere Verwendung bei Krylow-Unterraum-Verfahren zur naherungsweisen Losung von linearen Gleichungssystemen , die nur Skalar- und Matrix-Vektor-Produkte zur Durchfuhrung benotigen. Da die Berechnung der vollbesetzten LR-Zerlegung ${\displaystyle O(n^{3})}$ Operationen benotigt, das Matrix-Vektor-Produkt einer Matrix mit ${\displaystyle O(n)}$ Eintragen aber nur ${\displaystyle O(n)}$, sind diese Verfahren, falls sie nach nur wenigen Iterationen konvergieren, extrem effizient. Zur Effizienzsteigerung werden dort so genannte Vorkonditionierer eingesetzt. Fur dunnbesetzte Matrizen ist hier die unvollstandige LU-Zerlegung ein verbreitetes Verfahren, das eine fehlerbehaftete LR-Zerlegung berechnet, die aber eine ahnliche Besetzungsstruktur hat wie die originale Matrix und damit nicht wesentlich mehr Speicher braucht.

CRS ( Compressed Row Storage ) und CCS (Compressed Column Storage) sind zwei Moglichkeiten, eine dunnbesetzte Matrix platzsparend zu speichern.

• 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 Losung großer schwachbesetzter Gleichungssysteme (= Leitfaden der angewandten Mathematik und Mechanik. Band 69 = Teubner-Studienbucher. Mathematik. ). 2., uberarbeitete und erweiterte Auflage. Teubner, Stuttgart 1993, ISBN 3-519-12372-X .

1. ↑ Tim Davis: NA-Digest, 2007, Volume 07, Issue 12