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

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.<>