Hohlmatrix

In der Disziplin der numerischen Analyse der Mathematik ist eine spärliche Matrix eine Matrix, die viele Nullen enthält.

Konzeptionell entsprechen spärliche Matrizen Systemen, die nicht sehr gekoppelt sind. Wenn wir eine Reihe von Kugeln betrachten, von denen jede durch Gummibänder mit ihren direkten Nachbarn verbunden ist, würde dieses System durch eine hohle Matrix dargestellt. Im Gegenteil, wenn jede Kugel in der Reihe mit allen anderen Kugeln verbunden ist, würde dieses System durch eine dichte Matrix dargestellt . Dieses Konzept der spärlichen Matrix wird häufig in der kombinatorischen Analyse und ihren Anwendungsgebieten wie der Theorie der Netzwerke verwendet , die eine geringe Verbindungsdichte aufweisen.

In der Wissenschaft oder Technik treten häufig große, spärliche Matrizen auf , um partielle Differentialgleichungen zu lösen .

Wenn wir spärliche Matrizen mit dem Computer-Tool verarbeiten oder speichern möchten, ist es vorteilhaft oder sogar oft notwendig, Algorithmen und Datenstrukturen zu verwenden, die die spärliche Struktur der Matrix berücksichtigen: da Zeilen- und Spaltenkoordinaten unabhängig davon den Zugriff auf eine Adresse ermöglichen der physischen Organisation der Daten.

Die physikalische Darstellung all dieser Nullen im Speicher bei Verwendung auf großen, spärlichen Arrays wäre teuer und langsam. Es ist billiger und schneller zu sagen, dass jeder leere Wert für gegebene Koordinaten Null ist. Diese Datenkomprimierung führt fast immer zu einer signifikanten Aufteilung des Speicherverbrauchs bei vernachlässigbaren zusätzlichen Verarbeitungskosten. Einige sehr große, dünn besetzte Matrizen können jedoch mit herkömmlichen Algorithmen nicht verarbeitet werden.

Die zum Speichern eines Arrays verwendete naive Datenstruktur ist ein zweidimensionales Array. Jeder Eintrag im Array repräsentiert ein Element a i , j der Matrix, das von den beiden Indizes i und j erreicht werden kann . Für eine m × n- Matrix werden mindestens ( m × n ) Speicherplätze fester Größe benötigt , um die Matrix darzustellen.

Viele, wenn nicht die meisten Einträge in einer dünn besetzten Matrix sind Nullen. Die Grundidee besteht dann darin, nur die Nicht-Null-Eingaben der Matrix zu speichern, anstatt alle zu speichern. Abhängig von der Anzahl und Verteilung der Eingaben ungleich Null können unterschiedliche Datenstrukturen verwendet werden, was zu großen Einsparungen bei der im Speicher verwendeten Größe im Vergleich zur naiven Struktur führt. Diese Technik wird auch verwendet, wenn die Matrix einen Graphen darstellt  : Wenn eine Bitkante vorliegt, wird die Adjazenzliste für die Adjazenzmatrix bevorzugt .

Ein Beispiel für eine solche Darstellung ist das Yale Sparse Matrix-Format. Es speichert eine Matrix M der Größe m × n als drei eindimensionale Arrays. Wenn wir NNNdie Anzahl der Einträge in der Nicht-Null-Matrix M bezeichnen .

  • Das erste Array wird notiert Aund ist in der Länge NNN. Es enthält alle Werte der Nicht-Null-Eingänge von M von links nach rechts und von oben nach unten (die Werte werden in der ersten Zeile von links nach rechts, in der zweiten von links nach rechts usw. übernommen ).
  • Das zweite Array wird IAdurch die Länge angegeben (die Anzahl der Zeilen plus eins). Es wird rekursiv definiert: und wo ist die Anzahl der Einträge ungleich Null in Zeile i (Indizierung von 0). Die Zeile i der ursprünglichen Matrix M besteht aus den Elementen von Index zu Index (oder sie ist leer, wenn ).IA(0)=0IA(i+1)=IA(i)+NNNiNNNiAIA(i)IA(i+1)-1IA(i)=IA(i+1)
  • Das dritte Array wird mit JALänge bezeichnet und NNNenthält die Spaltennummer jedes Elements von A.

Zum Beispiel die folgende 4 × 8- Matrix

[ 1 2 0 0 0 0 0 0 ] [ 0 3 0 0 0 0 9 0 ] [ 0 0 0 0 0 0 0 0 ] [ 0 0 1 0 0 0 0 4 ]

wird in diesem Format durch dargestellt

A = [ 1 2 3 9 1 4 ] IA = [ 0 2 4 4 6 ] JA = [ 0 1 1 6 2 7 ]

Beispiel

Eine Bitmap mit nur zwei Farben, von denen eine dominant ist (z. B. eine Datei mit einer Signatur), kann als dünne Matrix gespeichert werden, die nur die Pixel der nicht dominanten Farbe enthält.

Diagonale Matrizen

Eine sehr effiziente Struktur zum Speichern einer Diagonalmatrix besteht darin, nur die Einträge der Hauptdiagonale in einem eindimensionalen Array zu speichern. Eine n × n- Diagonalmatrix erfordert nur n Einträge.

Bandbreite

Die niedrige Bandbreite einer Matrix M ist die kleinste ganze Zahl p, so dass die Eingänge a ij für i > j + p Null sind . Ebenso ist die hohe Bandbreite die kleinste ganze Zahl p, so dass die Eingänge a ij für i < j - p Null sind . Beispielsweise hat eine tridiagonale Matrix eine niedrige Bandbreite von 1 und eine hohe Bandbreite von 1.

Die Matrizen mit kleinen Breiten des hohen und niedrigen Bandes werden als Bandmatrizen  (in) bezeichnet, und es existieren häufig Algorithmen, die effizienter sind als diejenigen auf dünn besetzten Matrizen.

Zum Beispiel reduziert der Cuthill-McKee-Algorithmus  (in) die Bandbreite einer hohlen Matrix und symmetrisch , und es gibt viele andere Methoden, um diese Bandbreite zu reduzieren.

Füllphänomen

Das Ausfüllen einer Sparse-Matrix stellt die Anzahl der Einträge dar, die während der Ausführung eines Algorithmus von einem Nullwert auf einen anderen Wert als Null übergehen. Um die zusätzlichen Anforderungen an den Speicher und die Berechnungskosten, die dieses Phänomen verursacht, zu verringern, ist es notwendig, diese Füllung zu begrenzen, was durch Vertauschen der Spalten und Zeilen der Matrix erfolgen kann. Das Füllen ist ein theoretischer Begriff, der sich nicht zwischen den verschiedenen Algorithmen ( Cholesky-Faktorisierung , QR-Zerlegung usw.) ändert , die auf die Matrix angewendet werden können, aber die Anzahl der Nullen, die während der Ausführung tatsächlich einen Wert ungleich Null annehmen, variiert je nach ‚angewandt Algorithmus und einige Algorithmen haben eine Version Symbol , das die Füllung im schlimmsten Fall, wie die liefert symbolische Cholesky - Zerlegung  (in) .

Lösen von Gleichungen, die durch eine spärliche Matrix dargestellt werden

Es gibt iterative und direkte Methoden , um Systeme zu lösen, die durch spärliche Matrizen dargestellt werden. Eine weit verbreitete iterative Methode ist die konjugierte Gradientenmethode .

Verweise

Externe Links

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">