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
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
