Summary of available software for sparse direct methods

Timothy A. Davis

April 5, 2012

Click here for a PDF version of this document

Click here for a postscript version of this document

Table 1 summarizes most of the available software for solving sparse linear systems via direct methods as March 2009. The first column lists the name of the package. The next four columns describe what kinds of factorizations are available: LU, Cholesky, $LDL^T$ for symmetric indefinite matrices, and QR. If the $LDL^T$ factorization uses 2-by-2 block pivoting a ``2'' is listed; a ``1'' is listed otherwise [10,11]. The next column states if complex matrices (unsymmetric, symmetric, and/or Hermitian) are supported. The ordering methods available are listed in the next four columns: minimum degree and its variants (minimum fill, column minimum degree, Markowitz, and related methods), nested or one-way dissection (including all graph-based partitionings), permutation to block triangular form, and profile/bandwidth reduction (or related) methods. The next three columns indicate what level of BLAS is used (1: vector, 2: matrix-vector, 3: matrix-matrix), if the package is parallel (``s'' for shared-memory or ``d'' for distributed-memory), and whether or not the package includes an out-of-core option (where most of the factors remain on disk). Most distributed-memory packages can also be used in a shared-memory environment, since most message-passing libraries (MPI in particular) are ported to shared-memory environments. A code is listed as ``sd'' if it includes two versions, one for shared-memory and the other for distributed-memory. The next column indicates if a MATLAB interface is available. The primary method(s) used in the package are listed in the final column. Table 2 lists the authors of the packages, relevant papers, and where to get the code. An up-to-date table will be maintained at www.cise.ufl.edu/research/sparse/codes.


Table 1: Package features
package LU Cholesky $LDL^T$ QR complex Minimum degree Nested dissection Block triangular Profile BLAS Parallel out-of-core MATLAB method
SuiteSparseQR - - - X X X X - - 3 s - X multifrontal
BCSLIB-EXT X X 2 X X X X - - 3 s X - multifrontal
CHOLMOD - X 1 - X X X - - 3 - - X left-looking supernodal
CSparse X X - X X X - X - - - - X various
DSCPACK - X 1 - - X X - - 3 d - - multifrontal w/ selected inversion
GPLU X - - - X - - - - - - - X left-looking
KLU X - - - X X - X - - - - X left-looking
LDL - X 1 - - - - - - - - - X up-looking
MA27 - X 2 - X X - - - - - - - multifrontal
MA28 X - - - X X - X - - - - - right-looking Markowitz
MA32 X - - - X - - - X 1 - X - frontal
MA37 X - - - X X - - - - - - - multifrontal
MA38 X - - - X X - X - 3 - - - unsymmetric multifrontal
MA41 X - - - X X - - - 3 s - - multifrontal
MA42 X - - - X - - - X 3 - X - frontal
HSL_MP42 X - - - - - X - X 3 d X - frontal
MA46 X - - - - - - - - 3 - - - finite-element multifrontal
MA47 - X 2 - X X - - - 3 - - - multifrontal
MA48 X - - - X X - X - 3 - - X left-looking
HSL_MP48 X - - - - X - X - 3 d X - left-looking
MA49 - - - X - X - X - 3 s - - multifrontal
MA57 - X 2 - X X X - - 3 - - X multifrontal
MA62 - X - - X - - - X 3 - X - frontal
HSL_MP62 - X - - - - X - X 3 d X - frontal
MA67 - X 2 - - X - - - 3 - - - right-looking Markowitz
Mathematica X X - - X X X X - 3 - - - various
MATLAB X X - X X X - X X 3 - - X various
Meschach X X 2 - - X - - - - - - - right-looking
MUMPS X X 2 - X X X - - 3 d - X multifrontal
NSPIV X - - - - - - - - - - - - up-looking
Oblio - X 2 - X X X - - 3 - X - left, right, multifrontal
PARDISO X X 2 - X X X - - 3 s - X left/right supernodal
PaStiX X X 1 - X X X - - 3 d - - left-looking supernodal
PSPASES - X - - - - X - - 3 d - - multifrontal
RF X - - - - - - - X - - - - product form of inverse
S+ X - - - - - - - - 3 d - - right-looking supernodal
Sparse 1.4 X - - - X X - - - - - - - right-looking Markowitz
SPARSPAK X X - X - X X - X - - - - left-looking
SPRSBLKLLT - X - - - X - - - 3 - - - left-looking supernodal
SPOOLES X X 2 X X X X - - - sd - - left-looking, multifrontal
SuperLU X - - - X X - - - 2 - - X left-looking supernodal
SuperLU_MT X - - - - X - - - 2 s - - left-looking supernodal
SuperLU_DIST X - - - X X - - - 3 d - - right-looking supernodal
TAUCS X X 1 - X X X - - 3 s X - left-looking, multifrontal
UMFPACK X - - - X X - - - 3 - - X multifrontal
WSMP X X 1 - X X X X - 3 sd - - multifrontal
Y12M X - - - - X - - - - - - - right-looking Markowitz
Clique - - 1 - X - - - - 3 d - - multifrontal w/ selected inversion


Table 2: Package authors, references, and availability
package Authors, references URL and/or contact
BCSLIB-EXT Ashcraft, Grimes, Lewis, www.boeing.com
and Pierce [6,8,9,46] phantom/bcslib-ext
CHOLMOD Davis, Hager, Chen, and www.cise.ufl.edu/research/sparse
Rajamanickam [15]
CSparse Davis www.cise.ufl.edu/research/sparse
DSCPACK Heath and Raghavan [40,41,48] www.cse.psu.edu/$\sim$raghavan
GPLU Gilbert and Peierls [37] www.mathworks.com
KLU Davis and Palamadai www.cise.ufl.edu/research/sparse
LDL Davis [14] www.cise.ufl.edu/research/sparse
MA27 Duff and Reid [25] www.cse.clrc.ac.uk/nag/hsl
MA28 Duff and Reid [24] www.cse.clrc.ac.uk/nag/hsl
MA32 Duff [21] www.cse.clrc.ac.uk/nag/hsl
MA37 Duff and Reid [26] www.cse.clrc.ac.uk/nag/hsl
MA38 Davis and Duff [16] www.cse.clrc.ac.uk/nag/hsl
MA41 Amestoy and Duff [1] www.cse.clrc.ac.uk/nag/hsl
MA42 Duff and Scott [30] www.cse.clrc.ac.uk/nag/hsl
HSL_MP42 Scott [52,53,54] www.cse.clrc.ac.uk/nag/hsl
MA46 Damhaug and Reid [12] www.cse.clrc.ac.uk/nag/hsl
MA47 Duff and Reid [27] www.cse.clrc.ac.uk/nag/hsl
MA48 Duff and Reid [28] www.cse.clrc.ac.uk/nag/hsl
HSL_MP48 Duff and Scott [32] www.cse.clrc.ac.uk/nag/hsl
MA49 Amestoy, Duff and Puglisi [4] www.cse.clrc.ac.uk/nag/hsl
MA57 Duff [22,29] www.cse.clrc.ac.uk/nag/hsl
MA62 Duff and Scott [31] www.cse.clrc.ac.uk/nag/hsl
HSL_MP62 Scott [54] www.cse.clrc.ac.uk/nag/hsl
MA67 Reid [23] www.cse.clrc.ac.uk/nag/hsl
Mathematica Wolfram Research, Inc. [57] www.wolfram.com
MATLAB The MathWorks, Inc. [36] www.mathworks.com
Meschach Steward and Leyk www.netlib.org/c/meschach
MUMPS Amestoy, Duff , Guermouche, www.enseeiht.fr/apo/MUMPS
Koster, L'Excellent, Pralet [2,3,5] graal.ens-lyon.fr/MUMPS
NSPIV Sherman [56] www.netlib.org/toms/533
Oblio Dobrian, Kumfert, and email pothen@cs.odu.edu
Pothen [20]
PARDISO Schenk, Gärtner, and Fichtner www.computational.unibas.ch/
[50,51] cs/scicomp/software/pardiso
PaStiX Hénon, Ramet, and Roman [42] www.labri.fr/$\sim$ramet/pastix
PSPASES Joshi, Karypis, Kumar, Gupta, www.cs.umn.edu/$\sim$mjoshi/pspases
and Gustavson [39]
RF Neculai www.ici.ro/camo/neculai/RF
S+ Fu, Jiao, and Yang [33,55] www.cs.ucsb.edu/projects/s+
Sparse 1.4 Kundert [43] sparse.sourceforge.net
SPARSPAK George and Liu [34,35] www.cs.uwaterloo.ca/$\sim$jageorge
SPOOLES Ashcraft and Grimes [7] www.netlib.org/linalg/spooles
SPRSBLKLLT Ng and Peyton [45] email EGNg@lbl.gov
SuperLU Demmel, Eisenstat, Gilbert crd.lbl.gov/$\sim$xiaoye/SuperLU
and Li [18]
SuperLU_MT Demmel, Gilbert, and Li [19] crd.lbl.gov/$\sim$xiaoye/SuperLU
SuperLU_DIST Demmel and Li [44] crd.lbl.gov/$\sim$xiaoye/SuperLU
TAUCS Chen, Rotkin, and Toledo [49] www.tau.ac.il/$\sim$stoledo/taucs
UMFPACK Davis and Duff [13,16,17] www.cise.ufl.edu/research/sparse
WSMP Gupta [38,39] www.cs.umn.edu/$\sim$agupta/wsmp
Y12M Zlatev, Wasniewski, and www.netlib.org/y12m
Schaumburg [58]
Clique Poulson [47] www.ices.utexas.edu/$\sim$poulson

Updates to this document are welcome.

Tim Davis, http://www.cise.ufl.edu/$\sim$davis



Tim Davis 2012-04-05