# Difference between revisions of "FSPAI"

(Created page with 'test test') |
|||

Line 1: | Line 1: | ||

− | + | = <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™ 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 <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 © 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

## Contents

__Factorized Sparse Approximate Inverses__

- This is a dummy text
**Latest 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

**SPAI**: Parallel Implementation on SPAI — Sparse Approximate Inverses:

http://www.computational.unibas.ch/software/spai/**PARASAILS**: Parallel Sparse Approximate Inverse (Least-Squares) 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