# 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

Documentation
For installation details, links to papers and the like please see the SPAI manual.

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 check

If Matlab is installed, and in the current PATH, you can use

./configure --with-matlab

to build the Matlab interface functions.

Example
ORSIRR2: entries in inv(A) larger than 0.001 in absolute value (left) and sparse approximate inverse M with eps = 0.2 (right).

Authors
The package is developed by Marcus J. Grote, Stephen Barnard (up to version 3.0), Olaf Schenk, Oliver Broeker and Michael Hagemann (Configuration).

# Kontakt

Universität Basel

Dr. Anja Matthiä
Studiengangskoordination
Computational Sciences

Biozentrum, c/o sciCORE
Klingelbergstrasse 50/70
CH-4056 Basel
KLB61, Raum 1005
Tel. +41 (0)61 207 57 29
anja.matthiae-at-unibas.ch