Fast Approximate Matrix Multiplication by Solving Linear Systems

V. Strassen, Gaussian elimination is not optimal, Numer. Math., 14, pp. 354–356 (1969)

1969

Earlier work this paper cites.

V. Pan, How Can We Speed Up Matrix Multiplication?, SIAM Review Volume 26, No. 3, pp. 393-415 (1984)

1984

Earlier work this paper cites.

V. Strassen, Relative bilinear complexity and matrix multiplication, J. ReineAngew. Math., 375/376:406–443 (1987)

1987

Earlier work this paper cites.

J. Takche, Complexities of Special Matrix Multiplication Problems, Comput. Math. Applic. Vol. 15, No. 12, pp. 977-989 (1988)

1988

Earlier work this paper cites.

G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD (1989)

1989

Earlier work this paper cites.

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9, pp. 251–280 (1990)

1990

Earlier work this paper cites.

G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Academic Press, New York (1990)

1990

Earlier work this paper cites.

U. Baum and Mc. Clausen, Fast Fourier Transforms, SpektrumAkademischerVerlag (1993)

1993

Earlier work this paper cites.

A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank approximations, in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 370–378 (1998)

1998

Earlier work this paper cites.

E. Cohen and D. D. Lewis, Approximating matrix Multiplication for Pattern recognition tasks, Journal of Algorithms, 30(2): 211-252 (1999)

1999

Earlier work this paper cites.

D. Achiloptas and F. McSherry, Fast Computation of Low Rank Approximations, Proceedings of the 33rd Annual Symposium on Theory of Computing(2001)

2001

Cited alongside, same era.

P. Drineas and R. Kannan, Fast Monte-Carlo algorithms for approximate matrix multiplication, in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 452–459 (2001)

2001

Cited alongside, same era.

H. Cohn and C. Umans, A group-theoretic approach to fast matrix multiplication, in Proceedings of the 44th Annual FOCS, pp. 438–449 (2003)

2003

Cited alongside, same era.

P. Drineas and R. Kannan, Pass efficient algorithms for approximating large matrices, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 223–232 (2003)

2003

Cited alongside, same era.

H. Cohn, R. D. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic algorithms for matrix multiplication, in Proceedings of the 46th Annual FOCS, pp. 379–388 (2005)

N. Alon, A. Shpilka and C. Umans, On sunflowers and matrix multiplication, ECCC TR11-067, 18 (2011)

2011

Later among the works it cites.

N. Halko, P.G. Martinsson and J.A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review 53, pp. 217-288 (2011)

2011

Later among the works it cites.

A. Magen and A. Zouzias, Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication, SODA: 1422-1436 (2011)

2011

Later among the works it cites.

K. Kutzkov, Deterministic algorithms for skewed matrix products, CoRR abs/1209.4508 (2012)

Original

2012

Later among the works it cites.

V.V. Williams, Multiplying matrices faster than Coppersmith-Winograd, In Proceedings of the 44th Symposium on Theory of Computing, STOC ’12, ACM, 887–898 (2012)