The bit-operation complexity of matrix multiplication and of all pair shortest path problem

DOI10.1016/0898-1221(81)90130-9zbMath0462.68019OpenAlexW2139007071MaRDI QIDQ1152952

Pan, Victor Y.

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0898-1221(81)90130-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Polynomial division and its computational complexity, Algebraic complexity of computing polynomial zeros, Faster All-Pairs Shortest Paths via Circuit Complexity, A logarithmic Boolean time algorithm for parallel polynomial division, The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms, The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic, From Circuit Complexity to Faster All-Pairs Shortest Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest-path problem is not harder than matrix multiplication
• Complexity measures for matrix multiplication algorithms
• New combinations of methods for the acceleration of matrix multiplication
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• The Computational Complexity of Continued Fractions
• New Fast Algorithms for Matrix Operations
• The bit-complexity of arithmetic algorithms
• Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
• New Bounds on the Complexity of the Shortest Path Problem