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