On the asymptotic complexity of rectangular matrix multiplication

DOI10.1016/0304-3975(83)90054-3zbMath0503.68029OpenAlexW1996176003MaRDI QIDQ1173402

Francesco Romani, Grazia Lotti

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90054-3

zbMATH Keywords

number of operations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic and bilinear forms, inner products (15A63)

Related Items

Parallel evaluation of the determinant and of the inverse of a matrix, Bounds and algorithms for graph trusses, Fast matrix multiplication and its algebraic neighbourhood, Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time., Improved distance sensitivity oracles with subcubic preprocessing time, Fast and efficient linear programming and linear least-squares computations, Subquadratic-time factoring of polynomials over finite fields, Subquadratic-time algorithms for normal bases, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Efficient parallel linear programming

Cites Work

• Relations between exact and approximate bilinear algorithms. Applications
• New combinations of methods for the acceleration of matrix multiplication
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Gaussian elimination is not optimal
• New Fast Algorithms for Matrix Operations
• Approximate Solutions for the Bilinear Form Computational Problem
• Partial and Total Matrix Multiplication
• Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
• Rapid Multiplication of Rectangular Matrices
• On the Number of Multiplications Required for Matrix Multiplication