[ Features | Download | Documentation | Quick Installation | Example | Authors ]
SPAI — Sparse Approximate Inverses
Given a sparse matrix A the SPAI Algorithm computes a sparse approximate inverse M by minimizing || AM - I || in the Frobenius norm. The approximate inverse is computed explicitly and can then be applied as a preconditioner to an iterative method. The sparsity pattern of the approximate inverse is either fixed a priori or captured automatically:
- Fixed sparsity: The sparsity pattern of M is either banded or a subset of the sparsity pattern of A.
- Adaptive sparsity: The algorithm proceeds until the 2-norm of each column of AM-I is less than eps. By varying eps the user controls the quality and the cost of computing the preconditioner. Usually the optimal eps lies between 0.5 and 0.7.
A very sparse preconditioner is very cheap to compute but may not lead to much improvement, while if M becomes rather dense it becomes too expensive to compute. The optimal preconditioner lies between these two extremes and is problem and computer architecture dependent.
The approximate inverse M can also be used as a robust (parallel) smoother for (algebraic) multi-grid methods.
There is a mailing list at https://www.maillist.unibas.ch/mailman/listinfo/spai/.
Features
- robust,
- inherently parallel,
- no break-down (A nonsingular),
- ordering independent,
- effective on nonsymmetric and ill-conditioned problems,
- written in C/MPI
Quick Installation
The package uses the autoconf tools in order to facilitate the compilation on various platforms. The following steps should configure and build the software:tar xzvf spai-3.2.tar.gz cd spai-3.2 ./configure make make checkIf Matlab is installed, and in the current PATH, you can use
./configure --with-matlabto build the Matlab interface functions.
Example
ORSIRR2
ORSIRR2: entries in inv(A) larger than 0.001 in absolute value (left) and sparse approximate inverse M with eps = 0.2 (right).
Matrix M1
