An Efficient Parallel Algorithm for the Solution of Block Tridiagonal Linear Systems

Takashi NARITOMI  Hirotomo ASO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.3   pp.256-262
Publication Date: 1995/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
parallel algorithm,  tridiagonal linear system,  parallel preconditioning,  conjugate gradient method,  

Full Text: PDF>>
Buy this Article




Summary: 
A parallel overlapping preconditioner is applied to ICCG method and the effect of the parallel preconditioning on the convergence of the method is investigated by solving large scale block tridiagonal linear systems arising from the discretization of Poisson's equation. Compared with the original ICCG method, the parallel preconditioned ICCG method can solve the problems in high parallelism with slight increasing the number of iterations. Furthermore, the speedup and the efficiency are evaluated for the parallel preconditioned ICCG method by substituting the experimental results into formulae of complexity. For example, when a domain of simulation is discretized on a 250250 rectangular grid and the preconditioner is divided into 249 smaller ones, its speedup is 146.3 with the efficiency 0.59.