Title: A systolic algorithm for solving dense linear systems
Authors: Lin, CJ
National Chiao Tung University
Department of Applied Mathematics
Keywords: parallel computer;linear array;systolic algorithm;dense linear system
Issue Date: 1-Dec-1996
Abstract: For an arbitrary nxn matrix A and an nx1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax=b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 less than or equal to i less than or equal to n, the i(th) linear array:is responsible to eliminate the i(th) unknown variable x(i) of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover,this algorithm can detect whether A is singular or not.
URI: http://dx.doi.org/10.1016/S0898-1221(96)00208-8
ISSN: 0898-1221
DOI: 10.1016/S0898-1221(96)00208-8
Volume: 32
Issue: 12
Begin Page: 77
End Page: 91
Appears in Collections:Articles

Files in This Item:

  1. A1996WC72000006.pdf