Spärliche Matrix

Beispiel einer spärlichen Matrix ${\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}$

Die obige spärliche Matrix enthält nur 9 Elemente ohne Null mit 26 Nullelementen. Seine Sparsity beträgt 74%und ihre Dichte 26%.

Im numerische Analyse und Wissenschaftliches rechnen, a spärliche Matrix oder Spärmer Array ist ein Matrix in denen die meisten Elemente Null sind.^[1] Es gibt keine strenge Definition bezüglich des Anteils von Nullwertelementen für eine Matrix, die sich qualifizieren kann spärlich Ein häufiges Kriterium ist jedoch, dass die Anzahl der Elemente ungleich Null ungefähr der Anzahl der Zeilen oder Spalten entspricht. Im Gegensatz dazu wird die Matrix berücksichtigt, wenn die meisten Elemente ungleich Null sind dicht.^[1] Die Anzahl der nullwertigen Elemente geteilt durch die Gesamtzahl der Elemente (z. B.,,, m × n für ein m × n Matrix) wird manchmal als die bezeichnet Spärlichkeit der Matrix.

Konzeptionell entspricht Sparsity Systemen mit wenigen paarweisen Wechselwirkungen. Betrachten Sie beispielsweise eine Linie von Kugeln, die von Federn von einem zum nächsten verbunden sind: Dies ist ein spärliches System, da nur benachbarte Kugeln gekoppelt sind. Wenn im Gegensatz dazu die gleiche Kugellinie in Quellen haben würde, die jeden Ball mit allen anderen Kugeln verbinden, würde das System einer dichten Matrix entsprechen. Das Konzept der Sparsamkeit ist nützlich in Kombinatorik und Anwendungsbereiche wie z. Netzwerktheorie und numerische Analyse, die typischerweise eine geringe Dichte an signifikanten Daten oder Verbindungen aufweisen. Große spärliche Matrizen erscheinen oft in wissenschaftlich oder Ingenieurwesen Anwendungen beim Lösen partielle Differentialgleichungen.

Beim Speichern und Manipulieren von spärlichen Matrizen auf a ComputerEs ist vorteilhaft und oft notwendig, spezialisiert zu verwenden Algorithmen und Datenstrukturen Das nutzt die spärliche Struktur der Matrix. Spezialisierte Computer wurden für spärliche Matrizen gemacht,^[2] wie sie im Bereich des maschinellen Lernens üblich sind.^[3] Operationen unter Verwendung von Standard-Dichtmatrixstrukturen und Algorithmen sind langsam und ineffizient, wenn sie auf große spärliche Matrizen als Verarbeitung angewendet werden und ineffizient Erinnerung werden auf den Nullen verschwendet. Spärliche Daten sind von Natur aus leichter komprimiert und erfordert somit erheblich weniger Lagerung. Einige sehr große spärliche Matrizen können mithilfe von Standard-Matrix-Algorithmen nicht manipulieren.

Aufbewahrung einer spärlichen Matrix

Eine Matrix wird typischerweise als zweidimensionales Array gespeichert. Jeder Eintrag im Array repräsentiert ein Element a_i,j der Matrix und wird von den beiden zugegriffen Indizes i und j. Konventionell, i ist der Zeilenindex, der von oben nach unten nummeriert ist, und j ist der Spaltenindex, der von links nach rechts nummeriert ist. Für ein m × n Matrix, die zum Speichern der Matrix in diesem Format erforderliche Speichermenge ist proportional zu m × n (Missachtung der Tatsache, dass auch die Dimensionen der Matrix gespeichert werden müssen).

Bei einer spärlichen Matrix können erhebliche Reduzierungen des Gedächtnisses realisiert werden, indem nur die Einträge ungleich Null gespeichert werden. Abhängig von der Anzahl und Verteilung der Einträge ungleich Null können verschiedene Datenstrukturen verwendet werden und im Vergleich zum grundlegenden Ansatz enorme Einsparungen im Speicher erzielen. Der Kompromiss ist, dass der Zugriff auf die einzelnen Elemente komplexer wird und zusätzliche Strukturen erforderlich sind, um die ursprüngliche Matrix eindeutig wiederherzustellen.

Formate können in zwei Gruppen unterteilt werden:

• Diejenigen, die eine effiziente Modifikation unterstützen, wie DOK (Wörterbuch von Keys), LIL (Liste der Listen) oder COO (Koordinatenliste). Diese werden typischerweise zum Konstruktion der Matrizen verwendet.
• Diejenigen, die effiziente Zugriffs- und Matrixoperationen unterstützen, wie z. B. CSR (komprimierte spärliche Zeile) oder CSC (komprimierte spärliche Säule).

Wörterbuch von Schlüssel (DOK)

Dok besteht aus a Wörterbuch das karten (Zeile Spalte)-Paare zum Wert der Elemente. Elemente, die im Wörterbuch fehlen, werden als Null angesehen. Das Format ist gut, um eine spärliche Matrix in zufälliger Reihenfolge schrittweise zu konstruieren, aber schlecht für die Iterierung von Werten ungleich Null in lexikografischer Reihenfolge. Man konstruiert normalerweise eine Matrix in diesem Format und konvertiert dann zur Verarbeitung in ein ein effizienteres Format.^[4]

Liste der Listen (lil)

Lil speichert eine Liste pro Zeile, wobei jeder Eintrag den Spaltenindex und den Wert enthält. In der Regel werden diese Einträge nach dem Spaltenindex für eine schnellere Suche sortiert. Dies ist ein weiteres Format für die inkrementelle Matrixkonstruktion.^[5]

Koordinatenliste (COO)

COO speichert eine Liste von (Zeile, Spalte, Wert) Tupel. Im Idealfall werden die Einträge zunächst nach Zeilenindex und dann nach dem Spaltenindex sortiert, um die Zufallszugriffszeiten zu verbessern. Dies ist ein anderes Format, das für die inkrementelle Matrixkonstruktion gut ist.^[6]

Komprimierte spärliche Reihe (CSR-, CRS- oder Yale -Format)

Das Komprimierte spärliche Reihe (CSR) oder Druckspeicher (CRS) oder Yale -Format repräsentiert eine Matrix M durch drei (eindimensionale) Arrays, die jeweils ungleich Null-Werte, Zeilen und Säulenindizes enthalten. Es ähnelt COO, komprimiert aber die Zeilenindizes, daher der Name. Dieses Format ermöglicht schnelle Zeilenzugriffs- und Matrix-Vektor-Multiplikationen (Mx). Das CSR-Format wird seit mindestens Mitte der 1960er Jahre verwendet, wobei die erste vollständige Beschreibung im Jahr 1967 erschien.^[7]

Das CSR -Format speichert einen spärlichen m × n Matrix M in Zeilenform unter Verwendung von drei (eindimensionalen) Arrays (V, col_index, row_index). Lassen Nnz bezeichnen die Anzahl der Einträge ungleich Null in M. (Beachten Sie, dass Null-basierte Indizes soll hier verwendet werden.)

• Die Arrays V und Col_index sind von Länge Nnzund enthalten die Werte ungleich Null und die Säulenindizes dieser Werte.
• Das Array Row_index ist von Länge m + 1 und codiert den Index in V und Col_index wo die angegebene Reihe beginnt. Dies entspricht zu Row_index [j] Codierung der Gesamtzahl der Nicht -Zieros über der Reihe j. Das letzte Element ist Nnz , d.h. der fiktive Index in V unmittelbar nach dem letzten gültigen Index Nnz - 1. ^[8]

Zum Beispiel die Matrix

ist ein 4 × 4 Matrix mit 4 ungleich Null -Elementen, daher

V = [5 8 3 6] col_index = [0 1 2 1] row_index = [0 1 2 3 4]

unter der Annahme einer Null-Indexed-Sprache.

Um eine Reihe zu extrahieren, definieren wir zunächst:

row_start = row_index [row] row_end = row_index [row + 1]

Dann nehmen wir Scheiben von V und col_index ab row_start und enden von row_end.

Um die Zeile 1 (die zweite Reihe) dieser Matrix zu extrahieren, die wir eingestellt haben row_start = 1 und row_end = 2. Dann machen wir die Scheiben V [1: 2] = [8] und Col_index [1: 2] = [1]. Wir wissen jetzt, dass wir in Zeile 1 ein Element in Spalte 1 mit Wert 8 haben.

In diesem Fall enthält die CSR -Darstellung 13 Einträge, verglichen mit 16 in der ursprünglichen Matrix. Das CSR -Format spart den Speicher nur dann, wenn Nnz <(m (n - 1) - 1) / 2.

Ein weiteres Beispiel, die Matrix

ist ein 4 × 6 Matrix (24 Einträge) mit 8 Elementen ungleich Null, also

V = [10 20 30 40 50 60 70 80] col_index = [0 1 1 3 2 3 4 5] row_index = [0 2 4 7 8]

Das Ganze wird als 21 Einträge aufbewahrt: 8 in V, 8 in Col_indexund 5 in Row_index.

• Row_index spaltet das Array V in Reihen: (10, 20) (30, 40) (50, 60, 70) (80), Angabe des Index von V (und Col_index) wo jede Reihe beginnt und endet;
• Col_index Ausrichtung der Werte in Spalten: (10, 20, ...) (0, 30, 0, 40, ...) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Beachten Sie, dass in diesem Format der erste Wert von Row_index ist immer Null und das letzte ist immer NnzSie sind also in gewissem Sinne überflüssig (obwohl in Programmiersprachen, in denen die Arraylänge explizit gespeichert werden muss, Nnz wäre nicht überflüssig). Dies vermeidet jedoch die Notwendigkeit, einen Ausnahmefall bei der Berechnung der Länge jeder Zeile zu verarbeiten, da sie die Formel garantiert Row_index [i + 1] - row_index [i] funktioniert für jede Reihe i. Darüber hinaus sind die Speicherkosten dieser redundanten Speicherung für eine ausreichend große Matrix wahrscheinlich unbedeutend.

Die (alten) Yale -spärlichen Matrixformate sind Instanzen des CSR -Schemas. Das alte Yale -Format funktioniert genau wie oben beschrieben mit drei Arrays; Das neue Format kombiniert sich Row_index und Col_index in ein einzelnes Array und behandelt die Diagonale der Matrix getrennt.^[9]

Zum logisch AdjazenzmatrizenDas Datenarray kann weggelassen werden, da die Existenz eines Eintrags in das Zeilenarray ausreicht, um eine binäre Adjazenzbeziehung zu modellieren.

Es ist wahrscheinlich als Yale -Format bekannt, da es im Jale Sparse Matrix -Paket -Bericht von 1977 der Abteilung für Informatik an der Yale University vorgeschlagen wurde.^[10]

Komprimierte spärliche Säule (CSC oder CCS)

CSC ähnelt der CSR, außer dass Werte zuerst nach Spalte gelesen werden, ein Zeilenindex für jeden Wert gespeichert und Spaltenzeiger gespeichert werden. Zum Beispiel ist CSC (Val, Row_ind, col_ptr), wo val ist ein Array der (oben nach rechts) ungleich Null-Werte der Matrix; row_ind sind die Zeilenindizes, die den Werten entsprechen; und, col_ptr ist die Liste von val Indizes, bei denen jede Spalte beginnt. Der Name basiert auf der Tatsache, dass die Spaltenindexinformationen relativ zum COO -Format komprimiert werden. Man verwendet typischerweise ein anderes Format (lil, DOK, COO) für den Bau. Dieses Format ist effizient für arithmetische Operationen, Säulenschnitte und Matrixvektorprodukte. Sehen scipy.sparse.csc_matrix. Dies ist das herkömmliche Format zur Angabe einer spärlichen Matrix in Matlab (über die spärlich Funktion).

Sonderstruktur

Gebunden

Eine wichtige besondere Art von spärlichen Matrizen ist Bandmatrix, definiert wie folgt. Das niedrigere Bandbreite einer Matrix A ist die kleinste Zahl p so dass der Eintrag a_i,j verschwindet wann immer i > j + p. Ebenso das Obere Bandbreite ist die kleinste Zahl p so dass a_i,j = 0 Wann immer i < j − p (Golub & Van Loan 1996§1.2.1). Zum Beispiel a Triagonalmatrix hat eine niedrigere Bandbreite 1 und obere Bandbreite 1. Als ein weiteres Beispiel hat die folgende spärliche Matrix eine untere und obere Bandbreite, beide gleich 3. Beachten Sie, dass Nullen für Klarheit mit Punkten dargestellt werden.

Matrizen mit einigermaßen kleiner oberer und unterer Bandbreite werden als Bandmatrizen bezeichnet und verleihen sich häufig einfachere Algorithmen als allgemeine spärliche Matrizen. Oder man kann manchmal dichte Matrixalgorithmen anwenden und Effizienz einfach durch eine reduzierte Anzahl von Indizes zu gewinnen.

Durch Neuanordnung der Zeilen und Säulen einer Matrix A Es kann möglich sein, eine Matrix zu erhalten A′ mit einer niedrigeren Bandbreite. Eine Reihe von Algorithmen ist für Bandbreite Minimierung.

Diagonale

Eine sehr effiziente Struktur für einen extremen Fall von Bandmatrizen, die diagonale Matrix, ist nur die Einträge in der zu speichern Hauptdiagonale Als ein eindimensionales Arrayso eine Diagonale n × n Matrix erfordert nur n Einträge.

Symmetrisch

Eine symmetrische spärliche Matrix entsteht als die Adjazenzmatrix von einem ungerichtete Grafik; Es kann effizient als Adjazenzliste.

Block Diagonal

A Block-diagonale Matrix besteht aus Submatrizen entlang seiner diagonalen Blöcke. Eine blockdiagonale Matrix A hat die Form

wo A_k ist eine quadratische Matrix für alle k = 1, ..., n.

Reduzierung der Füllung

Das ergänze einer Matrix sind jene Einträge, die sich während der Ausführung eines Algorithmus von einem anfänglichen Null zu einem Wert ungleich Null ändern. Um die Speicheranforderungen und die Anzahl der während eines Algorithmus verwendeten arithmetischen Operationen zu reduzieren, ist es nützlich, das Einfüllen durch Schalten von Zeilen und Spalten in der Matrix zu minimieren. Das Symbolische Cholesky -Zersetzung Kann verwendet werden, um das schlechteste Ausfüllen zu berechnen, bevor Sie das tatsächliche durchführen Cholesky -Zersetzung.

Es gibt andere Methoden als die Cholesky -Zersetzung in Benutzung. Orthogonalisierungsmethoden (z. B. die QR -Faktorisierung) sind beispielsweise bei der Lösung von Problemen mit den geringsten Quadratsmethoden. Während das theoretische Ausfüllen immer noch gleich ist, können die "falschen Nicht-Ziers" für verschiedene Methoden unterschiedlich sein. Und symbolische Versionen dieser Algorithmen können auf die gleiche Weise wie das symbolische Cholesky verwendet werden, um das schlimmste Fall zu berechnen.

Lösen von spärlichen Matrixgleichungen

Beide iterativ und direkte Methoden existieren zur spärlichen Matrixlösung.

Iterative Methoden wie z. Konjugat -Gradient Methode und Gmres Verwenden Sie schnelle Berechnungen von Matrixvektorprodukten ${\ displayStyle ax_ {i}}$, wo Matrix ${\ displayStyle a}$ ist spärlich. Die Verwendung von Vorkondonierer kann die Konvergenz solcher iterativen Methoden erheblich beschleunigen.

Software

Viele Software -Bibliotheken unterstützen spärliche Matrizen und bieten Löser für spärliche Matrixgleichungen. Das Folgende ist Open-Source:

• Suitessparse, Eine Reihe spärlicher Matrixalgorithmen, die auf die direkte Lösung von spärlichen linearen Systemen ausgerichtet sind.
• PETSC, eine große C -Bibliothek, die viele verschiedene Matrixlöser für eine Vielzahl von Matrixspeicherformaten enthält.
• Trilinos, eine große C ++-Bibliothek mit Unterlibraren, die der Speicherung dichtes und spärlicher Matrizen und der Lösung entsprechender linearer Systeme gewidmet sind.
• Eigen3 ist eine C ++ - Bibliothek, die mehrere spärliche Matrixlöser enthält. Es ist jedoch keiner von ihnen parallelisiert.
• MUMPS (Multifrontal Massist PArallel spärlich direkt SOlver), geschrieben in fortran90, ist a Frontallöser.
• Deal.ii, eine Finite-Elemente-Bibliothek, die auch über ein Unter-Bibliothek für spärliche lineare Systeme und ihre Lösung verfügt.
• DÜNE, eine weitere Finite-Elemente-Bibliothek, die auch über ein Unterbibliothek für spärliche lineare Systeme und ihre Lösung verfügt.
• Pastix.
• Superlu.
• Gürteltier Bietet einen benutzerfreundlichen C ++-Wrapper für BLAS und LAPACK.
• Scipy Bietet Unterstützung für mehrere spärliche Matrixformate, lineare Algebra und Löser.
• Spärliche Matrix (Spam) R- und Python -Paket für spärliche Matrizen.
• Wolfram Sprache Werkzeuge zum Umgang mit spärlichen Arrays
• Alglib ist eine C ++ - und C# -Bibliothek mit spärlicher linearer Algebra -Unterstützung
• Arpack FORTRAN 77 Bibliothek für spärliche Matrixdiagonalisierung und -manipulation unter Verwendung des Arnoldi -Algorithmus
• SPÄRLICH Referenz (alt) NIST Paket für (reale oder komplexe) spärliche Matrixdiagonalisierung
• Slepc Bibliothek zur Lösung von linearen Systemen und spärlicher Matrizen zur Lösung von großem Maßstab
• Sympiler, ein domänenspezifischer Codegenerator und eine Bibliothek zur Lösung linearer Systeme und quadratischer Programmierungsprobleme.
• Scikit-Learn Ein Python -Paket für die Datenanalyse einschließlich spärlicher Matrizen.
• Sprs Implementiert spärliche Matrixdatenstrukturen und lineare Algebra -Algorithmen in reinem Rost.
• Basic Matrix Library (BML) Unterstützt mehrere spärliche Matrixformate und lineare Algebra -Algorithmen mit Bindungen für C, C ++ und FORTRAN.

Geschichte

Der Begriff spärliche Matrix wurde möglicherweise von geprägt von Harry Markowitz wer initiierte einige Pionierarbeit, verließ dann aber das Feld.^[11]

Siehe auch

Anmerkungen

Verweise

• Golub, Gene H.; Van Loan, Charles F. (1996). Matrixberechnungen (3. Aufl.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Einführung in die numerische Analyse (3. Aufl.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (Mai 1973). Sparse Matrices (Teil der Mathematik in Science & Engineering Series). Academic Press Inc. (Dieses Buch von einem Professor an der State University of New York im Stony Book war das erste Buch, das ausschließlich spärlichen Matrizen gewidmet war. Abschlusskurse, die dieses als Lehrbuch verwendeten, wurden Anfang der 1980er Jahre an dieser Universität angeboten.)
• Bank, Randolph E.; Douglas, Craig C. "Spärliche Matrix -Multiplikationspaket" (PDF).
• Pissanetzky, Sergio (1984). Spärliche Matrix -Technologie. Akademische Presse. ISBN 9780125575805.
• Snay, Richard A. (1976). "Reduzierung des Profils spärlicher symmetrischer Matrizen". Bulletin Géodésique. 50 (4): 341–352. Bibcode:1976bgeod..50..341s. doi:10.1007/bf02521587. HDL:2027/UC1.31210024848523. S2CID 123079384. Auch NOAA Technisches Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.^[1]

Weitere Lektüre

• Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). "Ein Vergleich mehrerer Bandbreiten- und Profilreduzierungsalgorithmen". ACM -Transaktionen auf mathematischer Software. 2 (4): 322–330. doi:10.1145/355705.355707. S2CID 14494429.
• Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). "Spärliche Matrizen in MATLAB: Design und Implementierung". Siam Journal über Matrixanalyse und Anwendungen. 13 (1): 333–356. Citeseerx 10.1.1.470.1054. doi:10.1137/0613024.
• Sparse Matrixalgorithmen Forschung an der Texas A & M University.
• Suitsparse Matrixsammlung
• Kleines Projekt Ein von EU finanziertes Projekt zu spärlichen Modellen, Algorithmen und Wörterbuchlernen für große Daten.