Lessa: an array to solve a aet of linear equations

Abstract

A dedicated linear array of simple processors is proposed to solve a set of linear equations. Data structure and algorithm also presented for the array to solve a set of n linear equations in O(n ²+ 3_n) time on an array of n processors. The given algorithm is a parallelization of the Gaussian elimination algorithm. The data input to the array is purely sequential. The algorithm is optimal, within a constant, in its time and area requirements.

Keywords:

• Systolic array
• gaussian elimination
• parallel algorithms
• area-time performance

C.R. Categories:

• F.1.1
• F.2.1
• B.7.1

†tPresent address: Department ol Computer Science. University of Central Florida. Orlando. Florida 32816 0001. U.S.A.

†tPresent address: Department ol Computer Science. University of Central Florida. Orlando. Florida 32816 0001. U.S.A.

Notes

†tPresent address: Department ol Computer Science. University of Central Florida. Orlando. Florida 32816 0001. U.S.A.