Harwell-Boeing-Format

Das Harwell-Boeing-Format (auch Compressed Column Storage, deutsch komprimierte Spaltenspeicherung, kurz CCS-Format) ist eine Datenstruktur, die beim Speichern von dünnbesetzten Matrizen verwendet wird.

Hintergrund

Die Elemente einer Matrix, die nicht Null sind, werden dabei spaltenweise von links nach rechts abgelegt. Insgesamt werden drei Speicherarrays benötigt (im Folgenden ist $A\in \mathbb {R} ^{m\times n}$, also eine Matrix mit m Zeilen und n Spalten, nnz bezeichnet die Anzahl der Nichtnulleinträge):

• value (real): Hier stehen die Nichtnulleinträge der Matrix; die Größe des Arrays ist nnz.
• row_ind (int): Zu jedem Element von value steht hier der zugehörige Zeilenindex zur Matrix $A$; die Größe des Arrays beträgt ebenfalls nnz.
• col_ptr (int): Beginn jeder Matrixspalte von $A$ in value bzw. row_ind. Die Größe ist $n+1$, wobei im letzten Eintrag der Wert nnz gespeichert wird (sofern die Zählweise bei 0 beginnt). Insbesondere beschreibt col_ptr[i+1] - col_ptr[i] die Anzahl der Nichtnulleinträge in Spalte i.

Die Vorteile des Formates liegen dabei in einem vergleichsweise geringen Speicherplatzbedarf, da die Nullelemente einer Matrix nicht gespeichert werden. Insbesondere dient diese Art der Speicherung dem schnellen Zugriff auf eine Spalte von $A$. Wenn ein schneller Zugriff auf Zeilen benötigt wird, bietet sich stattdessen das CRS-Format an, bei dem die Einträge zeilenweise erfasst werden, das ansonsten aber dem CCS-Format entspricht. Angewendet wird das Harwell-Boeing-Format z. B. bei der Diskretisierung von partiellen Differentialgleichungen im Bereich von Finite-Elemente-Methoden, wo die Steifigkeitsmatrizen häufig in dieser Datenstruktur gespeichert werden.

Beispiel

Gegeben sei die Matrix $A={\begin{pmatrix}a_{00}&0&0&a_{03}\\a_{10}&a_{11}&0&0\\0&0&a_{22}&0\\a_{30}&a_{31}&0&a_{33}\end{pmatrix}}$ mit nnz = 8 Nichtnulleinträgen. Für den Fall, dass die Zählweise der Speicherung von Elementen ab 0 beginnt, ergeben sich für die Speicherung im CCS-Format folgende Werte:

• value = $[a_{00},a_{10},a_{30},a_{11},a_{31},a_{22},a_{03},a_{33}]$
• row_ind = $[0,1,3,1,3,2,0,3]$
• col_ptr = $[0,3,5,6,8]$

Weblinks

• http://people.sc.fsu.edu/~burkardt/data/hb/hb.html
• http://www.dorn.org/uni/sls/kap09/i01_00.htm