imported>Monmirage: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-10-15T21:21:43Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Das '''Harwell-Boeing-Format''' (auch ''Compressed Column Storage,'' {{deS|komprimierte Spaltenspeicherung}}, kurz '''CCS'''-Format) ist eine [[Datenstruktur]], die beim Speichern von [[Dünnbesetzte Matrix|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 <math>A \in \mathbb R^{m\times n}</math>, 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 <math>A</math>; die Größe des Arrays beträgt ebenfalls ''nnz''.
* ''col_ptr'' (int): Beginn jeder Matrixspalte von <math>A</math> in ''value'' bzw. ''row_ind''. Die Größe ist <math>n+1</math>, 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 <math>A</math>. Wenn ein schneller Zugriff auf Zeilen benötigt wird, bietet sich stattdessen das [[Compressed Row Storage|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-Methode]]n, wo die Steifigkeitsmatrizen häufig in dieser Datenstruktur gespeichert werden.

=== Beispiel ===
Gegeben sei die Matrix
<math>
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}
</math>
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'' = <math>[a_{00}, a_{10}, a_{30}, a_{11}, a_{31}, a_{22}, a_{03}, a_{33}]</math>
* ''row_ind'' = <math>[0, 1, 3, 1, 3, 2, 0, 3]</math>
* ''col_ptr'' = <math>[0, 3, 5, 6, 8]</math>

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

[[Kategorie:Datenformat]]

Harwell-Boeing-Format - Versionsgeschichte

imported>Monmirage: /* growthexperiments-addlink-summary-summary:1|0|0 */