I just took a look at the paper and, after reading a bit, I am baffled that there are no citations of the H-matrix literature (Ctrl+F "Hackbusch" turns up nothing...). The paper seems to be in a similar spirit as the well-known H-matrix/H-matrix multiplication algorithms, which take O(N log^2 N) work, for O(1) ranks, but using truncation instead of low-rank approximations in clusters. Since only factors of 2-3x are reported versus SGEMM, which is O(N^3), that tells you that this algorithm (or, at least, its implementation) is O(N^3). I do not think a comparison can be drawn to sparse matrix-matrix multiply algorithms. I believe Gilbert and Buluc have the most recent publication on parallel sparse mat-mat. I have done some work on parallel H-matrix/H-matrix multiplication (the code is here: http://bitbucket.org/poulson/dmhm), but I haven't pushed the paper out the door yet. See http://www.ices.utexas.edu/~poulson/slides/DMHM.pdf for the talk I gave on it. I suspect that the ideas from parallel H-matrix/H-matrix multiplication could be used to generate a communication-efficient sparse mat-mat if it is okay to generate the result in a more general data-sparse form (i.e., low rank blocks) rather than specifically as explicitly classically sparse. Jack On Wed, Mar 28, 2012 at 10:07 PM, Hong Zhang <[email protected]> wrote:

Entire paper discusses SpAMM, and compares with SGEMM. Sorry, I do not see anything about SpMV. Hong

On Wed, Mar 28, 2012 at 9:52 PM, Matthew Knepley <[email protected]>wrote:

...

On Wed, Mar 28, 2012 at 9:39 PM, Hong Zhang <[email protected]> wrote:

...

Matt:

...

to the new scalable MatMatMult() that is done in PETSc? Is it possible to even compare the flop rates sensibly?

http://arxiv.org/abs/1203.1692

"An Optimized Sparse Approximate Matrix Multiply" computes Approximate matrix product for matrices with decay ^^^^^^^^^^^^ ^^^^^^^^^^ It is for special application in chemistry(?), not applicable for general sparse matrix product. No comparison can be drawn to petsc's C=A*B.

This is the wrong conclusion. What he does is sparsify the result, so he is computing SOME sort of sparse matrix-vector product. The question is:

Does his SpMV use the same algorithm as PETSc?

That is why I asked.

Matt

...

Hong

...

This is what Jeff is planning on using in his SciDAC.

Matt

-- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener

-- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener