Harwell-Boeing format

The Harwell-Boeing format (also called Compressed Column Storage (CCS)) is a data structure that is used when storing sparse matrices .

background

The elements of a matrix that are not zero are stored in columns from left to right. A total of three memory arrays are required (in the following , a matrix with m rows and n columns, nnz denotes the number of non-zero entries ): ${\ displaystyle A \ in \ mathbb {R} ^ {m \ times n}}$

value (real): Here are the non-zero entries of the matrix; the size of the array is na .

row_ind (int): For each element of value , there is the associated row index for the matrix ; the size of the array is also nnz . ${\ displaystyle A}$

col_ptr (int): Beginning of each matrix column from in value or row_ind . The size is , whereby the value nnz is saved in the last entry (provided the counting method starts with 0). In particular, col_ptr [i + 1] - col_ptr [i] describes the number of non-zero entries in column i. ${\ displaystyle A}$ ${\ displaystyle n + 1}$

The advantages of the format are the comparatively small storage space requirements, since the zero elements of a matrix are not saved. In particular, this type of storage is used for quick access to a column of . If faster access to lines is required, the CRS format can be used instead , in which the entries are recorded line by line, but which otherwise corresponds to the CCS format. The Harwell-Boeing format is used e.g. B. in the discretization of partial differential equations in the area of finite element methods , where the stiffness matrices are often stored in this data structure. ${\ displaystyle A}$

example

The matrix is given with nnz = 8 non-zero entries . In the event that the counting of the storage of elements starts from 0, the following values result for storage in CCS format: ${\ displaystyle 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}}}$

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

Harwell-Boeing format

background

example

Web links