On the Asymptotic Complexity of Matrix Multiplication
From MaRDI portal
Publication:3947117
DOI10.1137/0211038zbMath0486.68030OpenAlexW1972332180MaRDI QIDQ3947117
Don Coppersmith, Shmuel Winograd
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211038
Related Items (56)
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs ⋮ A note on VNP-completeness and border complexity ⋮ On computation of the Bessel function by summing up the series ⋮ An augmenting path algorithm for linear matroid parity ⋮ Parity OBDDs cannot be handled efficiently enough ⋮ Discrete logarithms in \(\mathrm{GF}(p)\) ⋮ A recognition algorithm for orders of interval dimension two ⋮ A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities ⋮ Semi-algebraic complexity -- Additive complexity of matrix computational tasks ⋮ Fast commutative matrix algorithms ⋮ Computing dominators in parallel ⋮ A Method to Compute Minimal Polynomials ⋮ Rapid parallel computation of degrees in a quotient ring of polynomials over a finite field ⋮ Rubber bands, convex embeddings and graph connectivity ⋮ The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms ⋮ On the order of approximation in approximative triadic decompositions of tensors ⋮ An introduction to the computational complexity of matrix multiplication ⋮ Speedup for natural problems and noncomputability ⋮ Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation ⋮ Pebbling Game and Alternative Basis for High Performance Matrix Multiplication ⋮ Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication ⋮ Unnamed Item ⋮ Matrix multiplication via arithmetic progressions ⋮ Reply to the paper The numerical instability of Bini's algorithm ⋮ The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic ⋮ Fast matrix multiplication without APA-algorithms ⋮ A note on two-way nondeterministic pushdown automata ⋮ Certifying algorithms ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ Fast hybrid matrix multiplication algorithms ⋮ Efficient decomposition of separable algebras. ⋮ Fast rectangular matrix multiplication and some applications ⋮ Revisiting matrix squaring ⋮ Very large cliques are easy to detect ⋮ The Hackbusch conjecture on tensor formats ⋮ On cap sets and the group-theoretic approach to matrix multiplication ⋮ Subquadratic-time factoring of polynomials over finite fields ⋮ Unnamed Item ⋮ Fast rectangular matrix multiplication and applications ⋮ Limits on the Universal method for matrix multiplication ⋮ Fast parallel algorithms for polynomial division over an arbitrary field of constants ⋮ Equivalent polyadic decompositions of matrix multiplication tensors ⋮ On-line computation of transitive closures of graphs ⋮ A note on border rank ⋮ Unnamed Item ⋮ Upper bounds on the complexity of solving systems of linear equations ⋮ Lower bounds in algebraic computational complexity ⋮ On commutativity and approximation ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Improved lower bounds for some matrix multiplication problems ⋮ The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms
This page was built for publication: On the Asymptotic Complexity of Matrix Multiplication
