Difference between revisions of "FSPAI"

From Sccswiki
Jump to navigation Jump to search
 
(25 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
= <u>Factorized Sparse Approximate Inverses</u> =
 
= <u>Factorized Sparse Approximate Inverses</u> =
: <span style="color:#ffffff">This is a dummy text</span><span style="font-variant:small-caps">'''Latest release is [http://www5.in.tum.de/software/fspai/fspai-1.0.tar.gz 1.0]'''</span>
+
: <span style="color:#ffffff">This is a dummy text</span><span style="font-variant:small-caps">'''Latest release is [http://www5.in.tum.de/software/fspai/fspai-1.1.tar.gz 1.1]'''</span>
  
 +
We developed a sequential and highly scalable parallel C/C++ implementation
 +
of the <br> known ''FSPAI (Factorized SParse Approximate Inverses)'' algorithm.
  
We developed a highly scalable sequential and parallel implementation of the
+
Note that there is a scalable implementation of [http://www5.in.tum.de/wiki/index.php/MSPAI Modified Sparse Approximate <br> Inverses (MSPAI)] as well.
known ''FSPAI (Factorized SParse Approximate Inverses)'' algorithm.
 
 
 
  
 
== Theory ==
 
== Theory ==
<!--
 
  
MSPAI is a preconditioner for large sparse and ill-conditioned systems of <br> linear equations. We extended the basic SPAI minimization
+
FSPAI is a preconditioner for large sparse and ill-conditioned symmetric positive <br> definite systems of linear equations. It is the factorized version of the SPAI <br> algorithm. FSPAI is inherently parallel and generates a preconditioner which <br> approximates the inverse of the Cholesky factor of the system matrix, i.e.,
  
: [[Image:spai.jpg]]
+
http://www5.in.tum.de/pic/Fspai.png
  
to target form and further generalized it in order to add additional ''probing constraints'':
+
Based on an initial chosen sparsity structure, FSPAI automatically updates its <br> sparsity structure and improves on a current approximation.
  
: [[Image:mspai.jpg]]
+
== Features ==
  
For an overview of the versatile employment possibilities of our MSPAI formulation, <br>
+
* Single source providing
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].
+
** highly scalable parallel implementation
-->
+
** sequential (MPI free) implementation
 +
* Support for real and complex valued problems
 +
* PCG solver available using [http://acts.nersc.gov/hypre/ HYPRE] package
 +
* Arbitrary start patterns, i.e., possibility to compute a FSAI without <br>  updating the pattern
 +
* Support for sparse methods using [http://www.cise.ufl.edu/research/sparse/CXSparse/ CXSparse] by Tim Davis
 +
* Caching and Hashing approach to avoid redundant Cholesky decompositions
 +
* Written in C/C++
  
== Implementation and Features ==
+
We are currently working on a next release which will cover a highly scalable <br> block version of FSPAI, i.e., BFSPAI.
<!--
 
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 ===
+
== Download ==
* Extension to target form: allow probing.
 
* 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, <br> FSPAI, etc subject to probing subspaces.
 
* Compute sparse spectrally equivalent approximations to dense or <br> even full matrices.
 
  
=== Technical improvements ===
+
=== FSPAI 1.1 ===
* 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 ===
+
In contrast to FSPAI 1.0, FSPAI 1.1 additionally requires [http://www.cise.ufl.edu/research/sparse/CXSparse/ CXSparse] and [http://www.cise.ufl.edu/research/sparse/UFconfig/ UFconfig]. <br>
* Mex interface for MATLAB.
+
If you are not going to use the Fspai Caching/Hashing or the
* PetSc interface.
+
sparse methods, <br> you can use FSPAI 1.0 instead.
* 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 ==
+
* Source code tar ball: [http://www5.in.tum.de/software/fspai/fspai-1.1.tar.gz fspai-1.1.tar.gz].
<!--
+
* Manual: [http://www5.in.tum.de/software/fspai/fspai-1.1.pdf fspai-1.1.pdf].
=== MSPAI 1.2 ===
+
* Only the HTML documentation of source code: [http://www5.in.tum.de/software/fspai/htmlonly-fspai-1.1.tar.gz htmlonly-fspai-1.1.tar.gz]
  
* Source code tar ball: [http://www5.in.tum.de/software/mspai/mspai-1.2.tar.gz mspai-1.2.tar.gz].
+
=== FSPAI 1.0 ===
* Manual, closely adapted from SPAI 3.2 manual: [http://www5.in.tum.de/software/mspai/mspai-1.2.pdf mspai-1.2.pdf].
 
  
* HTML documentation of source code: [http://www5.in.tum.de/software/mspai/htmlonly-mspai-1.2.tar.gz htmlonly-mspai-1.2.tar.gz].
+
* Source code tar ball: [http://www5.in.tum.de/software/fspai/fspai-1.0.tar.gz fspai-1.0.tar.gz].
* Source code and HTML documentation: [http://www5.in.tum.de/software/mspai/mspai-1.2-html.tar.gz mspai-1.2-html.tar.gz].
+
* Manual: [http://www5.in.tum.de/software/fspai/fspai-1.0.pdf fspai-1.0.pdf].
-->
+
* Only the HTML documentation of source code: [http://www5.in.tum.de/software/fspai/htmlonly-fspai-1.0.tar.gz htmlonly-fspai-1.0.tar.gz]
=== Some Theses on MSPAI ===
 
<!--
 
* 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): [http://www5.in.tum.de/software/mspai/roy_diplomathesis.pdf pdf].
 
* Further details about implementation (german only): [http://www5.in.tum.de/software/mspai/sedlacek_diplomathesis.pdf pdf].
 
-->
 
  
 
== Tested environments ==
 
== Tested environments ==
<!--
+
 
* [http://www.lrr.in.tum.de/Par/arch/infiniband/#cluster InfiniBand-Cluster] of the Lehrstuhl Rechnertechnik und Rechnerorganisation/<br>Parallelrechnerarchitektur of Technische Universtität München:
+
*[http://www.hpc.kaust.edu.sa/documentation/user_guide/ Shaheen] from the KAUST Supercomputing Laboratory (KSL) at King <br> Abdullah University of Science and Technology (KAUST):
** 128 processors: AMD Opteron&trade; Processor 850
+
** 65536 compute cores: 16 racks of Blue Gene/P, each containing <br> 1024 quad-core, 32-bit 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
 +
 
 +
* [http://www.lrr.in.tum.de/Par/arch/infiniband/ InfiniBand-Cluster] of the Lehrstuhl Rechnertechnik und Rechnerorganisation/<br>Parallelrechnerarchitektur of Technische Universtität München:
 +
** 128 compute cores: AMD Opteron&trade; Processor 850
 
** Architecture: x86_64
 
** Architecture: x86_64
** Compiler version: gcc version 3.3.3 (SuSE Linux)
+
** Compiler version: gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu3)
** Libraries: lapack 3.0, csparse 2.2.0, MPI based on MPICH 1.2.7  
+
** Libraries:  
 +
*** Lapack 3.0  
 +
*** MPI based on MPICH 1.2.7  
 +
*** HYPRE 2.7.0b
  
 
* i686-pc-linux-gnu:
 
* i686-pc-linux-gnu:
** Processor:  
+
** Processor: Intel&reg; Core&trade;2 Duo CPU P8700  @ 2.53GHz
*** Intel&reg; Pentium&reg; D CPU 2.80GHz,
 
*** Intel&reg; Pentium&reg; M CPU 1.60GHz
 
 
** Architecture: i686
 
** Architecture: i686
** Compiler version:  
+
** Compiler version: gcc version 4.3.4 (Gentoo 4.3.4 p1.1, pie-10.1.5)
*** gcc version 4.1.1 (Gentoo 4.1.1-r3), Intel&reg; Compiler icpc version 9.1
 
*** gcc version 4.1.2 (Gentoo 4.1.2 p1.1)
 
 
** Libraries:  
 
** Libraries:  
*** lapack 3.1.1, csparse 2.2.0
+
*** Lapack 3.3.1
*** lapack 3.1, csparse 2.2.0
+
*** HYPRE 2.7.0b
  
  
MSPAI is provided "as is", without warranty and support of any kind, express
+
FSPAI is provided "as is", without warranty and support of any kind, express
 
or <br>implied, including but not limited to the warranties of merchantability,
 
or <br>implied, including but not limited to the warranties of merchantability,
 
fitness for a <br>particular purpose, title and non-infringement. In no event
 
fitness for a <br>particular purpose, title and non-infringement. In no event
shall the copyright holders <br>or anyone distributing MSPAI be liable for any
+
shall the copyright holders <br>or anyone distributing FSPAI be liable for any
 
damages or other liability, whether in contract, tort or otherwise, arising
 
damages or other liability, whether in contract, tort or otherwise, arising
from, out of or in connection with MSPAI or the use <br>or other dealings in MSPAI.
+
from, out of or in connection with FSPAI or the use <br>or other dealings in FSPAI.
-->
 
  
 
== Some References ==
 
== Some References ==
<!--
+
 
 
=== Papers ===  
 
=== Papers ===  
  
<pubsccs>nocaption=1&pubid=1463&lang=en</pubsccs><pubsccs>nocaption=1&pubid=1423&lang=en</pubsccs><pubsccs>nocaption=1&persid=53&utypid=1020&datum=2007&lang=en</pubsccs><pubsccs>nocaption=1&pubid=620&lang=en</pubsccs><pubsccs>nocaption=1&pubid=645&lang=en</pubsccs><pubsccs>nocaption=1&pubid=654&lang=en</pubsccs><pubsccs>nocaption=1&pubid=677&lang=en</pubsccs><pubsccs>nocaption=1&pubid=499&lang=en</pubsccs>  
+
<pubsccs>nocaption=1&pubid=620&lang=en</pubsccs><pubsccs>nocaption=1&pubid=645&lang=en</pubsccs><pubsccs>nocaption=1&pubid=677&lang=en</pubsccs><pubsccs>nocaption=1&persid=53&utypid=2030&datum=2008&lang=en</pubsccs><pubsccs>nocaption=1&pubid=1140&lang=en</pubsccs>
  
=== Theses ===
+
=== Thesis ===
  
<pubsccs>nocaption=1&persid=53&utypid=2030&datum=2008&lang=en</pubsccs><pubsccs>nocaption=1&pubid=1140&lang=en</pubsccs><pubsccs>nocaption=1&lang=en&persid=58&datum=2008&utypid=2040</pubsccs>
+
<pubsccs>nocaption=1&lang=en&pubid=1901</pubsccs>
  
 
=== Further ===
 
=== Further ===
  
* Short summary on SPAI with core reference list: [http://www5.in.tum.de/software/mspai/summary.pdf summary.pdf]  
+
* Short summary on sparse approximate inverses with core reference list: [http://www5.in.tum.de/software/mspai/summary.pdf summary.pdf]  
 
* Extended reference list: [http://www5.in.tum.de/software/mspai/extended.pdf extended.pdf]
 
* Extended reference list: [http://www5.in.tum.de/software/mspai/extended.pdf extended.pdf]
-->
 
<!--
 
== Successful Applications ==
 
=== MSPAI ===
 
 
* see References (Section 1.5), <br> e.g. Smoothing and Regularization with MSPAI
 
 
=== SPAI ===
 
* see References (Section 1.5.3), <br> e.g. Alleon, G., Benzi, M., and Giraud, L.: <b>Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics.</b> <i>Numerical Algorithms</i>, Volume 16(1), p. 1-15 (1997)
 
-->
 
  
 
== Authors ==
 
== Authors ==
Line 123: Line 102:
 
* [http://www5.in.tum.de/wiki/index.php/Univ.-Prof._Dr._Thomas_Huckle Thomas Huckle]  
 
* [http://www5.in.tum.de/wiki/index.php/Univ.-Prof._Dr._Thomas_Huckle Thomas Huckle]  
 
* [http://www5.in.tum.de/wiki/index.php/Matous_Sedlacek Matous Sedlacek]
 
* [http://www5.in.tum.de/wiki/index.php/Matous_Sedlacek Matous Sedlacek]
 
  
 
== License ==  
 
== License ==  
  
 
FSPAI: Factorized Sparse Approximate Inverses<br>
 
FSPAI: Factorized Sparse Approximate Inverses<br>
Copyright &copy; 2010-2011,  Matous Sedlacek<br>
+
Copyright &copy; 2012-2013,  Matous Sedlacek<br>
 
Research Unit Scientific Computing in Computer Science - Informatics V<br>
 
Research Unit Scientific Computing in Computer Science - Informatics V<br>
 
Technische Universität München
 
Technische Universität München
Line 147: Line 125:
 
If you obtain any results with FSPAI we would appreciate that you refer
 
If you obtain any results with FSPAI we would appreciate that you refer
 
to FSPAI.
 
to FSPAI.
 
  
 
== Further work on Sparse Approximate Inverses ==
 
== Further work on Sparse Approximate Inverses ==
  
 
* <b>SPAI</b>: Parallel Implementation on SPAI — Sparse Approximate Inverses:<br>http://www.computational.unibas.ch/software/spai/
 
* <b>SPAI</b>: Parallel Implementation on SPAI — Sparse Approximate Inverses:<br>http://www.computational.unibas.ch/software/spai/
 +
* <b>MSPAI</b>: Parallel implementation of MSPAI — Modified Sparse Approximate Inverses: <br>http://www5.in.tum.de/wiki/index.php/MSPAI
 
* <b>PARASAILS</b>: Parallel Sparse Approximate Inverse (Least-Squares) Preconditioner:<br>https://computation.llnl.gov/casc/parasails/parasails.html
 
* <b>PARASAILS</b>: Parallel Sparse Approximate Inverse (Least-Squares) Preconditioner:<br>https://computation.llnl.gov/casc/parasails/parasails.html
 
* <b>HYPRE</b>: Software on high performance preconditioners containing a PARASAILS module:<br>https://computation.llnl.gov/casc/linear_solvers/sls_hypre.html
 
* <b>HYPRE</b>: Software on high performance preconditioners containing a PARASAILS module:<br>https://computation.llnl.gov/casc/linear_solvers/sls_hypre.html

Latest revision as of 17:05, 28 January 2013

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 ill-conditioned 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.,

Fspai.png

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.

FSPAI 1.0

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 quad-core, 32-bit 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
  • InfiniBand-Cluster 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.4-1ubuntu3)
    • Libraries:
      • Lapack 3.0
      • MPI based on MPICH 1.2.7
      • HYPRE 2.7.0b
  • i686-pc-linux-gnu:
    • Processor: Intel® Core™2 Duo CPU P8700 @ 2.53GHz
    • Architecture: i686
    • Compiler version: gcc version 4.3.4 (Gentoo 4.3.4 p1.1, pie-10.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 non-infringement. 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

404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443
404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443
404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443
404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443
404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443


Thesis

404 Not Found

Not Found

The requested URL was not found on this server.


Apache/2.4.29 (Ubuntu) Server at www5.in.tum.de Port 443


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 © 2012-2013, 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