Matrix multiplication via arithmetic progressions

By Don Coppersmith, S. Winograd. 1987

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “, [29, 55, 71]) provides amortization over multiple matrix-vector multiplication instances.”
Structural Intervention Distance (SID) for Evaluating Causal Graphs (2013, methodology): “on). The worst case computational complexity for computing the SID between dense matrices is O(plog 2(p) f(p)), where squaring a matrix requires O(f(p)); a naive implementation yields f(p) = p3 while Coppersmith and Winograd (1987) report f(p) = O(p2:375477), for example. Sparse matrices lead to imp”
Particle filter theory and practice with positioning applications (2010, background): “The complexity of a matrix inversion using state of the art al gorithms [62] isO(n y ).”
Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing (2000, background): “Letting ω denote the exponent of matrix multiplication (Coppersmith and Winograd [14] prove that ω < 2.”
Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing (2004, background): “Letting ω denote the exponent of matrix multiplication (Coppersmith and Winograd [13] prove that ω < 2.”
Fast Matrix Factorization for Online Recommendation with Implicit Feedback (2016, methodology): “Although eALS does not empirically show K times faster than ALS due to the more eﬃcient matrix inversion implementation (we used the fastest known algorithm [1] with time complexity around O ( K 2 .”
The growth rate of tri-colored sum-free sets (2016, methodology): “41) algorithm of Coppersmith and Winograd [8] rests on a combinatorial construction that can, in hindsight, be interpreted1 as a large sum-free set in Fn2 .”
Fast Polynomial Factorization and Modular Composition (2011, unknown): “376 [CW90]).”
Temporal causal modeling with graphical granger methods (2007, methodology): “The complexity of matrix inversion can be reduced, for example to O(p) by using the Coppersmith Winograd algorithm [3].”
Polynomial time algorithms for multicast network code construction (2005, unknown): “Check whether all the span (time using matrix inversion based on fast matrix multiplication [6]).”
How hard is the tensor rank (2016, background): “The rank of a three-way tensor corresponds to the invariant known as the multiplicative complexity for bilinear programs [22, 24, 59], which appears in the famous problem on the complexity of matrix multiplication [16, 35, 58].”
Size-Estimation Framework with Applications to Transitive Closure and Reachability (1997, methodology): “The best known bounds for the all-pairs problem is O(mn), by solving a single-source problem for each node, or alternatively O(n) [7] using fast binary matrix multiplication.”
DOULION: counting triangles in massive graphs with a coin (2009, background): “37, the exponent of the state-ofthe-art algorithm for matrix multiplication ([10]).”