A tearing-based hybrid parallel banded linear system solver

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:226

Article

Naumov, Maxim¹  Sameh, Ahmed H.¹ 

[1] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47907 USA

关键词: Parallel algorithms;    Hybrid schemes;    Domain Decomposition;    Krylov subspace methods;    CG;    BiCGstab;   

DOI  :  10.1016/j.cam.2008.08.019

来源: Elsevier

【 摘 要 】

A new parallel algorithm for the solution of banded linear systems is proposed. The scheme tears the coefficient matrix into several overlapped independent blocks in which the size of the overlap is equal to the system's bandwidth. A corresponding splitting of the right-hand side is also provided. The resulting independent, and smaller size, linear systems are solved tinder the constraint that the solutions corresponding to the overlap regions are identical. This results in a linear system whose size is proportional to the sum of the overlap regions which we refer to as the balance system. We propose a solution strategy that does not require obtaining this balance system explicitly. Once the balance system is solved, retrieving the rest of the solution can be realized with almost perfect parallelism. Our proposed algorithm is a hybrid scheme that combines direct and iterative methods for solving a single banded system of linear equations on parallel architectures. It has broad applications in finite-element analysis, particularly as a parallel solver of banded preconditioners that can be used in conjunction with outer Krylov iterative schemes. (c) 2008 Elsevier B.V. All rights reserved.

【 授权许可】

Free