The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms

DOI10.1016/0898-1221(85)90095-1zbMath0674.68027OpenAlexW2006379975MaRDI QIDQ1121670

Pan, Victor Y.

Publication date: 1985

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(85)90095-1

zbMATH Keywords

matrix multiplicationbit complexity\(\lambda \) algorithmsany precision approximation algorithms

Mathematics Subject Classification ID

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

Related Items

Polynomial division and its computational complexity, A logarithmic Boolean time algorithm for parallel polynomial division

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to multiply matrices faster
• On commutativity and approximation
• Relations between exact and approximate bilinear algorithms. Applications
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem
• The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
• The complexity of partial derivatives
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Gaussian elimination is not optimal
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• The bit-complexity of arithmetic algorithms
• On the Asymptotic Complexity of Matrix Multiplication
• A generalization of the fast LUP matrix decomposition algorithm and applications