Parallel matrix computations using a reconfigurable pipelined optical bus

We present fast and cost-efficient parallel algorithms for a number of important and fundamental matrix computation problems on linear arrays with reconfigurable pipelined optical bus systems. These problems include computing the inverse, the characteristic polynomial, the determinant, the rank, the Nth power, and an LU- and a QR-factorization of a matrix and solving linear systems of equations. Our algorithms provide a wide range of performance-cost combinations. Compared with known results, the running time of parallel solutions to all these problems can be reduced by a factor of O( log N) while costs are maintained under o(N-4). (C) 1999 Academic Press.