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
http://hdl.handle.net/11536/906
ISSN: 0898-1221
DOI: 10.1016/S0898-1221(96)00208-8
Journal: COMPUTERS & MATHEMATICS WITH APPLICATIONS
Volume: 32
Issue: 12
Begin Page: 77
End Page: 91
Appears in Collections:Articles


Files in This Item:

  1. A1996WC72000006.pdf