A divide-and-conquer method of solving tridiagonal systems on hypercube massively parallel computers

Author

Wang, Xiaojing ; Mou, Z. George

Author_Institution

Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA

fYear

1991

fDate

2-5 Dec 1991

Firstpage

810

Lastpage

817

Abstract

The authors present a new parallel algorithm, based on the divide-and-conquer (DC) strategy, for solving tridiagonal systems. Through a comparative study between their DC method and other well known tridiagonal solvers: cyclic odd-even reduction (CR), recursive doubling (RD), and the partition method, they show that for the binary hypercube architecture, the communication complexity of their DC method is the lowest among all, and therefore the most efficient tridiagonal solver for communication-expensive massively parallel hypercube computers

Keywords

communication complexity; hypercube networks; parallel algorithms; binary hypercube architecture; communication complexity; cyclic odd-even reduction; divide-and-conquer method; hypercube massively parallel computers; parallel algorithm; partition method; recursive doubling; tridiagonal systems solution; Chromium; Computer architecture; Computer science; Concurrent computing; Costs; Differential equations; Heart; Hypercubes; Parallel algorithms; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-2310-1

Type

conf

DOI

10.1109/SPDP.1991.218237

Filename

218237