Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms

DOI10.1137/0202013zbMath0294.65022OpenAlexW2053839977MaRDI QIDQ4047031

J. Musinski, John E. Hopcrofts

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/5999

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Multiplicative complexity of direct sums of quadratic systems, Nonuniform ACC Circuit Lower Bounds, Computing Riemann-Roch spaces via Puiseux expansions, An introduction to the computational complexity of matrix multiplication, Unnamed Item, On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping, The approximate bilinear complexity of the multiplication of matrices of sizes \(2\times n\) and \(n\times 4\), Univariate polynomial factorization over finite fields with large extension degree, Using duality for the synthesis of an optimal algorithm involving matrix multiplication, New combinations of methods for the acceleration of matrix multiplication, Fast matrix multiplication and its algebraic neighbourhood, Dual problems of multiplication of a vector by a matrix, On the exact and approximate bilinear complexities of multiplication of \(4\times 2\) and \(2\times 2\) matrices, A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications, On the additive complexity of 2 \(\times 2\) matrix multiplication, An extended duality theorem and multiplication of several matrices, Numerical CP decomposition of some difficult tensors, Algebraic complexities and algebraic curves over finite fields, Some elementary proofs of lower bounds in complexity theory, On the optimal evaluation of a set of bilinear forms, Global properties of tensor rank, \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication, Using duality to compute the pair of matrix products \(QY\) and \(Y^TQ\) over a noncommutative ring, On a signal processing algorithms based class of linear codes, On the synthesis of fast algorithms for signal processing, A noncommutative algorithm for multiplying 5\(\times 5\) matrices using 102 multiplications, A fast algorithm for reversion of power series, Stand-alone results and applications in multilinear algebra, Amortized multi-point evaluation of multivariate polynomials, The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations, A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices