Veclibs Speicherschema für dünnbesetzte Matrizen

Verbreitetes Speicherschema:

• Vektor von Spaltenzeigern
• jeder zeigt auf eine Liste von Paaren
• jedes Paar besteht aus Zeilenindex und Wert
• symmetrische Matrix: nur unteres Dreieck incl. Diagonale

Beispiel:

• Fortran-Array (Indizes ab 1):
  
  $$\left( \begin{array}{cccccc} 0 & 0 & 3 & 0 & 0 & 0 \\ 0... ...& 0 & 0 & 6 \\ 0 & 0 & 0 & 0 & 4 & 0 \end{array} \right)$$
  
  

• Vektor von 6 Spaltenpointern:
  $$\begin{eqnarray*} colptr(1) & \rightarrow & ( (4,1) ) \\ colptr(2) & \rightar... ... (2,1), (6,4) ) \\ colptr(6) & \rightarrow & ( (4,4), (5,6) ) \end{eqnarray*}$$
  
  
  
  
  

Abbildung auf einfache Vektoren:

• alle Paare in der Reihenfolge der Spalten hintereinanderschreiben
• daraus zwei Vektoren:

  rowind	Liste der Zeilen-Indizes
  value	Liste der Werte

  jeweils Länge nz = Zahl der nichtverschwindenen Elemente

• dritter Vektor colstr beschreibt die Spalten:
  • Länge N+1, N = Zahl der Spalten
  • colstr(i) = Nummer des ersten Elements von Spalte i in rowind/value
  • colstr(N+1) = nz+1
  • $\rightarrow$ colstr(i+1) - colstr(i) = Zahl der Elemente $\neq 0$ in Spalte i
• Für die Beispielmatrix erhält man: