Parallel Matrix and Graph Algorithms
SIAM Journal on Computing1981Vol. 10(4), pp. 657–675
Citations Over TimeTop 10% of 1981 papers
Abstract
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.