A Parallel Algorithm for Block Tridiagonal Systems

Author

Zhang, Heng ; Zhang, Wu ; Sun, Xian-He

Author_Institution

Sch. of Comput. Eng. & Sci., Shanghai Univ., Shanghai

fYear

2008

fDate

1-4 Dec. 2008

Firstpage

62

Lastpage

65

Abstract

A parallel algorithm, namely parallel block diagonal dominant (PBDD) algorithm, is proposed to solve block tridiagonal linear systems on multi-computers. This algorithm is based on divided-and-conquer idea of the PDD method. When the systems is strictly block diagonal dominant, the PBDD is highly parallel and provides approximate solutions that equals to the exact solutions within machine accuracy. The PBDD method has been implemented on a 64-node multi-computer. The analytic results match closely with the results measured from the numerical experiments.

Keywords

divide and conquer methods; multiprocessing systems; parallel algorithms; 64-node multicomputer; block tridiagonal linear systems; block tridiagonal systems; divide-and-conquer method; parallel algorithm; parallel block diagonal dominant algorithm; strictly block diagonal dominant systems; Algorithm design and analysis; Application software; Bismuth; Concurrent computing; Distributed computing; Educational institutions; Linear systems; Mathematics; Parallel algorithms; Partitioning algorithms; Block tridiagonal systems; block LU decomposition; block diagonal dominant; divided-and-conquer;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Computing, Applications and Technologies, 2008. PDCAT 2008. Ninth International Conference on

Conference_Location

Otago

Print_ISBN

978-0-7695-3443-5

Type

conf

DOI

10.1109/PDCAT.2008.21

Filename

4710962