Sparse Matrix Matrix multiplication terminology (SpGEMM or SpMM?)

Question

I have seen sparse matrix-matrix multiplication commonly referred to as SpGEMM, which means general/generalised sparse matrix-matrix multiplication. I've seen it once or twice (forgot where) as SpMM.

My question is, what is "general" referring to? The type of sparse matrix? Does there exist a non-general sparse matrix-matrix multiplication algorithm? All the routines/kernels I've come across are designed for sparse matrices which doesn't assume a structure, so isn't the word "general" a bit redundant? SpMM seems like a more fitting acronym.

Answer 1

I think this is a hold-over from the naming convention for the same routines in BLAS, where there are routines like DGEMM for double-precision, general matrix/matrix multiply, DSYMM for symmetric matrices, ZHEMM for complex Hermitian matrices, etc. The reason for the different routines is that, if you know the matrix is symmetric or Hermitian, you can use just the upper triangle of it to compute the result of a matrix multiply compared to the general case. Perhaps by saying SpGEMM they are implying that they also considered optimized routines for sparse symmetric matrices.

Answer 2

The specification for the sparse BLAS ( see http://www.nist.gov/customcf/get_pdf.cfm?pub_id=50993 for an overview of the specification) documents a routine for the multiplication of a sparse matrix and a dense matrix. This operation is commonly referred to as SpMM. The document does not specify a routine for multiplication of a sparse matrix and a second sparse matrix for reasons described on page 243 of the overview document.

Nevertheless, multiplication of two sparse matrices is an important operation and is often referred to as SpGEMM to distinguish it from the sparse BLAS version. See, for example, http://www.sandia.gov/~gmballa/talks/LA15.pdf, for more information on SpGEMM.