Gaussian-elimination-based algorithm for solving linear equations on mesh-connected processors

摘要

The problem of solving a system of N linear equations on a mesh-connected multiprocessor structure is considered. The solution to the problem is obtained by using a Gaussian-elimination-based algorithm called 'successive Gaussian elimination'. The new algorithm does not contain a separate backsubstitution phase. A two-dimensional array of N/spl times/(N+1) processors is employed to obtain the solution in (5N-log N-4) time steps. This scheme eliminates the use of two processor structures in conjunction, one for triangulation and the other for backsubstitution, for producing the complete solution using the existing Gaussian elimination algorithm. Most importantly, the new algorithm supports pairwise pivoting to assure numerical stability. The proposed processor-array structure is amenable for VLSI implementation as identical processors with only simple and regular interconnections are required.