Difference between revisions of "FSPAI"

From Sccswiki
Jump to navigation Jump to search
(Created page with 'test test')
 
Line 1: Line 1:
test test
+
= <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>
 +
 
 +
 
 +
We developed a highly scalable sequential and parallel implementation of the
 +
known ''FSPAI (Factorized SParse Approximate Inverses)'' algorithm.
 +
 
 +
 
 +
== Theory ==
 +
<!--
 +
 
 +
MSPAI is a preconditioner for large sparse and ill-conditioned systems of <br> linear equations. We extended the basic SPAI minimization
 +
 
 +
: [[Image:spai.jpg]]
 +
 
 +
to target form and further generalized it in order to add additional ''probing constraints'':
 +
 
 +
: [[Image:mspai.jpg]]
 +
 
 +
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 ==
 +
<!--
 +
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 ===
 +
* 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 ===
 +
* 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.2 ===
 +
 
 +
* Source code tar ball: [http://www5.in.tum.de/software/mspai/mspai-1.2.tar.gz mspai-1.2.tar.gz].
 +
* 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 and HTML documentation: [http://www5.in.tum.de/software/mspai/mspai-1.2-html.tar.gz mspai-1.2-html.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 ==
 +
<!--
 +
* [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:
 +
** 128 processors: AMD Opteron&trade; 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&reg; Pentium&reg; D CPU 2.80GHz,
 +
*** Intel&reg; Pentium&reg; M CPU 1.60GHz
 +
** Architecture: i686
 +
** Compiler version:
 +
*** 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:
 +
*** 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 <br>implied, including but not limited to the warranties of merchantability,
 +
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
 +
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.
 +
-->
 +
 
 +
== Some References ==
 +
<!--
 +
=== 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>
 +
 
 +
=== Theses ===
 +
 
 +
<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>
 +
 
 +
=== Further ===
 +
 
 +
* Short summary on SPAI 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]
 +
-->
 +
<!--
 +
== 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 ==
 +
 
 +
* [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]
 +
 
 +
 
 +
== License ==
 +
 
 +
FSPAI: Factorized Sparse Approximate Inverses<br>
 +
Copyright &copy; 2010-2011,  Matous Sedlacek<br>
 +
Research Unit Scientific Computing in Computer Science - Informatics V<br>
 +
Technische Universität München
 +
 
 +
This program is free software: you can redistribute it and/or modify
 +
it under the <br>terms of the GNU Lesser General Public License as published by
 +
the Free Software <br>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 <br> WARRANTY; without even the implied warranty of
 +
MERCHANTABILITY or FITNESS FOR<br> 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 <br>this program. If not, see [http://www.gnu.org/licenses/ 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 ==
 +
 
 +
* <b>SPAI</b>: Parallel Implementation on SPAI — Sparse Approximate Inverses:<br>http://www.computational.unibas.ch/software/spai/
 +
* <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

Revision as of 15:46, 11 July 2011

Factorized Sparse Approximate Inverses

This is a dummy textLatest release is 1.0


We developed a highly scalable sequential and parallel implementation of the known FSPAI (Factorized SParse Approximate Inverses) algorithm.


Theory

Implementation and Features

Download

Some Theses on MSPAI

Tested environments

Some References

Authors


License

FSPAI: Factorized Sparse Approximate Inverses
Copyright © 2010-2011, 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