Scientific Computing FAQ: Sparse Linear Algebra Systems

Sparse Linear Algebra Systems

Netlib (see Netlib ) has a number of libraries for handling sparse systems. See the netlib directories: sparse, sparse-blas, sparsepak.

National HPCC Software Exchange Catalog

Victor Eijkhout's Overview of Iterative Linear System Solver Packages. Gives an overview of available iterative solver packages, with basic information (status, C or Fortran), and details such issues as data structures and parallelism."

The Templates Book Online and well-recommended book on iterative methods for large sparse nonsymmetric systems of linear equations. SIAM has published it as "Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods" By Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, and Henk Van der Vorst.

SPARSKIT is a linear algebra system for sparse matrices.

PSPASES PSPASES: A Scalable Parallel Direct Solver for Sparse Symmetric Positive Definite Systems is a stand-alone MPI-based parallel library for solving linear systems of equations involving sparse symmetric positive definite matrices. The library efficiently implements the scalable parallel algorithms developed by authors, for each of the four phases of direct solution method; viz. ordering, symbolic factorization, numerical Cholesky factorization, and solution of triangular systems.

AZTEC: A Parallel Iterative Package for Linear Systems, Aztec is an iterative library that greatly simplifies the parallelization process when solving the linear systems of equations Ax = b where A is a user supplied nxn sparse matrix, b is a user supplied vector of length n and x is a vector of length n to be computed. Aztec is intended as a software tool for users who want to avoid cumbersome parallel programming details but who have large sparse linear systems which require an efficiently utilized parallel processing system. A collection of data transformation tools are provided that allow for easy creation of distributed sparse unstructured matrices for parallel solution. Once the distributed matrix is created, computation can be performed on any of the parallel machines running Aztec: workstation clusters (DEC, SGI, SUN, LINUX, etc.), Cray T3E, Intel TeraFlop, Intel Paragon, IBM SP2, nCUBE 2 as well as other MPI platforms, vector machines or serial machines.

Aztec includes a number of Krylov iterative methods such as conjugate gradient (CG), generalized minimum residual (GMRES) and stabilized biconjugate gradient (BiCGSTAB) to solve systems of equations. These Krylov methods are used in conjunction with various preconditioners such as polynomial or domain decomposition methods using LU or incomplete LU factorizations within subdomains. Although the matrix A can be general, the package has been designed for matrices arising from the approximation of partial differential equations (PDEs).

S+ provides sparse LU factorization with partial pivoting is important for many scientific applications and delivering high performance for this problem is difficult on distributed memory machines. This project studies the properties of elimination forests and uses them to guide supernode partitioning/amalgamation and execution scheduling. This design with 2D mapping effectively identifies dense structures without introducing too many zeros in the BLAS computation and exploits asynchronous parallelism with low buffer space cost. The implementation of this code, called S+, uses supernodal matrix multiplication which retains the BLAS-3 level efficiency and avoids unnecessary arithmetic operations. This project also studies two space optimization techniques which can greatly improve the worst-case performance of static symbolic factorization.The experiments show that S+ can achieve up to 10.85GFLOPS on 128 Cray T3E 450MHz nodes, which is the highest performance reported in the literature.

WSMP, the Watson Sparse Matrix Package, (WSMP Part 1, WSMP Part 2) is a robust, high-performance, easy- to-use serial and parallel software for the direct solution of general and symmetric sparse linear systems on IBM RS6000 and SP platforms.

UMFPACK 4.1 is a package for sparse LU factorization. It includes an interface to AMD v1.0. It is much faster than v4.0 (which appears as x=A\b in MATLAB 6.5), particularly for unsymmetric matrices with symmetric nonzero pattern. It is written in C, and includes a MATLAB and Fortran interface. It can handle real or complex matrices.

AMD v1.0 is also available as a stand-alone package, for ordering sparse matrices prior to Cholesky factorization (or LU factorization with diagonal pivoting). It has versions in both C and Fortran, with a MATLAB interface. In MATLAB, p = amd (A) is much faster than p = symamd (A). AMD is co-authored with Patrick Amestoy and Iain Duff.

MTJ Matrix Toolkits for Java (MTJ) is a comprehensive collection of matrix datastructures, linear solvers (direct and iterative), least squares methods, eigenvalue- and singular value decompositions.

Mondriaan is a sparse matrix partitioning package. It is a two-dimensional, multilevel, hypergraph-based package for the partitioning of a rectangular sparse matrix, as a sequential preprocessing step for parallel sparse matrix-vector multiplication. It is written in C. It is distributed under the GNU license.

EigTool combines the Pseudospectra GUI with MATLAB's eigs command to provide visualisation of the Arnoldi iteration during an eigs computation. It includes all of the existing features of the Pseudospectra GUI along with several new ones, notably norms of matrix powers and exponentials and a collection of over 30 demos.