Gaussian elimination is not optimal

By V. Strassen. 1969

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.”
Fast Algorithms for Convolutional Neural Networks (2015, methodology): “The Strassen algorithm for fast matrix multiplication [13] was used by Cong and Xiao [3] to reduce the number of convolutions in a convnet layer, thereby reducing its total arithmetic complexity.”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “icalimplementationsoftheGEMMmethod,such as in CUDNN[38], implement “implicit GEMM”, in which the Toeplitz matrix is never materialized. It was also reported[49] that the Strassen matrix multiplication[223] can be used for the underlying computation, reducing the number of operations by up to 47%. A ”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “1Strassen’s algorithm [13] and its generalizations offer a recursive approach to faster matrix multiplications over multiple processing nodes, but they are often not preferred because of their high communication cost [14].”
The Fastest and Shortest Algorithm for all Well-Defined Problems (2000, methodology): “×Rn·n of size l(x)∼n2, then tp∗(x):=2n3 upper bounds the true computation time timep∗(x)=n2(2n − 1). We know there exists an algorithm p′ for matrix multiplication with time p′(x) ≤ tp′(x) := c·n2.81 [21]. The time-bound function (cast to an integer) can, as in many cases, be computed very quickly, ”
On the optimal recovery threshold of coded matrix multiplication (2017, unknown): “2More sophisticated algorithms [28] also require super-quadratic complexity in N , so the conclusion will hold if those algorithms are used at workers as well.”
Matrices: Theory and Applications (2002, unknown): “Here is Strassen’s formula [33].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “We seek a factorization of the form A = Q R Π∗, m× n m× n n× n n× n (16.5) 1The celebrated method of Strassen (1969) has exponent ω = log2(7) = 2.807 · · · .”
Why Does Deep and Cheap Learning Work So Well? (2016, background): “mal: the Strassen algorithm [47] requires only O(nω) multiplications (synapses), where ω = log2 7 ≈ 2.”
Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD (2013, background): “For linear algebra algorithms of O(n(3)) complexity run on a machine with a fast or local memory of size M (hence excluding Strassen-like algorithms [18], [41]), the asymptotic communication lower bound is known to be Ω(n(3)/M) words (bandwidth cost) and Ω(n(3)/M) messages (latency cost) [11].”
Tractability of Multivariate Problems (2008, methodology): “It was also used in the work of Coppersmith and Winograd [32], Pan [182], Strassen [222], and others for the famous problem of matrix multiplication.”
Existence and Computation of Low Kronecker-Rank Approximations for Large Linear Systems of Tensor Product Structure (2004, unknown): “In that case Strassen’s algorithm [ 13 ] yields a better order OðN log2ð7Þ Þ. Obviously, OðN 2 Þ is a lower bound if no structure on the matrix A is imposed.”
The LINPACK Benchmark: past, present and future (2003, methodology): “This excludes the use of a fast matrix multiply algorithm like Strassen’s [3, 34, 47, 52] or Coppersmith and Winograd’s [12] methods for matrix multiplication.”
A symbol of uniqueness: the cluster bootstrap for the 3-loop MHV heptagon (2014, background): “Finally, it reduces row and column operations to matrix multiplications, which can be done very fast with the help of other well-known algorithms, for example [90].”
Bounded-rank tensors are defined in bounded degree (2011, background): “Tensor rank is an important notion in such diverse areas as multilinear algebra and algebraic geometry [10, 11, 25]; algebraic statistics [1, 17], in particular with applications to phylogenetics [2, 9, 8, 30], and complexity theory [6, 7, 14, 21, 22, 23, 28, 29].”