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