Timothy A. Davis
Abstract
An ANSI C code for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The pre-ordering and symbolic analysis phase computes an upper bound on fill-in, work, and memory usage during the subsequent numerical factorization. User-callable routines are provided for ordering and analyzing a sparse matrix, computing the numerical factorization, solving a system with the LU factors, transposing and permuting a sparse matrix, and converting between sparse matrix representations. The simple user interface shields the user from the details of the complex sparse factorization data structures by returning simple handles to opaque objects. Additional user-callable routines are provided for printing and extracting the contents of these opaque objects. An even simpler way to use the package is through its MATLAB interface. UMFPACK is incorporated as a built-in operator in MATLAB 6.5 as x = A\b when A is sparse and unsymmetric.
Supplemental Material
Available for Download
Software for "UMFPACK V4.3---an unsymmetric-pattern multifrontal method"
- Davis, T. A. 2004. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2. Google Scholar
Index Terms
- Algorithm 832: UMFPACK V4.3---an unsymmetric-pattern multifrontal method
Recommendations
Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm
Two codes are discussed, COLAMD and SYMAMD, that compute approximate minimum degree orderings for sparse matrices in two contexts: (1) sparse partial pivoting, which requires a sparsity preserving column pre-ordering prior to numerical factorization, ...
Algorithm 837: AMD, an approximate minimum degree ordering algorithm
AMD is a set of routines that implements the approximate minimum degree ordering algorithm to permute sparse matrices prior to numerical factorization. There are versions written in both C and Fortran 77. A MATLAB interface is included.
Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate
CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, ...
Reviews
Lawrence Shampine
UMFPACK is a package for the direct solution of a system of linear equations Ax = b with a matrix A that is sparse and unsymmetric. It is practical to solve very large systems of equations only when the matrix has a special structure. Commonly, a very large matrix is sparse, meaning that most of its entries are zero. By storing only the indices and values of non-zero entries, the storage required to hold A can be reduced greatly. This is a natural way to describe a sparse matrix, but there are more economical ways, so one of the programs in UMFPACK converts from this natural description to one that uses less storage and is convenient for numerical solution of the system. Iterative methods compete with the direct solution of sparse systems by a variant of Gaussian elimination, but the most efficient iterative methods require A to be symmetric. A critical issue in solving sparse linear systems by elimination is "fill-in," the creation of non-zero entries in the matrix. In selecting which variable to eliminate, it is necessary to consider numerical stability as well as fill-in. In addition to deciding which variable to eliminate, it is possible to improve the process by reordering the variables. Davis explains how this is done in UMFPACK in a previous paper [1]. The programs of UMFPACK are written in C, but there is a MATLAB interface that simplifies solving a sparse system of linear equations. Indeed, the built-in function for this task in MATLAB was replaced by UMFPACK at version 6.5 because UMFPACK was generally faster, used less memory, and returned sparser LU factors. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments