Publication:
A new gaussian elimination-based algorithm for parallel solution of linear equations

Placeholder Image
Date
01-01-1995
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Abstract
In this paper, a variant of Gaussian Elimination (GE) called Successive Gaussian Elimination (SGE) algorithm for parallel solution of linear equations is presented. Unlike the conventional GE algorithm, the SGE algorithm does not have a separate back substitution phase, which requires O(N) steps using O(N) processors or O(log22 N) steps using O(N3) processors, for solving a system of linear algebraic equations. It replaces the back substitution phase by only one step division and possesses numerical stability through partial pivoting. Further, in this paper, the SGE algorithm is shown to produce the diagonal form in the same amount of parallel time required for producing triangular form using the conventional parallel GE algorithm. Finally, the effectiveness of the SGE algorithm is demonstrated by studying its performance on a hypercube multiprocessor system. © 1995.
Description
Keywords
Back substitution, Gaussian elimination, Linear equations, Multiprocessor system, Numerical stability, Pivoting, Scheduling, Task system, Triangulation
Citation
Collections