MSPAI: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
= Modified Sparse Approximate Inverses -- UNDER CONSTRUCTION!!! = | = Modified Sparse Approximate Inverses -- UNDER CONSTRUCTION!!! = | ||
Based upon the well-known sparse approximate inverse preconditioner [http://www.computational.unibas.ch/software/spai/ SPAI], we developed the ''modified sparse approximate inverse (MSPAI)'' preconditioner. | Based upon the well-known sparse approximate inverse preconditioner [http://www.computational.unibas.ch/software/spai/ SPAI], <br> we developed the ''modified sparse approximate inverse (MSPAI)'' preconditioner. | ||
== Theory == | == Theory == | ||
[[Image:spai.png]] | MSPAI is a preconditioner for large sparse and ill-conditioned systems of <br> linear equations. We extended the basic SPAI minimization | ||
: [[Image:spai.png]] | |||
to target form and further generalized it in order to add additional ''probing constraints'': | to target form and further generalized it in order to add additional ''probing constraints'': | ||
[[Image:mspai.png]] | : [[Image:mspai.png]] | ||
For an overview of the versatile employment possibilities of our MSPAI formulation, see this [http://www5.in.tum.de/software/mspai/mspai_variants.pdf pdf] taken from [http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20071114-632977-1-5 here]. | For an overview of the versatile employment possibilities of our MSPAI formulation, <br> | ||
see this [http://www5.in.tum.de/software/mspai/mspai_variants.pdf pdf] taken from [http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20071114-632977-1-5 here]. | |||
== Implementation and Features == | == 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. | The entire implementation is done in C++ with parallelization in MPI. Except the Block <br> SPAI approach, we cover the full functionality of SPAI 3.2. | ||
=== Methodical improvements === | === Methodical improvements === | ||
* 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 <br> 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 | * Improve given factorized preconditioners such as ILU, AINV, FSAI, <br> FSPAI, etc subject to probing subspaces. | ||
* Compute sparse spectrally equivalent approximations to dense or even full matrices | * Compute sparse spectrally equivalent approximations to dense or <br> even full matrices. | ||
=== Technical improvements === | |||
* Support for complex valued problems. | |||
* Support for sparse QR methods using [http://www.cise.ufl.edu/research/sparse/CSparse/ 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 <br> 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 <br> Matrix Market format only. | |||
* Full support for complex problems in all features. | |||
== Download == | |||
=== | === MSPAI 1.1 === | ||
* Source code tar ball: []. | |||
* HTML documentation for source code: []. | |||
* Source code and HTML documentation: []. | |||
* MSPAI manual, closely adapted from SPAI 3.2 manual: []. | |||
== | === Thesis on MSPAI === | ||
* MSPAI 1. | * Ph.D. thesis about MSPAI, both theory and implementation: [http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20071114-632977-1-5 mediatum]. | ||
* | * Details about sparse QR methods in SPAI applications (german only): []. | ||
* Further details about implementation (german only): [http://www5.in.tum.de/software/mspai/sedlacek_diplomathesis.pdf pdf]. | |||
== MSPAI References == | == 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> | <pubsccs>nocaption=1&persid=53&utypid=1020&datum=2007&lang=en</pubsccs><pubsccs>nocaption=1&persid=53&utypid=2030&datum=2008&lang=en</pubsccs> | ||
Revision as of 14:35, 9 October 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
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.1
- Source code tar ball: [].
- HTML documentation for source code: [].
- Source code and HTML documentation: [].
- MSPAI manual, closely adapted from SPAI 3.2 manual: [].
Thesis on MSPAI
- 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>