On the exact and approximate bilinear complexities of multiplication of \(4\times 2\) and \(2\times 2\) matrices

DOI10.1134/S0081543813070079zbMath1317.68061OpenAlexW1964758312MaRDI QIDQ483185

Yong-Cai Geng, Sumit K. Garg

Publication date: 16 December 2014

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543813070079

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

The bilinear complexity and practical algorithms for matrix multiplication ⋮ Unnamed Item ⋮ Tensor decomposition and homotopy continuation ⋮ On the approximate bilinear complexity of matrix multiplication ⋮ The approximate bilinear complexity of the multiplication of matrices of sizes \(2\times n\) and \(n\times 4\) ⋮ On bilinear complexity of multiplying \(2 \times 2\)-matrix by \(2 \times m\)-matrix over finite field ⋮ Tensor rank is not multiplicative under the tensor product ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ Two bilinear \((3\times3)\)-matrix multiplication algorithms of complexity 25 ⋮ On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication ⋮ A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Relations between exact and approximate bilinear algorithms. Applications
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• On the complexity of the multiplication of matrices of small formats
• Gaussian elimination is not optimal
• On multiplication of 2 \(\times\) 2 matrices
• On the complexity of some algorithms of matrix multiplication
• Partial and Total Matrix Multiplication
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
• On Winograd's Algorithm for Inner Products
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication