Sparse Matrizen – wann sollte man sie nutzen?

Jakob Gepp Blog, Data Science, Statistik

Wenn man mit Matrizen arbeitet, die viele Nullen enthalten, dann sind schwachbesetzte (engl. sparse) Matrizen das richtige. Hierbei wird der benötigte Speicherplatz der Matrix reduziert, in dem der Inhalt der Matrix effizienter verwaltet wird. Es gibt verschiedene Methoden Matrizen zu komprimieren – zum Beispiel in dem nur die Tupel aus Zeile, Spalte und Wert genutzt werden. Die Matrix

A= \left[ {\begin{array}{cccc}       1 & 0 & 0 & 1 \\       0 & 0 & 2 & 0 \\       4 & 0 & 0 & 0 \\       0 & 3 & 0 & 0  \end{array} } \right]\\

reduziert sich hierbei zu

A_{sparse} =  \begin{cases}  1, 1, 1  \\  1, 4, 1  \\  2, 3, 2  \\  3, 1, 4  \\  4, 2, 3 \end{cases}\\

Durch diese Umformung müssen nicht alle Werte gespeichert werden (Nullen fallen weg), wodurch weniger Platz benötigt wird.

Für Berechnungen mit sparsen Matrizen gibt es in R das package Matrix. Die Berechnungen auf diesen Matrizen sind deutlich effektiver im Speicherverbrauch als die normale base Verwendung. Sollte man nun immer sparse Matrizen verwenden?

Problem

Letztens hatte ich ein Problem mit der Laufzeit meines R Codes und konnte durch Debugging eine Zeile als Wurzel allen Übels identifizieren.

J[, c(2,3] <- J[, c(2,3)] -  const  * B 

Hierbei waren J_{n,k} und J_{n,2} als sparse Matrizen definiert und const ein numerischer Faktor. Das Ersetzen der beiden Spalten dauerte nun sehr lange und es stellte sich raus, dass J und B voll besetzt waren – also doch nicht sparse!
Mir kamen folgende Fragen auf: Bei welchen Operationen lohnen sich sparse Matrizen? Was passiert, wenn eine Matrix nicht schwachbesetzt ist, aber sie dennoch so definiert wird?

Simulation

Um diese Fragen zu beantworten, Für diese Problemstellung habe ich eine kleine Simulation durchgeführt und mir neben dem Speicherbedarf auch die Berechnugnszeiten folgender Operationen angeschaut:

t(X)                           # Transponieren
X %*% t(X)                     # Kreuzprodukt 
X + X                          # Addition 
X * X                          # Matrixmultiplikation 
X[, c(2,3)] <- X[, c(3,2)]     # Spalten vertauschen 

Weitere Einstellungen waren die Spaltenanzahl n der quadratischen Matrix X sowie die Dichte der Nullen innerhalb der Matrix.
Den genauen Code habe ich auf unserem git hinterlegt.

Auswertung

Wie erwartet ist die Reduktion des Speicherplatzes bei kleiner Spaltenanzahl n davon abhängig, wie viele Nullen in der Matrix vorhanden sind. Je höher die Dichte der Nullen, desto geringer der Speicherbedarf. Unter einer Dichte von ca. 50% lohnt es sich nicht mehr sparse Matrizen zu verwenden, um Speicherplatz zu sparen.

Abbildunug zum Speicherbedarf

Egal wie hoch der Anteil der Nullen innerhalb der Matrix ist, bei normalen Matrizen dauern die Matrixoperationen immer gleich lang. Dies erkennt man in der Abbildung daran, dass die durchgezogenen Linien übereinander verlaufen. Bei schwachbesetzten Matrizen brauchen die Berechnungen hingegen deutlich langsamer, wenn es sich um zellenbasierte Operationen handelt. Hierunter fällt auch das Ersetzten ganzer Spalten! Dies ist verständlich, wenn man sich nochmal verdeutlicht, wie die schwachbesetzten Matrizen gespeichert werden.

Abbildung zum Zeitverbrauch

Fazit

Eine Matrix für alle Fälle gibt es nicht. Die Verwendung hängt davon ab, was optimiert werden soll (Rechenzeit oder Speichergröße). Aber auch je nachdem welche Operationen durchgeführt werden müssen, können sich schwachbesetzte Matrizen lohnen oder einem die Laufzeit verlängern!

Über den Autor
Jakob Gepp

Jakob Gepp

Numbers were always my passion and as a data scientist and a statistician at STATWORX I can fullfill my nerdy needs. Also I am responsable for our blog. So if you have any questions or suggestions, just send me an email!