FSPAI
From Sccswiki
Contents 
Factorized Sparse Approximate Inverses
 This is a dummy textLatest release is 1.1
We developed a sequential and highly scalable parallel C/C++ implementation
of the
known FSPAI (Factorized SParse Approximate Inverses) algorithm.
Note that there is a scalable implementation of Modified Sparse Approximate
Inverses (MSPAI) as well.
Theory
FSPAI is a preconditioner for large sparse and illconditioned symmetric positive
definite systems of linear equations. It is the factorized version of the SPAI
algorithm. FSPAI is inherently parallel and generates a preconditioner which
approximates the inverse of the Cholesky factor of the system matrix, i.e.,
Based on an initial chosen sparsity structure, FSPAI automatically updates its
sparsity structure and improves on a current approximation.
Features
 Single source providing
 highly scalable parallel implementation
 sequential (MPI free) implementation
 Support for real and complex valued problems
 PCG solver available using HYPRE package
 Arbitrary start patterns, i.e., possibility to compute a FSAI without
updating the pattern  Support for sparse methods using CXSparse by Tim Davis
 Caching and Hashing approach to avoid redundant Cholesky decompositions
 Written in C/C++
We are currently working on a next release which will cover a highly scalable
block version of FSPAI, i.e., BFSPAI.
Download
FSPAI 1.1
In contrast to FSPAI 1.0, FSPAI 1.1 additionally requires CXSparse and UFconfig.
If you are not going to use the Fspai Caching/Hashing or the
sparse methods,
you can use FSPAI 1.0 instead.
 Source code tar ball: fspai1.1.tar.gz.
 Manual: fspai1.1.pdf.
 Only the HTML documentation of source code: htmlonlyfspai1.1.tar.gz
FSPAI 1.0
 Source code tar ball: fspai1.0.tar.gz.
 Manual: fspai1.0.pdf.
 Only the HTML documentation of source code: htmlonlyfspai1.0.tar.gz
Tested environments
 Shaheen from the KAUST Supercomputing Laboratory (KSL) at King
Abdullah University of Science and Technology (KAUST): 65536 compute cores: 16 racks of Blue Gene/P, each containing
1024 quadcore, 32bit 850 MHz PowerPC compute nodes  Architecture: PowerPC (PPC)
 Compiler version: IBM XL C/C++ Advanced Edition for Blue Gene/P, V9.0
 Libraries:
 Lapack 3.2.1
 MPI based on MPICH2
 HYPRE 2.7
 65536 compute cores: 16 racks of Blue Gene/P, each containing
 InfiniBandCluster of the Lehrstuhl Rechnertechnik und Rechnerorganisation/
Parallelrechnerarchitektur of Technische Universtität München: 128 compute cores: AMD Opteron™ Processor 850
 Architecture: x86_64
 Compiler version: gcc version 4.2.4 (Ubuntu 4.2.41ubuntu3)
 Libraries:
 Lapack 3.0
 MPI based on MPICH 1.2.7
 HYPRE 2.7.0b
 i686pclinuxgnu:
 Processor: Intel® Core™2 Duo CPU P8700 @ 2.53GHz
 Architecture: i686
 Compiler version: gcc version 4.3.4 (Gentoo 4.3.4 p1.1, pie10.1.5)
 Libraries:
 Lapack 3.3.1
 HYPRE 2.7.0b
FSPAI 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 noninfringement. In no event
shall the copyright holders
or anyone distributing FSPAI be liable for any
damages or other liability, whether in contract, tort or otherwise, arising
from, out of or in connection with FSPAI or the use
or other dealings in FSPAI.
Some References
Papers

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.

M. Grote and T. Huckle: Parallel preconditioning with sparse approximate inverses [BibTeX].
In SIAM J. Sci. Comput., Volume 18(3), 1997.

A. Kallischko: Modified Sparse Approximate Inverses (MSPAI) for Parallel Preconditioning [] [BibTeX].
Dissertation, Fakultät für Mathematik, Technische Universität München, March 2008.
Thesis

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.
Further
 Short summary on sparse approximate inverses with core reference list: summary.pdf
 Extended reference list: extended.pdf
Authors
License
FSPAI: Factorized Sparse Approximate Inverses
Copyright © 20122013, Matous Sedlacek
Research Unit 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 FSPAI we would appreciate that you refer to FSPAI.
Further work on Sparse Approximate Inverses
 SPAI: Parallel Implementation on SPAI — Sparse Approximate Inverses:
http://www.computational.unibas.ch/software/spai/  MSPAI: Parallel implementation of MSPAI — Modified Sparse Approximate Inverses:
http://www5.in.tum.de/wiki/index.php/MSPAI  PARASAILS: Parallel Sparse Approximate Inverse (LeastSquares) Preconditioner:
https://computation.llnl.gov/casc/parasails/parasails.html  HYPRE: Software on high performance preconditioners containing a PARASAILS module:
https://computation.llnl.gov/casc/linear_solvers/sls_hypre.html