Previous [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 (September 2002)


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 K 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

Full Text () Retrieve PDF document (200209_04.pdf)

Received August 31, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makato Takizawa and Myongsoon Park.