Fast and scalable parallel algorithms for matrix chain product and matrix powers on reconfigurable pipelined optical buses

Given N matrices A(1), A(2),..., A(N) of size N x N, the matrix chain product problem is to compute A(1) x A(2) x ... x A(N). Given an N x N matrix A, the matrix powers problem is to calculate the first N powers of A, i.e., A, A(2), A(3),..., A(N). We show that the two problems can be solved in O(Nalpha+1/p + N2(l+l/alpha)/p(2/alpha) log P/N + (log N)(2)) and O(Nalpha+1/p + N2(l+l/alpha)/p(2/alpha) log p + log Nlog p) times respectively, where alpha<2.3755, and p, the number of processors, can be arbitrarily chosen in the interval [1..Nalpha+1]. Our highly scalable algorithms can be implemented on a linear array with a reconfigurable pipelined bus system, which is a distributed memory system using optical interconnections.