Difference between revisions of "FSPAI"

From Sccswiki
Jump to navigation Jump to search
 
(15 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  
 
We developed a sequential and highly scalable parallel C/C++ implementation  
of the <br> known ''FSPAI (Factorized SParse Approximate Inverses)'' algorithm.
+
of the <br> known ''FSPAI (Factorized SParse Approximate Inverses)'' algorithm.  
  
 +
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.
  
 
== Theory ==
 
== Theory ==
Line 11: Line 11:
 
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.,
 
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
 
 
Based on an initial chosen sparsity structure, FSPAI automatically updates its <br> sparsity structure and improves an a current approximation.
 
  
 +
Based on an initial chosen sparsity structure, FSPAI automatically updates its <br> sparsity structure and improves on a current approximation.
  
== Implementation and Features ==
+
== Features ==
  
 
* Single source providing  
 
* Single source providing  
Line 22: Line 21:
 
** sequential (MPI free) implementation
 
** sequential (MPI free) implementation
 
* Support for real and complex valued problems
 
* Support for real and complex valued problems
* PCG solver available using HYPRE package
+
* 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++
 
* Written in C/C++
  
Line 28: Line 30:
  
 
== Download ==
 
== Download ==
 +
 +
=== FSPAI 1.1 ===
 +
 +
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>
 +
If you are not going to use the Fspai Caching/Hashing or the
 +
sparse methods, <br> you can use FSPAI 1.0 instead.
 +
 +
* 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].
 +
* 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]
  
 
=== FSPAI 1.0 ===
 
=== FSPAI 1.0 ===
Line 33: Line 45:
 
* Source code tar ball: [http://www5.in.tum.de/software/fspai/fspai-1.0.tar.gz fspai-1.0.tar.gz].
 
* Source code tar ball: [http://www5.in.tum.de/software/fspai/fspai-1.0.tar.gz fspai-1.0.tar.gz].
 
* Manual: [http://www5.in.tum.de/software/fspai/fspai-1.0.pdf fspai-1.0.pdf].
 
* 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]
* HTML documentation of source code: [http://www5.in.tum.de/software/fspai/htmlonly-fspai-1.0.tar.gz htmlonly-fspai-1.0.tar.gz].
 
* Source code and HTML documentation: [http://www5.in.tum.de/software/fspai/fspai-1.0-html.tar.gz fspai-1.0-html.tar.gz].
 
 
 
  
 
== Tested environments ==
 
== Tested environments ==
Line 49: Line 58:
 
*** HYPRE 2.7
 
*** HYPRE 2.7
  
* [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.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
 
** 128 compute cores: AMD Opteron&trade; Processor 850
 
** Architecture: x86_64
 
** Architecture: x86_64
Line 73: Line 82:
 
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 FSPAI or the use <br>or other dealings in FSPAI.
 
from, out of or in connection with FSPAI or the use <br>or other dealings in FSPAI.
 
  
 
== Some References ==
 
== Some References ==
Line 80: Line 88:
  
 
<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>
 
<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>
 +
 +
=== Thesis ===
 +
 +
<pubsccs>nocaption=1&lang=en&pubid=1901</pubsccs>
  
 
=== Further ===
 
=== Further ===
Line 85: Line 97:
 
* Short summary on sparse approximate inverses 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 100: 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 124: 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 ==

Latest revision as of 16: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