Sparse data math info

Two weeks ago, I posted about Matlab’s math libraries and their various versions across Matlab releases. Matlab relies on the proprietary Intel MKL and AMD ACML libraries for most of its core math, matrix manipulation and linear algebra functions, for Intel/AMD CPUs (respectively). MKL and ACML are adaptations of, and wrappers for, the ubiquitous BLAS and LAPACK packages (LAPACK uses BLAS for its low-level functionality).

Introducing SuiteSparse

Unfortunately, BLAS can be used only with full (non-sparse) matrix data on a CPU. So, for GPU support Matlab uses MAGMA (libmwmagma.dll). Similarly, for sparse data Matlab uses the SuiteSparse library by University of Florida’s Tim Davis, whose work on sparse matrix software has very recently earned him SIAM fellowship. SuiteSparse is used by Google Earth and Street-View to create their amazing real-time 3D renditions.
SuiteSparse relies on sparse-data algorithms that have been developed over many years (since the 70’s elsewhere, since 1991 at UFL), and continuously evolve to this day. A presentation about the algorithms in 2006 is available: video, slides (FEX #12295). A detailed presentation of some of the algorithms can be found in Tim’s book “Direct Methods for Sparse Linear Systems” (SIAM, 2006), which should not be confused with Tim’s other book, the widely-popular “Matlab Primer“. A more recent technical description of the sparse algorithms is provided in an ACM paper.

SuiteSparse in Matlab

SuiteSparse has been incorporated into Matlab’s core functionality over the span of several years, between 2000 and 2009 (details). The functions were apparently incorporated into libmwmathlinalg.dll, libmwmathcore.dll, libcolamd.dll, libmwspmatrix.dll, libmwumfpack.dll, libmwumfpack_api.dll, libmwcholmod.dll, libmwamd.dll, libmwspqr.dll, libmwma57.dll, libmwcsparse.dll, libmwspqr.dll (and possibly a couple of other DLLs I missed). On *nix systems, the libraries have the same name, with an *.so extension (e.g., libmwcsparse.so). All these dynamic libraries are located in the /bin/%arch%/ folder of the Matlab installation, alongside the rest of Matlab’s libs. The lib names are pretty self-explanatory, for example libmwspqr.dll contains the SuiteSparse QR library; libmwcsparse.dll contains the CSparse library (which is described in the above-mentioned SIAM book).
Back in 2007, SuiteSparse could be used in Matlab as a separate package on the File Exchange (#12233), which was discussed on Loren’s blog. Since Matlab has incorporated SuiteSparse into its core functions, FEX #12233 is no longer available. We can still download the sources directly from the SuiteSparse page on UFL.

Sparse libs version info in Matlab

Unlike BLAS, LAPACK, FFTW and MKL, there is no known way to directly extract the sparse-libs version info in Matlab. But there is an indirect way to do so, and in the process, we discover lots of interesting information about the internal mechanisms of the sparse algos.
We begin by setting the debugging information to maximum using the spparms function. This not only provides version info, but also all kinds of diagnostics about the sparse matrices and the selected algorithm path. For example (note the highlighted version info text):

>> spparms('spumoni',2)
>> load west0479
>> b = rand(size(west0479,1));
>> x = west0479 \ b;
sp\: bandwidth = 388+1+337.
sp\: is A diagonal? no.
sp\: is band density (0.01) > bandden (0.50) to try banded solver? no.
sp\: is A triangular? no.
sp\: is A morally triangular? no.
sp\: is A a candidate for Cholesky (symmetric, real positive diagonal)? no.
sp\: use Unsymmetric MultiFrontal PACKage with automatic reordering.
UMFPACK V5.4.0 (May 20, 2009), Control:    Matrix entry defined as: double
    Int (generic integer) defined as: UF_long
    BLAS library used: Fortran BLAS.  size of BLAS integer: 8
    MATLAB:                           yes.
    CPU timer:                        ANSI clock ( ) routine.
    number of rows in matrix A:       479
    number of columns in matrix A:    479
    entries in matrix A:              1887
    memory usage reported in:         16-byte Units
    size of int:                      4 bytes
    size of UF_long:                  8 bytes
    size of pointer:                  8 bytes
    size of numerical entry:          8 bytes
    strategy used:                    unsymmetric
    ordering used:                    colamd on A
    modify Q during factorization:    yes
    prefer diagonal pivoting:         no
    pivots with zero Markowitz cost:               133
    ...  % lots of other interesting internal information

A Matlab script to extract the sparse libs’ version info is provided here. The script runs a few sparse math operations that more-or-less cover the sparse libs, and then reports the version data when it’s done. In order to parse the debugging info, the script uses either an external OS grep command (which is available on Linux & Macs), or a Matlab equivalent. Here are the results on my R2013a system:

>> sparse_lib_versions
...  % numerous debugging info...
=> sparse matrix library versions (from C:\Users\Yair\AppData\Local\Temp\sparse_info.txt):
============================================================
AMD version 2.2.0, May 31, 2007: approximate minimum degree ordering
AMD version 2.2.0, May 31, 2007, results:
colamd version 2.5, May 5, 2006: OK.
CHOLMOD version 1.7.0, Sept 20, 2008:  : status: OK
CHOLMOD version 1.7.0, Sept 20, 2008: : status: OK
SuiteSparseQR, version 1.1.0 (Sept 20, 2008)
UMFPACK V5.4.0 (May 20, 2009), Control:
UMFPACK V5.4.0 (May 20, 2009), Info:

It looks like MathWorks haven’t updated Matlab’s sparse libs in quite a few years. These libraries continue to be improved continuously, but most of the tweaks are quite minor and no important bugs were found for many years, so I guess that we can’t really complain.

Austria & Switzerland visit

I will be visiting clients in Austria and Switzerland in August. If you live in the area, I will be happy to meet you to discuss how I could bring value to your needs, as consultant, contractor or trainer. Please email me if you think that this could be relevant for you. The relevant dates are:

• Vienna – Aug 18, 25-26
• Salzburg – Aug 19-23
• Zurich – Aug 26-29

Bis bald!