how does matlab solve large, symmetric and sparse linear systems

Question

That is, when I do A\b for a very large, symmetric and sparse A, what algorithm does matlab use?

Answer 1

The answer depends on the some properties of A (diagonal/square/banded? etc.). CHOLMOD, UMFPACK and qr factorization are some of the options.

The documentation explains it. Here are links to online snapshots of the docs. This may be outdated. - http://amath.colorado.edu/computing/Matlab/OldTechDocs/ref/arithmeticoperators.html - http://www.maths.lth.se/na/courses/NUM115/NUM115-11/backslash.html

Answer 2

If the matrix is sparse and symmetric positive definite, but has a very narrow band, then a specialized band solver is used. Most matrices do not have a narrow enough band to trigger this condition. Typically, this comes up with 1-D splines in the Spline Toolbox. 2-D problems have a large "band" (they are not truly banded matrices).

More typically, MATLAB uses CHOLMOD for sparse symmetric positive definite matrices. If the matrix is sparse, symmetric, and indefinite, then it uses MA49 by Iain Duff.

You can get MATLAB to tell you what it is doing inside A\b with this option:

spparms ('spumoni',3)

then turn it off again with

spparms ('spumoni',0)

For sparse square matrices it uses UMFPACK. For sparse rectangular matrices it uses SuiteSparseQR (or spqr for short).

For sparse matrices that are lower or upper triangular, or can be permuted into such, it uses a forward/back solver that exploits these properties.

MATLAB does not use the simplex method in backslash at all. If the matrix is rectangular (and short and fat, with more columns than rows) the A\b returns a basic solution. If you want a minimum 2-norm solution, you need to factorize A'. That can be done in the spqr MATLAB interface but that option is not available in the MATLAB distribution. You would need to install spqr from the source code at suitesparse.com.