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)                           # 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! Jakob Gepp Jakob Gepp

Mehr erfahren!

Als eines der führenden Beratungs- und Entwicklungsunternehmen für Data Science und KI begleiten wir Unternehmen in die datengetriebene Zukunft. Erfahre mehr über statworx und darüber, was uns antreibt.

Über uns