** Next:** Compressed Diagonal Storage
** Up:** Sparse Matrix Storage Formats
** Previous:** Compressed Column Storage
** Contents**
** Index**

##

Block Compressed Row Storage

If the sparse matrix is composed of square
dense blocks of nonzeros in some regular pattern, we can modify
the CRS (or CCS) format to exploit such block patterns. Block
matrices typically arise from the discretization of partial differential
equations in which there are several *degrees of freedom* associated
with a grid point. We then partition the matrix in small blocks with
a size equal to the number of degrees of freedom and treat each
block as a dense matrix, even though it may have some zeros.

If is the dimension of each block and is the number of nonzero
blocks in the matrix , then the total storage
needed is
.
The block
dimension of is then defined by .

Similar to the CRS format, we require three arrays for the BCRS format:
a rectangular array for floating point numbers (
`val(,,)`) which stores the nonzero blocks in
(block) row-wise fashion, an integer array (`col_ind()`)
which stores the actual column indices in the original matrix of
the () elements of the nonzero blocks, and a pointer
array (`row_blk()`) whose entries point to the beginning of
each block row in `val(:,:,:)` and `col_ind(:)`. The
savings in storage locations and reduction in time spent
doing indirect addressing for
block compressed row storage (BCRS)
over CRS can be significant for matrices with a large .

** Next:** Compressed Diagonal Storage
** Up:** Sparse Matrix Storage Formats
** Previous:** Compressed Column Storage
** Contents**
** Index**
Susan Blackford
2000-11-20