Efficient tridiagonal solvers on multicomputers

Author

Sun, Xian-He ; Zhang, Hong ; Ni, Lionel M.

Author_Institution

Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA

Volume

41

Issue

3

fYear

1992

fDate

3/1/1992 12:00:00 AM

Firstpage

286

Lastpage

296

Abstract

Three parallel algorithms, namely, the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm, are proposed for solving tridiagonal linear systems on multicomputers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and nonpivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals the exact solution within machine accuracy. Computation and communication complexities of the three algorithms are presented. All three methods have been implemented on a 64-node nCUBE-1 multicomputer. The analytic results closely match the results measured from the nCUBE-1 machine

Keywords

computational complexity; linear algebra; mathematics computing; 64-node nCUBE-1 multicomputer; approximate solution; communication complexities; computation complexity; divide-and-conquer parallel computation model; multicomputers; nonpivoting; parallel algorithms; parallel diagonal dominant; parallel partition LU algorithm; parallel partition hybrid; pivoting; tridiagonal linear systems; tridiagonal solvers; Complexity theory; Computational modeling; Computer science; Concurrent computing; Laboratories; Linear systems; Parallel algorithms; Parallel processing; Partitioning algorithms; Sun;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.127441

Filename

127441