Dünnbesetzte Matrix


Dünnbesetzte Matrix
Besetzungsstruktur einer dünnbesetzten Matrix aus einer Finite-Elemente-Rechnung, Nichtnulleinträge erscheinen in Schwarz

In der numerischen Mathematik bezeichnet man als dünnbesetzte oder schwachbesetzte Matrix eine Matrix, bei der so viele Einträge aus Nullen bestehen, dass es sich lohnt, dies auszunutzen. Bei quadratischen Matrizen, die O(n²) Einträge haben, sind dies viele Matrizen mit O(n) oder auch noch O(n\cdot \log n) Einträgen. 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.[1]

Die Diskretisierung von partiellen Differentialgleichungen führt meistens auf dünnbesetzte Matrizen, etwa auf Bandmatrizen, ebenfalls die Darstellung von Graphen über ihre Adjazenzmatrix. Zu beachten ist, dass die Inverse einer dünnbesetzten Matrix im Regelfall vollbesetzt ist, ebenso wie die LU-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-Produkts 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 linearen Gleichungssystemen, die nur Skalar- und Matrix-Vektor-Produkte zur Durchführung benötigen. Da die Berechnung der vollbesetzten LU-Zerlegung O(n3) Operationen benötigt, das Matrix-Vektor-Produkt einer Matrix mit O(n) Einträgen aber nur O(n), sind diese Verfahren, falls sie nur nach wenigen Iterationen konvergieren, extrem effizient. Zur Effizienzsteigerung werden dort so genannte Vorkonditionierer eingesetzt. Für dünnbesetzte Matrizen ist hier die unvollständige LU-Zerlegung ein verbreitetes Verfahren, das eine fehlerbehaftete LU-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 2003, ISBN 0-898-71534-2
  • Wolfgang Hackbusch: Iterative Lösung großer schwachbesetzter Gleichungssysteme, 2. Auflage, Teubner Studienbücher, 1993, ISBN 3-519-12372-X

Einzelnachweise

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Matrix - получить на Академике действующий промокод Pharmacosmetica или выгодно matrix купить со скидкой на распродаже в Pharmacosmetica

  • Gozinto-Matrix — Der Gozintograph ist ein gerichteter Graph, der beschreibt, aus welchen Teilen sich ein oder mehrere Produkte zusammensetzen. Der Produktionsprozess kann dabei mehrstufig sein, wobei der Input aus Rohstoffen, Halb und Fertigteilen besteht. Im… …   Deutsch Wikipedia

  • Dualer Simplex — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Eckentheorem — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Primaler Simplex — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplex-Algorithmus — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplex-Tableau — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplexalgorithmus — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Simplexverfahren — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • Duales Problem — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Linear programming — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia