Block Compressed Row Storage

If the sparse matrix $A$ 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 $n_b$ is the dimension of each block and $nnzb$ is the number of nonzero blocks in the $n \times n$ matrix $A$, then the total storage needed is  $nnz = nnzb \times n_b^2$. The block dimension $n_d$ of $A$ is then defined by $n_d = n / n_b$.

Similar to the CRS format, we require three arrays for the BCRS format: a rectangular array for floating point numbers ( val($1:nnzb$,$1:n_b$,$1:n_b$)) which stores the nonzero blocks in (block) row-wise fashion, an integer array (col_ind($1:nnzb$)) which stores the actual column indices in the original matrix $A$ of the ($1,1$) elements of the nonzero blocks, and a pointer array (row_blk($1:n_d+1$)) 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 $n_b$.