UMFPACK: unsymmetric multifrontal sparse LU factorization package

UMFPACK is a set of routines for solving unsymmetric sparse linear systems, Ax=b, using the Unsymmetric MultiFrontal method. Written in ANSI/ISO C, with a MATLAB (Version 6.0 and later) interface. Appears as a built-in routine (for lu, backslash, and forward slash) in MATLAB. Includes a MATLAB interface, a C-callable interface, and a Fortran-callable interface. Note that "UMFPACK" is pronounced in two syllables, "Umph Pack". It is not "You Em Ef Pack".

Copyright, and License:

Copyright (c) 1994-2011 by Timothy A. Davis, University of Florida. All Rights Reserved. Distributed under the GNU GPL license.

Availability:

• Download the current version of UMFPACK here
• Browse the source code
• read the change log
• Requires the SuiteSparse_config package.
• Requires the AMD package.
• Get all of SuiteSparse here.

The BLAS: Basic Linear Algebra Subprograms

UMFPACK has installation options to use the many versions of the BLAS, or no BLAS at all. The BLAS is what UMFPACK relies on to get high performance on a wide range of computers. If at all possible, use the BLAS. If your BLAS uses 64-bit integers, compile with -DBLAS64. You can also edit the SuiteSparse_config.mk file as needed to include this definition.
• 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 for the nCUBE.

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.
• See Evgenni Rudnyi's page on Compiling UMFPACK for help on compiling UMFPACK for Unix/Linux and Windows.

Versions:

• UMFPACK-5.6.2.tar.gz (current version)
• UMFPACK-5.6.1.tar.gz
• UMFPACK-5.6.0.tar.gz
• UMFPACK-5.5.2.tar.gz
• UMFPACK-5.5.1.tar.gz
• UMFPACK-5.5.0.tar.gz
• UMFPACK-5.4.0.tar.gz
• UMFPACK-5.3.0.tar.gz
• UMFPACK-5.2.0.tar.gz
• UMFPACK-5.1.0.tar.gz
• UMFPACK-5.0.3.tar.gz
• UMFPACK-5.0.2.tar.gz
• UMFPACK-5.0.1.tar.gz
• UMFPACK-5.0.0.tar.gz
• UMFPACK-4.6.0.tar.gz
• UMFPACK-4.4.0.tar.gz
• UMFPACK-3.2.0.tar.gz
• MA38 (version 2.2.1) in HSL

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.