Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Kurs: MATLAB - Weitere Datentypen

Dünn besetzte Matrizen

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
Matrizen, bei denen ein großer Anteil der Elemente 0 ist, lassen sich effizienter im Sparse-Format speichern. In dieser Darstellung werden nur die von 0 verschiedenen Elemente und deren Indizes in Listen abgelegt. Alle Matrixoperationen lassen sich auch auf Matrizen im Sparse-Format anwenden. Die Resultate sind dabei stets Sparse-Matrizen, sofern alle Parameter Sparse-Matrizen sind. Verknüpfungen mit vollbesetzten Matrizen (double array) ergeben vollbesetzte Matrizen.

Beispiel einer dünn besetzten $ (10\times 10)$-Matrix mit einem Belegungsgrad von ca. 5%: 

  >> S=sprand(10,10,.05)
  S =
     (7,2)       0.8699
     (9,4)       0.4442
     (5,5)       0.1472
     (1,9)       0.9566
     (8,9)       0.7694

  >> whos S
    Name      Size                    Bytes  Class
    S        10x10                      104  double array (sparse)
  Grand total is 5 elements using 104 bytes

Spezielle Funktionen zur Behandlung dünn besetzter Matrizen sind unter anderem:

 Erzeugung/Manipulation von Sparse-Matrizen
   sparse, full Konvertierung zwischen dünn und voll besetzten Matrizen
   speye, spdiags Einheits-/Diagonalmatrizen im Sparse-Format
   sprand, sprandn Sparse-Matrizen mit Pseudo-Zufallszahlen
   nonzeros, nnz Ausgabe der von 0 verschiedenen Elemente bzw. deren Anzahl
   spy Grafische Anzeige der Belegungsstruktur
 Funktionen für Sparse-Matrizen
   eigs, svds Bestimmung einiger Eigen- bzw. Singulärwerte
   normest, condest Norm- bzw. Konditionsschätzer
   pcg, minres Iterative Löser für dünnbesetzte Systeme
Eine Übersicht der für Sparse-Matrizen verfügbaren Befehle kann mittels
matlab/sparfun
angezeigt werden.
(Autoren: Hörner/Wipper)

Download:

( .m, 579 ,  27.03.2007)

(Beschreibung der Dateitypen)

Mit Hilfe der Befehle 
  >> A=sprand(100,100,.1); B=sprand(100,100,.2); C=sprand(100,100,.3);
  >> spy(B)
werden zunächst die drei dünn besetzten $ (100\times 100)$-Matrizen A, B und C erzeugt, bei denen rund 10%, 20% bzw. 30% der Elemente von 0 verschieden sind. Das nachfolgende Bild zeigt die mittels spy(B) dargestellte Belegungsstruktur der Matrix B:
\includegraphics[width=7cm]{bsp_sparse_spy1.eps}

Rechnen mit Sparse-Matrizen: 

  >> M=(A+B)*C;
  >> nnz(M)
  ans =
          9992
  >> F=full(M);
  >> whos
    Name      Size                    Bytes  Class
  
    A       100x100                   11900  double array (sparse)
    B       100x100                   22100  double array (sparse)
    C       100x100                   31688  double array (sparse)
    F       100x100                   80000  double array
    M       100x100                  120404  double array (sparse)
    ans       1x1                         8  double array
  
  Grand total is 25374 elements using 266100 bytes
Verknüpfungen von Sparse-Matrizen (wie bei der Berechnung von M) ergeben wiederum Sparse-Matrizen. Dabei ist jedoch darauf zu achten, dass der Belegungsgrad steigen und die Verwendung des Sparse-Formats damit ggf. ineffizient sein kann. In dem betrachteten Beispiel ist M aufgrund der 9992 von 0 verschiedenen Elemente nahezu vollbesetzt und benötigt gegenüber der in F gespeicherten Variante im double array Format rund 50% mehr Speicherplatz.

Wie das nachfolgende Beispiel zeigt, enstehen bei der Verknüpfung von Matrizen im dünn- und vollbesetzten Format stets vollbesetzte Ergebnismatrizen: 

  >> X=C-F;
  >> whos X
    Name      Size                    Bytes  Class
  
    X       100x100                   80000  double array
  
  Grand total is 10000 elements using 80000 bytes
(Autoren: Hörner/Wipper)
[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
  automatisch erstellt am 5.2.2008