DocumentCode :
2394729
Title :
A new Gaussian elimination-based algorithm for parallel solution of linear equations
Author :
Murthy, K. N Balasubramanya ; Murthy, C. Siva Ram
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Madras, India
fYear :
1994
fDate :
22-26 Aug 1994
Firstpage :
82
Abstract :
A variant of Gaussian elimination (GE) method called the successive Gaussian elimination (SGE) algorithm, for the 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(log2 2N) steps using O(N3) processors-for solving a system of N linear algebraic equations. The SGE algorithm replaces the back-substitution phase by only one step-division-and possesses numerical stability through partial pivoting. Finally, an efficient scheduling scheme for assigning the computational tasks in the SGE algorithm on to the processors in a multiprocessor system is given
Keywords :
computational complexity; equations; linear algebra; numerical stability; parallel algorithms; processor scheduling; back-substitution phase; computational task assignment; division; linear algebraic equations; multiprocessor system; numerical stability; parallel algorithm; partial pivoting; processor assignment; scheduling scheme; successive Gaussian elimination algorithm; Algebra; Art; Computer science; Equations; Linear systems; Multiprocessing systems; Numerical stability; Scheduling algorithm; Scientific computing; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
TENCON '94. IEEE Region 10's Ninth Annual International Conference. Theme: Frontiers of Computer Technology. Proceedings of 1994
Print_ISBN :
0-7803-1862-5
Type :
conf
DOI :
10.1109/TENCON.1994.369331
Filename :
369331
Link To Document :
بازگشت