Personal tools

MSPAI

From Sccswiki

Jump to: navigation, search

Contents

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

Spai.jpg

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

Mspai.jpg

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

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

Papers

  • T. Huckle, A. Kallischko, A. Roy, M. Sedlacek and T. Weinzierl: An Efficient Parallel Implementation of the MSPAI Preconditioner [BibTeX].
    In Parallel Computing, Volume 36(5-6), p. 273–284, June 2010.
  • T. Huckle and A. Kallischko: Frobenius Norm Minimization and Probing for Preconditioning [BibTeX].
    In International Journal of Computer Mathematics, Volume 84(8), p. 1225–1248, August 2007.
  • T. Huckle: Factorized Sparse Approximate Inverses for Preconditioning [BibTeX].
    In Journal of Supercomputing, Volume 25(2), p. 109–117, 2003.
  • T. Huckle: Factorized Sparse Approximate Inverses for Preconditioning and Smoothing [BibTeX].
    In Selcuk Journal of Applied Mathematics, Volume 1(1) of Sonderheft zum 60. Geburtstag von Prof. Chr. Zenger, p. 63–70, 2000.
  • T. Huckle: Approximate Sparsity Patterns for the Inverse of a Matrix and Preconditioning [BibTeX].
    In Applied Numerical Mathematics, Volume 30, p. 291–303, 1999.
  • M. Grote and T. Huckle: Parallel preconditioning with sparse approximate inverses [BibTeX].
    In SIAM J. Sci. Comput., Volume 18(3), 1997.
  • T. Huckle: PVM-Implementation of Sparse Approximate Inverse preconditioners for Solving Large Sparse Linear Equations [] [BibTeX].
    In Proceedings of the Third Euro PVM Users' Group Meeting, 7.-9. Oktober 1996, München, Volume 1156 of Lecture Notes in Computer Science, p. 166–173, 1996.


Theses

  • M. Sedlacek: Sparse Approximate Inverses for Preconditioning, Smoothing, and Regularization [] [BibTeX].
    Dissertation, Fakultät für Informatik, Technische Universität München. mediaTUM, München, October 2012.
  • A. Kallischko: Modified Sparse Approximate Inverses (MSPAI) for Parallel Preconditioning [] [BibTeX].
    Dissertation, Fakultät für Mathematik, Technische Universität München, March 2008.
  • M. Sedlacek: Effiziente parallele Implementierung des MSPAI Präkonditionierers unter Verwendung von Caching-Strategien und QR-Updates [BibTeX].
    Diplomarbeit, Fakultät für Informatik, Technische Universität München, January 2008.


Further


Successful Applications

MSPAI

  • see References (Section 1.5),
    e.g. Smoothing and Regularization with MSPAI

SPAI

  • see References (Section 1.5.3),
    e.g. Alleon, G., Benzi, M., and Giraud, L.: Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics. Numerical Algorithms, Volume 16(1), p. 1-15 (1997)


Authors


License

MSPAI: Modified Sparse Approximate Inverses
Copyright © 2007-2013, Matous Sedlacek
Chair of Scientific Computing in Computer Science - Informatics V
Technische Universität München

This program is free software: you can redistribute it and/or modify it under the
terms of the GNU Lesser General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with
this program. If not, see http://www.gnu.org/licenses/.

If you obtain any results with MSPAI we would appreciate that you refer to MSPAI.


Funding

This work has partially been funded by Bund der Freunde der Technischen Universität München e.V. (BdF),
Antrag 2008-09.


Further work on Sparse Approximate Inverses

Retrieved from "https://www5.in.tum.de/wiki/index.php?title=MSPAI&oldid=12714"