Parallel Matrix and Graph Algorithms

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.