A tearing-based hybrid parallel sparse linear system solver

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:234

Article

Naumov, Maxim¹  Manguoglu, Murat¹  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.2010.04.016

来源: Elsevier

【 摘 要 】

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented. (C) 2010 Elsevier B.V. All rights reserved.

【 授权许可】

Free