Array architecture for solving large-scale linear system of equations by block Gauss-Seidel algorithm and local reordering approach

Author

Chen, Ben ; Onoda, Mahoki

Author_Institution

Dept. of Electr. & Electron. Eng., Tokyo Inst. of Technol., Japan

fYear

1989

fDate

1-2 June 1989

Firstpage

56

Lastpage

59

Abstract

An array architecture for solving a large-scale linear system of equations (LSE) by the block Gauss-Seidel (BGS) algorithm is presented. A new triangular type of reconfigurable systolic array (LU-module) is proposed which can solve mth (where m is the block size) order LSE directly based on LU decomposition. An array architecture using one LU-module and an appropriate number of AM-modules (matrix-vector accumulative-multiplication module) is designed for solving nth order large-scale LSE in which the BGS algorithm can be performed with the least waiting time between LU- and AM-modules. In order to perform the BGS algorithm effectively, a local reordering approach is considered.<>

Keywords

cellular arrays; computer architecture; matrix algebra; LU decomposition; LU-module; array architecture; block Gauss-Seidel algorithm; large-scale linear system; linear equations; local reordering; matrix-vector accumulative-multiplication module; reconfigurable systolic array; Equations; Gaussian processes; Hardware; Large-scale systems; Linear systems; Matrices; Partitioning algorithms; Pipeline processing; Systolic arrays; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Computers and Signal Processing, 1989. Conference Proceeding., IEEE Pacific Rim Conference on

Conference_Location

Victoria, BC, Canada

Type

conf

DOI

10.1109/PACRIM.1989.48305

Filename

48305