Parallel Matrix and Graph Algorithms
Eliezer Dekel, David Nassimi, Sartaj K. Sahni · SIAM Journal on Computing · 1981
Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two $n \times n$ matrices can be multiplied in $O(n/m + \log m)$ time when $n^2 m$, $1 \leqq m \leqq n$, processing elements (PEs) are available. When only $m^2 $, $1 \leqq m \leqq n$, PEs are available, two $n \times n$ matrices can be multiplied in $O(n^2/m + m(n/m)^{2.61} )$ time. It is shown that many graph problems can be solved efficiently using the matrix multiplication algorithms.
Cited by 353 works. doi:10.1137/0210049
Authors
References
- Parallel Processing with the Perfect Shuffle
- Lower bounds on information transfer in distributed computations
- Very high-speed computing systems
- Some Complexity Results for Matrix Computations on Parallel Processors
- The Parallel Evaluation of General Arithmetic Expressions
- Sorting on a mesh-connected parallel computer
- New Parallel-Sorting Schemes
- Fundamentals of data-structures
- Communication, transmission, and transportation networks
- Optimal algorithms for parallel polynomial evaluation