JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]


Journal of Information Science and Engineering, Vol. 18 No. 5, pp. 713-727


Fast and Scalable Parallel Algorithms for Matrix Chain Product and Matrix Powers on Reconfigurable Pipelined Optical Buses


Keqin Li 
Department of Computer Science 
State University of New York 
New Paltz, New York 12561, U.S.A. 
E-mail: li@mcs.newpaltz.edu


    Given N matrices A1, A2, ..., AN of size N X N, the matrix chain product problem is to compute A1 X A2 X … X AN. Given an N X N matrix A, the matrix powers problem is to calculate the first N powers of A, i.e., A, A2, A3, ..., AN. We show that the two problems can be solved in and times respectively, where a < 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.


Keywords: cost-optimality, distributed memory system, linear array, matrix chain product, matrix multiplication, matrix power, pipelined optical bus, reconfigurable system, scalability, speedup

  Retrieve PDF document (JISE_200205_04.pdf)