Sparse Matrix Compression Formats

BCCSBlock Compressed Column Storage format
BCRSBlock Compressed Row Storage format
BNDLinpack Banded format
BSRBlock Sparse Row format
CCSCompressed Column Storage format
COOCoordinate format
CRSCompressed Row Storage format
CSCCompressed Sparse Column format
CSRCompressed Sparse Row format
DIADiagonal format
DNSDense format
ELLEllpack-Itpack generalized diagonal format
JADJagged Diagonal format
LNKLinked list storage format
MSRModified Compressed Sparse Row format
NSKNonsymmetric Skyline format
SSKSymmetric Skyline format
SSSSymmetric Sparse Skyline format
USSUnsymmetric Sparse Skyline format
VBRVariable Block Row format

Example

Uncompressed Matrix

Nj
A=
11 12 13 14 0 0
0 22 23 0 0 0
0 0 33 34 35 36
0 0 0 44 45 0
0 0 0 0 0 56
0 0 0 0 0 66
Ni

Variables
iRow index
jColumn index
kElement index in compressed data vector
a(i,j)Element at matrix row i, column j
 
Abbreviations
NNumber of elements per side of the matrix
NBNumber of elements per side of the Block
NDZNumber of Diagonal Zeros
NNZNumber of Non-Zeros
NNZBNumber of Non-Zero Blocks
NRNumber of blocks per side of the matrix
OOrder of magnitude

Compressed Row Storage / Compressed Sparse Row

i 1 2 3 4 5 6 7 O
Row Start Index k 1 5 7 11 13 14 15 Ni+1
k 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Column Index j 1 2 3 4 2 3 3 4 5 6 4 5 6 6 NNZ
Data a(i,j) 11 12 13 14 22 23 33 34 35 36 44 45 56 66 NNZ
Row Start Index : 1 ≤ i ≤ Ni:if Data(k) = a(i,j) then RowStartIndex(i) ≤ k < RowStartIndex(i+1)
i = Ni+1:k = NNZ+1
Order is 2*NNZ + Ni + 1 (=35)

Compressed Column Storage / Compressed Sparse Column / Harwell-Boeing Sparse Matrix

j 1 2 3 4 5 6 7 O
Column Start Index k 1 2 4 7 10 12 15 Nj+1
k 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Row Index i 1 1 2 1 2 3 1 3 4 3 4 3 5 6 NNZ
Data a(i,j) 11 12 22 13 23 33 14 34 44 35 45 36 56 66 NNZ
Column Start Index : 1 ≤ j ≤ Nj:if Data(k) = a(i,j) then ColumnStartIndex(j) ≤ k < ColumnStartIndex(j+1)
j = Nj+1:k = NNZ+1
Order is 2*NNZ + Nj + 1 (=35)

Modified Compressed Sparse Row

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 O
Index k;j 8 11 12 15 16 17 17 2 3 4 3 4 5 6 5 6 NNZ+NDZ+1
Data a(i,j) 11 22 33 44 0 66 12 13 14 23 34 35 36 45 56 NNZ+NDZ+1
kIndexData
1 ≤ k ≤ NiRow Start Indexa(k,k)
Ni+1NNZ+NDZ+1
Ni+2 ≤ k ≤ NNZ+NDZ+1Column Indexa(i,j), i<>j
Order is 2*NNZ + 2*NDZ + 2 (=32)

Modified Compressed Sparse Column

k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 O
Index k;i 8 8 9 11 13 15 17 1 1 2 1 3 3 4 3 5 NNZ+NDZ+1
Data a(i,j) 11 22 33 44 0 66 12 13 23 14 34 35 45 36 56 NNZ+NDZ+1
kIndexData
1 ≤ k ≤ NjColumn Start Indexa(k,k)
Nj+1NNZ+NDZ+1
Nj+2 ≤ k ≤ NNZ+NDZ+1Row Indexa(i,j), i<>j
Order is 2*NNZ + 2*NDZ + 2 (=32)

Block Compressed Row Storage / Block Sparse Row

i 1 2 3 4 O
Row Start Index k 1 3 5 6 NRi+1
k 1 2 3 4 5
Column Index j 1 3 3 5 5 NNZB
Data a(i,j) 11 12 13 14 33 34 35 36 0 56 NNZB*NBi*NBj
0 22 23 0 0 44 45 0 0 66
NRi = Ni/NBi
Order is NNZB*NBi*NBj + NNZB + NRi + 1 (=29)