SSMULT: multiply two MATLAB sparse matrices

Tim Davis, Prof.
Room E338 CSE Building
P.O. Box 116120
University of Florida
Gainesville, FL 32611-6120
352/392-1481
email: my last name AT cise.ufl.edu

back to Tim Davis' home page

other sparse matrix research

UF sparse matrix collection: submissions always welcome.

Description:

SSMULT is a simple stand-alone MATLAB mexFunction that computes C=A*B where both A and B are sparse. It is typically faster and always uses less memory than C=A*B in MATLAB 7.4 (or earlier). Works on MATLAB 6.1 to the current version. Untested on earlier versions of MATLAB.

Copyright, and License:

Availability:

Versions:

SSMULT-1.1.0.tar.gz (current version)
SSMULT-1.0.0.tar.gz

Performance:

You can run the tests shown below on your own computer, using sstest.m. In the plots below, speedup is the time for MATLAB C=A*B divided by the time for C=ssmult(A,B). The X-axis is n, the dimension of the square matrices A and B. A is a sparse random matrix with 1% nonzero values. Yes, I am fully aware that random sparse matrices are unreliable performance indicators; they are just easier to include in a test, so as not to require the user to download 8GB of real sparse matrices; see below for non-random tests (sstest2.m). B is diagonal in the first row of plots, a permutation in the 2nd row, and tridiagonal in the third. C=A*B is in blue, C=B*A is in red. A and B are both real in the first column of plots, B is complex in the 2nd, A in the 3rd, and both are complex in the 4th column of plots.

The first three plots are on the same machine, just different compilers and OS's.

Intel Core Duo, Windows XP, MATLAB 7.4, Microsoft Visual C++ 2005 Express Edition

Intel Core Duo, Windows XP, MATLAB 7.4, lcc compiler

You can see why I recommend not using the lcc compiler that comes with MATLAB.

Intel Core Duo, SUSE Linux, MATLAB 7.4, gcc -O3 (version 4.1.0)

AMD Opteron, SUSE Linux, MATLAB 7.3, gcc -O3 (version 4.1.10)

Intel Pentium 4M, SUSE Linux, MATLAB 7.3, gcc -O3 (version 4.1.10)

AMD Opteron, SUSE Linux, MATLAB 7.3, gcc -O3 (version 4.1.10)

In the following plots, the results of sstest2.m are shown. That test computes A*B for all matrices in the UF Sparse Matrix Collection, on an AMD Opteron, where B=A'. This test was done four times, where A and B were made complex by adding an imaginary part with the same nonzero pattern as the real part. The time to compute B=A' was excluded. The x-axis is the time for MATLAB to compute C=A*B, which gives a measure of the problem size. The y-axis of the plots in the first row is the same MATLAB time, divided by the SSMULT time. This shows that SSMULT tends to get faster for larger problems. Each circle is one matrix in the collection. The three red lines are 1.1, 1.0, and 1/1.1, so a circle in within the red lines is a result in which the run time of MATLAB and SSMULT differ by at most 10%. The green lines are 2, 1.5, 1/1.5, and 1/2. So if a circle resides above the top green line, SSMULT is over twice as fast as MATLAB for that matrix. Other than a few matricies, SSMULT is as fast as MATLAB for tiny matrices, and much faster for larger ones. SSMULT tends to be slower for very dense matrices such as computing the square of sparse(rand(2000)), but this will be fixed in the next version.

All plots are log-log.

The second row of plots compare SSMULT with SSMULT_UNSORTED. The latter function is the same as SSMULT, except that the output matrix C is returned with unsorted row indices in its columns. This is a non-standard MATLAB matrix, but many MATLAB operators work just fine on an unsorted matrix. The y-axis is the SSMULT time divided by the SSMULT_UNSORTED time. The x-axis is the same as in the first row of plots (the MATLAB time). Note that SSMULT_UNSORTED is typically faster than SSMULT, which is itself faster than the MATLAB C=A*B.