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 + log 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.