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 aus Nullen bestehen, dass man nach Möglichkeiten sucht, dies insbesondere hinsichtlich Algorithmen sowie Speicherung auszunutzen. Bei quadratischen Matrizen mit insgesamt ${\displaystyle n^{2}}$ Einträgen sind dies viele Matrizen mit ${\displaystyle O(n)}$ oder auch noch ${\displaystyle O(n\cdot \log n)}$ Einträgen ungleich Null. Das Gegenstück zu einer dünnbesetzten Matrix wird vollbesetzte Matrix genannt. Der Begriff wurde von James Hardy Wilkinson eingeführt, der ihn erstmals 1971 niederschrieb. Analog dazu wird ein Vektor, der zu einem Großteil aus Nullen besteht, als dünnbesetzter Vektor (englisch 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.