UMFPACK: unsymmetric multifrontal sparse LU factorization package

Tim Davis, Prof.
Room E338 CSE Building
P.O. Box 116120
University of Florida
Gainesville, FL 32611-6120
352/392-1481
email: my last name AT cise.ufl.edu

back to Tim Davis' home page

other sparse matrix research

UF sparse matrix collection: submissions always welcome.

UMFPACK:

MATLAB

NOTE: UMFPACK 3.2 through 5.1 is available under a GNU LGPL license. UMFPACK 5.2 (and future versions) are available under the GNU GPL license. For a non-GNU license, please contact Tim Davis.

NOTE: The gcc compiler versions 4.2.3 and 4.2.4 on 64-bit Linux systems have a bug (when any optimization is enabled) that causes UMFPACK to fail. The bug is fixed in gcc 4.3.2, so either use an old gcc compiler, or 4.3.2 or later. The error occurs in umf_singletons which incorrectly concludes that a nonsymmetric permutation is symmetric. In a future release, I'll try to change UMFPACK to a work around this gcc bug (and thanks to Pat Quillen for tracking this down!).

Copyright, and License:

Availability:

The BLAS: Basic Linear Algebra Subprograms

BLAS: basic linear algebra subprograms. This is the standard reference BLAS. You should use optimized BLAS whenever possible. Used by CHOLMOD and UMFPACK.
Goto BLAS: typically the fastest BLAS available. Highly recommended for CHOLMOD and UMFPACK.

Contributors:

Iain Duff (Rutherford Appleton Lab, UK): co-developed the algorithm, and the AMD ordering.
Patrick Amestoy (ENSEEIHT, Toulouse, France): co-developed AMD.
Stefan Larimore (now at Microsoft): co-developed the COLAMD ordering.
John Gilbert (UC Santa Barbara) co-developed the COLAMD ordering, while he was at Xerox PARC.
Esmond Ng (Lawrence Berkeley National Lab): co-developed the COLAMD ordering.
Steve Hadfield (US Air Force Academy): wrote a parallel version of UMFPACK.

Contributions, and related codes:

AMD is the default preordering used in MA41, by Patrick Amestoy, Iain Duff, and Chiara Puglisi.
COLAMD is the default preordering used in SuperLU, by Sherry Li (Lawrence Berkeley National Lab).
Anshul Gupta (IBM) has a sparse matrix algorithm (WSMP) and code based on the method used in UMFPACK, related to Steve Hadfield's parallel version. It has a different pre-processing step, based on the DAG instead of the column elimination tree.
Michael Janeschitz-Kriegl has a Fortran-90 interface.

Versions:

Windows Version:

UMFPACK at MATLAB Central (a zip file)

References (please cite these when using this software):

A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, T. A. Davis, ACM Transactions on Mathematical Software, vol 30, no. 2, June 2004, pp. 165-195.
Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method, T. A. Davis, ACM Transactions on Mathematical Software, vol 30, no. 2, June 2004, pp. 196-199.
A combined unifrontal/multifrontal method for unsymmetric sparse matrices, T. A. Davis and I. S. Duff, ACM Transactions on Mathematical Software, vol. 25, no. 1, pp. 1-19, March 1999.
An unsymmetric-pattern multifrontal method for sparse LU factorization, T. A. Davis and I. S. Duff, SIAM Journal on Matrix Analysis and Applications, vol 18, no. 1, pp. 140-158, Jan. 1997.