Fast sparse matrix multiplication
By Raphael Yuster, Uri Zwick. TALG, 2004
302 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/b1848703264f90b73f33d936940863e4d8629f59
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- J. Demmel
- Wojciech Samek
- Oded Schwartz
- Matthieu Latapy
- K. Müller
- Sivan Toledo
- Jalaj Upadhyay
- Olga Holtz
In Computer Networks and Communications
- J. Demmel
- Aydin Buluç
- Oded Schwartz
- Grey Ballard
- Olga Holtz
- Matthieu Latapy
- K. Müller
- Jalaj Upadhyay
Citations in the corpus
- Communication optimal parallel multiplication of sparse random matrices (2013, methodology): “Yuster and Zwick [31] gave a O(nnzn + n) time serial algorithm for multiplying matrices over a ring, which uses Strassen-like fast dense rectangular matrix multiplication as a subroutine.”
- Random Projections, Graph Sparsification, and Differential Privacy (2013, methodology): “For a sparse graph, m = O(n); therefore, using [34], it takes Õ(n) time to compute the JL transform (since every column in the Laplacian of a sparse graph has Õ(1) entries).”
- Compact and Computationally Efficient Representation of Deep Neural Networks (2018, background): “Hence, a great part of the research was focused on the design of data structures that have as well low-complex dot product algorithms [7]–[10].”
- Main-memory triangle computations for very large (sparse (power-law)) graphs (2008, methodology): “Note that one may also use sparsematrix product algorithms, see for instance [39].”
- Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars (2010, background): “However, the obtained matrices are very sparse (only a few non-zero entries), such that the multiplication can be accelerated by using sparse matrix multiplication algorithms [175].”
- Minimizing Communication in Numerical Linear Algebra (2009, methodology): “lated problems. Thus our lower bounds may hold, as long as the matrix multiplication algorithm that is used agrees with Equation (1). The bounds do not apply when using Strassen-like algorithm (e.g., [YZ05]). In some cases, one can directly match the flops performed by an algorithm to Equation (1), a”