I dug in a little deeper, and I recommend reading their previous paper: http://arxiv.org/abs/1011.3534
That paper actually _does_ mention the connection to H-matrix algebra: "SpAMM is similar to the H-matrix algebra of Hackbusch and co-workers, where off-diagonal sub-matrices are treated as reduced rank factorizations (truncated SVD), typically structured and grouped to reflect properties of the underlying operators. For problems with rapid decay, truncated SVD may behave in a similar way to simple dropping schemes. SpAMM is different than the H-matrix algebra as it achieves separation uniquely in the product space and does not rely on a reduced complexity representation of matrices. For very slow decay, the H-matrix algebra may certainly offer a path for intractable problems for which SpAMM is ineffective." So it seems that the claim is that SpAMM might be more computationally efficient than H-matrices for fast decay, but ineffective otherwise. Either way, I don't think it's going to help with classical parallel sparse matrix-matrix multiplication. Jack On Wed, Mar 28, 2012 at 10:28 PM, Jack Poulson <jack.poulson at gmail.com>wrote: > Actually, please excuse my misreading. The quoted 2-3x speedup was versus > itself due to hardware prefetch, so it does appear to be asymptotically > better than SGEMM (they quote the crossover at n ~= 1000). > > Jack > > > On Wed, Mar 28, 2012 at 10:23 PM, Jack Poulson <jack.poulson at > gmail.com>wrote: > >> 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.pdffor 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 <hzhang at mcs.anl.gov> 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 <knepley at >>> gmail.com>wrote: >>> >>>> On Wed, Mar 28, 2012 at 9:39 PM, Hong Zhang <hzhang at mcs.anl.gov> 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 >>>> >>> >>> >> > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20120328/e28a4625/attachment.html>