Title :
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
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;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218237
