| Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
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
Received August 31, 2001; accepted April 15, 2002.
Retrieve PDF document (200209_04.pdf)
Communicated by Jang-Ping Sheu, Makato Takizawa and Myongsoon Park.