MSPAI: Difference between revisions
No edit summary |
No edit summary |
||
| Line 21: | Line 21: | ||
* Extension to target form: allow probing | * Extension to target form: allow probing | ||
* Support for explicit and inverse approximations, both in factorized and unfactorized form and probing of Schur complements, see [http://www5.in.tum.de/software/mspai/mspai_variants.pdf pdf] | * Support for explicit and inverse approximations, both in factorized and unfactorized form and probing of Schur complements, see [http://www5.in.tum.de/software/mspai/mspai_variants.pdf 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 | |||
| Line 30: | Line 33: | ||
* Support for maximum sparsity patterns | * Support for maximum sparsity patterns | ||
* Arbitrary start patterns, i.e. possibility to compute a ''static'' SPAI without pattern update steps | * Arbitrary start patterns, i.e. possibility to compute a ''static'' SPAI without pattern update steps | ||
* MSPAI returns residual matrix ''R=I-AM'' for usage in symmetrization techniques | |||
Revision as of 20:13, 20 September 2008
Modified Sparse Approximate Inverses -- UNDER CONSTRUCTION!!!
Based upon the well-known sparse approximate inverse preconditioner SPAI, we developed the modified sparse approximate inverse (MSPAI) preconditioner.
Theory
MSPAI is a preconditioner for large sparse and ill-conditioned systems of linear equations. We extended the basic SPAI minimization
Error creating thumbnail: Unable to save thumbnail to destination
to target form and further generalized it in order to add additional probing constraints:
Error creating thumbnail: Unable to save thumbnail to destination
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
- MSPAI returns residual matrix R=I-AM for usage in symmetrization techniques
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
Download
- MSPAI 1.1 source code tar ball: []
- MSPAI manual, closely adapted from SPAI 3.2 manual: []
- Ph.D. thesis about MSPAI, both theory and implementation: mediatum
- Details about sparse QR methods in SPAI applications (german only): []
- Further details about implementation (german only): pdf
MSPAI References
<pubsccs>nocaption=1&persid=53&utypid=1020&datum=2007&lang=en</pubsccs><pubsccs>nocaption=1&persid=53&utypid=2030&datum=2008&lang=en</pubsccs>
under construction -- more information about MSPAI implementation and download will be available soon.