Modified Sparse Approximate Inverses

This is a dummy textLatest release is 1.2

Based upon the well-known sparse approximate inverse preconditioner SPAI,
we developed the modified sparse approximate inverse (MSPAI) preconditioner.

Note that there is a scalable implementation of Factorized Sparse Approximate
Inverses (FSPAI) as well.

Theory

MSPAI is a preconditioner for large sparse and ill-conditioned systems of
linear equations. We extended the basic SPAI minimization

to target form and further generalized it in order to add additional probing constraints:

For an overview of the versatile employment possibilities of our MSPAI formulation,
see this pdf taken from here.

Implementation and Features

The entire implementation is done in C++ with parallelization in MPI. Except the Block
SPAI approach, we cover the full functionality of SPAI 3.2.

Methodical improvements

Extension to target form: allow probing.
Support for explicit and inverse approximations, both in factorized
and unfactorized form and probing of Schur complements, see pdf.
Improve given factorized preconditioners such as ILU, AINV, FSAI,
FSPAI, etc subject to probing subspaces.
Compute sparse spectrally equivalent approximations to dense or
even full matrices.

Technical improvements

Support for complex valued problems.
Support for sparse QR methods using CSparse by Tim Davis.
Caching approach to avoid redundant QR decompositions.
Implementation of QR updates to accelerate pattern update steps.
Support for maximum sparsity patterns.
Arbitrary start patterns, i.e. possibility to compute a static SPAI
without pattern update steps.

Todo

Mex interface for MATLAB.
PetSc interface.
Support for other LAPACK implementations than ATLAS.
Wider coverage of file formats for sparse matrices, now support for
Matrix Market format only.
Full support for complex problems in all features.

Download

MSPAI 1.2

Source code tar ball: mspai-1.2.tar.gz.
Manual, closely adapted from SPAI 3.2 manual: mspai-1.2.pdf.

HTML documentation of source code: htmlonly-mspai-1.2.tar.gz.
Source code and HTML documentation: mspai-1.2-html.tar.gz.

Some Theses on MSPAI

Ph.D. thesis about MSPAI, both theory and implementation: mediaTUM.
Ph.D. thesis about SPAI, MSPAI, and FSPAI both theory and implementation: mediaTUM
Details about sparse QR methods in SPAI applications (german only): pdf.
Further details about implementation (german only): pdf.

Tested environments

InfiniBand-Cluster of the Lehrstuhl Rechnertechnik und Rechnerorganisation/
Parallelrechnerarchitektur of Technische Universtität München:
- 128 processors: AMD Opteron™ Processor 850
- Architecture: x86_64
- Compiler version: gcc version 3.3.3 (SuSE Linux)
- Libraries: lapack 3.0, csparse 2.2.0, MPI based on MPICH 1.2.7

i686-pc-linux-gnu:
- Processor:
  - Intel® Pentium® D CPU 2.80GHz,
  - Intel® Pentium® M CPU 1.60GHz
- Architecture: i686
- Compiler version:
  - gcc version 4.1.1 (Gentoo 4.1.1-r3), Intel® Compiler icpc version 9.1
  - gcc version 4.1.2 (Gentoo 4.1.2 p1.1)
- Libraries:
  - lapack 3.1.1, csparse 2.2.0
  - lapack 3.1, csparse 2.2.0

MSPAI is provided "as is", without warranty and support of any kind, express or
implied, including but not limited to the warranties of merchantability, fitness for a
particular purpose, title and non-infringement. In no event shall the copyright holders
or anyone distributing MSPAI be liable for any damages or other liability, whether in contract, tort or otherwise, arising from, out of or in connection with MSPAI or the use
or other dealings in MSPAI.

Some References