Fast and Scalable Parallel Algorithms for Matrix Chain Product and Matrix Powers on Optical Buses
Keqin Li · Kluwer Academic Publishers eBooks · 2005
Given N matrices A 1, A 2 ..., A N of size N − N, the matrix chain product problem is to compute A 1 × A 2 × ... × 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\left( {\frac{{N^{\alpha + 1} }} {p} + \frac{{N^{2(1 + 1/\alpha )} }} {{p^{2/\alpha } }}\log \frac{p} {N} + (\log N)^2 } \right)$$ and $$ O\left( {\frac{{N^{\alpha + 1} }} {p} + \frac{{N^{2(1 + 1/\alpha )} }} {{p^{2/\alpha } }}\log p + \log N\log p} \right)$$ times respectively, where α < 2.3755, and p, the number of processors, can be arbitrarily chosen in the interval [1‥ N α+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.