Parallel algorithms for solution of tridiagonal systems on multicomputers

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

doi:10.1145/318789.318822

Parallel algorithms for solution of tridiagonal systems on multicomputers

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

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

17 Citations (Scopus)

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 multicomput-ers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. 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 to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.

Original language	English
Title of host publication	Proceedings of the 3rd International Conference on Supercomputing, ICS 1989
Publisher	Association for Computing Machinery
Pages	303-312
Number of pages	10
ISBN (Electronic)	0897913094
DOIs	https://doi.org/10.1145/318789.318822
Publication status	Published - 1 Jun 1989
Externally published	Yes
Event	3rd International Conference on Supercomputing, ICS 1989 - Crete, Greece Duration: 5 Jun 1989 → 9 Jun 1989

Publication series

Name	Proceedings of the International Conference on Supercomputing
Volume	Part F130180

Conference

Conference	3rd International Conference on Supercomputing, ICS 1989
Country/Territory	Greece
City	Crete
Period	5/06/89 → 9/06/89

Bibliographical note

Publisher Copyright:
© 1989 ACM.

Access to Document

10.1145/318789.318822

Cite this

Sun, X. H., Sun, H. Z., & Ni, L. M. (1989). Parallel algorithms for solution of tridiagonal systems on multicomputers. In Proceedings of the 3rd International Conference on Supercomputing, ICS 1989 (pp. 303-312). (Proceedings of the International Conference on Supercomputing; Vol. Part F130180). Association for Computing Machinery. https://doi.org/10.1145/318789.318822

@inproceedings{e84cdeff64c4476f877d7e720c988b1e,

title = "Parallel algorithms for solution of tridiagonal systems on multicomputers",

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 multicomput-ers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. 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 to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.",

author = "Sun, \{Xian He\} and Sun, \{Hong Zhang\} and Ni, \{Lionel M.\}",

note = "Publisher Copyright: {\textcopyright} 1989 ACM.; 3rd International Conference on Supercomputing, ICS 1989 ; Conference date: 05-06-1989 Through 09-06-1989",

year = "1989",

month = jun,

day = "1",

doi = "10.1145/318789.318822",

language = "English",

series = "Proceedings of the International Conference on Supercomputing",

publisher = "Association for Computing Machinery",

pages = "303--312",

booktitle = "Proceedings of the 3rd International Conference on Supercomputing, ICS 1989",

}

Sun, XH, Sun, HZ & Ni, LM 1989, Parallel algorithms for solution of tridiagonal systems on multicomputers. in Proceedings of the 3rd International Conference on Supercomputing, ICS 1989. Proceedings of the International Conference on Supercomputing, vol. Part F130180, Association for Computing Machinery, pp. 303-312, 3rd International Conference on Supercomputing, ICS 1989, Crete, Greece, 5/06/89. https://doi.org/10.1145/318789.318822

Parallel algorithms for solution of tridiagonal systems on multicomputers. / Sun, Xian He; Sun, Hong Zhang; Ni, Lionel M.
Proceedings of the 3rd International Conference on Supercomputing, ICS 1989. Association for Computing Machinery, 1989. p. 303-312 (Proceedings of the International Conference on Supercomputing; Vol. Part F130180).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Parallel algorithms for solution of tridiagonal systems on multicomputers

AU - Sun, Xian He

AU - Sun, Hong Zhang

AU - Ni, Lionel M.

PY - 1989/6/1

Y1 - 1989/6/1

N2 - 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 multicomput-ers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. 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 to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.

AB - 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 multicomput-ers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. 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 to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.

UR - http://www.scopus.com/inward/record.url?scp=84909817332&partnerID=8YFLogxK

U2 - 10.1145/318789.318822

DO - 10.1145/318789.318822

M3 - Conference Paper published in a book

AN - SCOPUS:84909817332

T3 - Proceedings of the International Conference on Supercomputing

SP - 303

EP - 312

BT - Proceedings of the 3rd International Conference on Supercomputing, ICS 1989

PB - Association for Computing Machinery

T2 - 3rd International Conference on Supercomputing, ICS 1989

Y2 - 5 June 1989 through 9 June 1989

ER -

Parallel algorithms for solution of tridiagonal systems on multicomputers

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this