Sparse Matrizen – wann sollte man sie nutzen?
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)
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.
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.
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!
