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 n matrices can be multiplied in O (n/m + m) time when n² m, 1 m n, processing elements (PEs) are available. When only m², 1 m n, PEs are available, two n n matrices can be multiplied in O (n²/m + m (n/m) ^2. 61) time. It is shown that many graph problems can be solved efficiently using the matrix multiplication algorithms.