Introduction

The BCP3.0 library (Block Constant Preconditioner, also known as BCAI, Block Constant Approximate Inverse) computes an approximate inverse of a sparse matrix. It consists in a set of m-files and mex-files for Matlab.

Sparse Approximate Inverse methods try to build a matrix that is a good approximation of the inverse of the original sparse matrix. Hence they are used as preconditionners for iterative solvers, as a replacement of incomplete factorisations.
Classical sparse approximate inverse use the same sparsity pattern than the original matrix A (or A², etc…). If A is a matrix built from a PDE dicretization, then its inverse is approximation of the Green function of the PDE : (A^-1)_i,j≅g(x_i,x_j), hence A^-1 is not sparse, and approximating it with a sparse matrix which has the pattern of A may not lead to a good approximation. This can be seen as an approximation of a continuous function with a set of Dirac masses.
Hence the basic idea of the block sparse approximate inverse, is to have a staircase approximation of the Green function:

Below is an example of block sparse approximate: as you can see, the original matrix (on the left) is sparse, and the BCP matrix is full (1e-7 < C_i,j < 0.95) but as it is a bloc constant matrix, it does not use more memory than the original one!

left: sparsity pattern of the original matrix A; right: log10(BCP(A)) [clic here for a larger picture]