11
$\begingroup$

Does matrix multiplication (both Mat*Mat, and Mat*Vec) scale with number of non-zeros, or with the size of the matrix? Or some combination of the two.

What about with shape.

For example, I have a 100 x 100 matrix with 100 values in it, or a 1000 x 1000 matrix with 100 values in it.

When squaring these matrices (or multiplying them by similar matrices with similar sparsity), is the first (100x100) going to be faster than the second (1000x1000)? Does it depend on where the values are?

If it is implementation dependent, I am interested in the answer for PETSc.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
12
$\begingroup$

The cost of sparse matrix-vector multiplication scales linearly with the number of nonzero entries, as each entry is multiplied once by some entry in the vector.

The cost of sparse matrix-matrix multiplication is highly dependent on the structure of the nonzeros. For instance, consider squaring a sparse matrix $A$ which is of an arrowhead structure:

$$ A = \left(\begin{array}{ccccc} \delta_1 & & & & \beta_1 \\ & \delta_2 & & & \beta_2 \\ & & \ddots & & \vdots \\ & & & \delta_{n-1} & \beta_{n-1} \\ \gamma_1 & \gamma_2 & \cdots & \gamma_{n-1} & \delta_n \end{array}\right), $$

then $A$ has $O(n)$ nonzeros, but $A^2$ is dense. There is a well-known graph interpretation of this phenomenon: every path of length 1 or 2 in the graph of $A$ becomes an edge in the graph of $A^2$ (i.e., a nonzero entry in $A^2$).

Improve this answer
$\endgroup$
5
$\begingroup$

Firstly, it is implementation dependent. If you implement a sparse matrix as a dense matrix and fill in the non-zeroes, it will scale with the overall size of the matrix. If it is stored as nonzeroes, it will scale as the access time scales with the matrix size.

In the PETSc documentation, it explains that the default storage for sparse matrices is compressed row storage, which scales with the number of rows and the number of non-zero values per row. So I would expect a MatMat to scale broadly with the square of this measure; i.e. $O(r^2 n^2)$.

One thing to note, however, is that there is no point storing what isn't there; if you care about this performance, why are you storing a 100 values for a 1000x1000 matrix? That means that at least 90% of the rows/columns have no nonzero values at all, and could be entirely removed from the matrix. If the pattern of non-zero values does not change, consider removing the always-all-zero rows from both this and the target matrix; it will remove some 90% of the effort, leaving the performance of the two matrices (1002, 10002) broadly equivalent.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Empty rows and columns often have function with respect to a problem (ie keeping a uniform mapping between row number to the location in an image for example) There will be a trade-off not getting rid of these however. $\endgroup$
    – meawoppl
    May 15, 2012 at 21:51
  • $\begingroup$ Exactly; making your runtime performance around 10x worse just to maintain a mapping that you could store in a single array of 100 ints is not a normal tradeoff. Since the question was about performance as the blank size of the matrix scales, this is a pretty important point particularly for PETSc, as he asked about. $\endgroup$
    – Phil H
    May 16, 2012 at 12:01
4
$\begingroup$

A complete model of SpMV performance is given in this paper. It shows clearly that the main limiter is bandwidth, although you can lessen the burden by using multiple vectors. After that you run into instruction issue limitations and a limit on outstanding write instructions I believe.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.