Diese Antwort hat man schon seit langem befürchtet.

Vier gewinnt – deshalb geht es dieses Mal schon in Runde vier unserer Reihe zu dem Programm Matlab. In der letzten Ausgabe haben wir euch einen Einblick gegeben, worauf ihr beim Visualisieren von Daten in einem Plot achten solltet und was für Informationen wie hinzugefügt werden können.
Nicht nur Griechenland ist zum Sparen angehalten, auch bei der Programmierung ist es wichtig, sowohl Speicherplatz als auch Zeit zu sparen, denn beides ist bekanntlich Geld und macht die Effizienz eines Programmes aus. Matlab bietet für sogenannte spärlich besetzte Matrizen, das sind Matrizen mit einem hohen Anteil an Nulleinträgen, einen besonderen Datentyp, der sowohl speichertechnisch als auch zeitlich für eine starke Effizienzsteigerung sorgen kann.
Der Datentyp sparse ist speziell für diese Matrizen angelegt. Die normale Speicherweise von Matlab speichert Nulleinträge einer Matrix A genauso wie andere Werte, sodass die vollen m × n Einträge der Matrix gespeichert werden. Sparse-Matrizen merken sich nur noch die Indizes und Werte der Einträge, die nicht null sind. Somit hängt deren Speicherplatzbedarf nur noch von der Anzahl nnz(A) der Nichtnulleinträge ab. Das Verhältnis von Nichtnulleinträgen zu Gesamtanzahl an Einträgen wird auch als Dichte der Matrix bezeichnet. Das Gegenteil, also eine voll besetzte Matrix, wird logischerweise full genannt. Matrizen lassen sich mit den Befehlen sparse(A) bzw. full(A) von dem einen in den anderen Datentyp umwandeln.
Spezielle spärlich besetzte Matrizen lassen sich direkt erstellen. Der Begriff speye(n) erstellt eine Sparse-Einheitsmatrix, mithilfe von spdiags lassen sich Diagonalmatrizen erstellen. Die Syntax für diesen Befehl ist A=spdiags(B,d,m,n). Dabei ist B eine Matrix, welche als Spalten die gewünschten Diagonalenelemente enthält. d beschreibt die Positionen der Diagonalen – die Hauptdiagonale hat den Index 0, die oberen Nebendiagonalen positive, die unteren Nebendiagonalen negative Indexeinträge. Die Zahlen m und n beschreiben zuletzt die Dimension der Matrix. Das Ergebnis für die Eingabe A=spdiags(ones(3,1)*(1:4),[-2,-1,0,2],3,3) sieht wie folgt aus:

Für Statistiker gibt es außerdem mit A=sprand(m,n,Dichte) die Möglichkeit eine Sparse-Matrix mit zufällig gleichverteilten Werten zu generieren, welche die vorgegebene Dichte zwischen 0 und 1 besitzt.
Ein zusätzlicher Effizienzschub wird generell durch Präallokation erreicht. Ist die Größe einer Matrix bekannt und nicht von dynamischer Größe, so kann durch das vorherige Festlegen der Matrix (die Präallokation) das Programm noch besser laufen. Bei üblichen Matrizen ist das durch vorherige Definition als Nullmatrix möglich, für Sparse-Matrizen gibt es den spalloc-Befehl: Mit S=spalloc(m,n,nzmax) wird eine m × n Sparse-Matrix S erstellt, welche bis zu nzmax Nichtnulleinträge haben kann. Diese Zahl kann zwar überschritten werden, doch dann muss Matlab wieder dynamisch Speicher hinzufügen und der Effizienzgewinn ist verloren.
Es existieren noch einige weitere Befehle mit denen man Eigenschaften der Sparse-Matrizen abfragen kann. Der Befehl issparse(A) gibt einen boolean-Wert aus, der beschreibt, ob die Matrix im Sparse-Format vorliegt. nzmax(A) gibt den allokierten Speicherplatz, nnz(A) die Anzahl an Nichtnulleinträgen an. Nicht zu verwechseln ist dieser mit dem nonzeros-Befehl, welcher sämtliche Nichtnulleinträge ausgibt.
Die Befehle sind nun klar – doch worin ist nun der tatsächliche Nutzen zu sehen? Der Vergleich zwischen einer zufälligen Sparse-Matrix A=sprand(1000,1000,0.3) und ihrer Darstellung B=full(A) ergibt beim Speicherplatzvergleich 4.1 MB für Matrix A und 8 MB für Matrix B. Auch die Multiplikation ist um einiges schneller: Mit den Vektoren x=sprand(1000,1,0.3) bzw. y=full(x) ergibt sich für die Berechnung A*x eine benötigte Zeit von 0.05 Sekunden, im Vergleich dazu braucht die Berechnung B*y 0.63 Sekunden.
Insbesondere bei der Diskretisierung, beispielsweise von Gradienten oder von partiellen Differentialgleichungen treten solche spärlich besetzten Matrizen, häufig als Band- oder Blockmatrizen auf. Bei diesen Problemen sind damit viel größere Probleme vom Rechner beherrschbar – das Verwenden dieses Datentyps ist daher lohnend. In der nächsten Ausgabe gibt es weitere Tipps und Tricks rund um das Programm Matlab.

Noch keine Kommentare, sei der Erste!