Anderson acceleration of the Jacobi iterative method: An efficient alternative to Krylov methods for large, sparse linear systems

JOURNAL OF COMPUTATIONAL PHYSICS

卷:306

Article

Pratapa, Phanisri P.¹  Suryanarayana, Phanish¹  Pask, John E.² 

[1] Georgia Inst Technol, Coll Engn, Atlanta, GA 30332 USA

[2] Lawrence Livermore Natl Lab, Div Phys, Livermore, CA 94550 USA

关键词: Linear systems of equations;    Fixed-point iteration;    Jacobi method;    Anderson extrapolation;    Nonsymmetric matrix;    Poisson equation;    Helmholtz equation;    Parallel computing;   

DOI  :  10.1016/j.jcp.2015.11.018

来源: Elsevier

【 摘 要 】

We employ Anderson extrapolation to accelerate the classical Jacobi iterative method for large, sparse linear systems. Specifically, we utilize extrapolation at periodic intervals within the Jacobi iteration to develop the Alternating Anderson-Jacobi (AAJ) method. We verify the accuracy and efficacy of AAJ in a range of test cases, including nonsymmetric systems of equations. We demonstrate that AAJ possesses a favorable scaling with system size that is accompanied by a small prefactor, even in the absence of a preconditioner. In particular, we show that AAJ is able to accelerate the classical Jacobi iteration by over four orders of magnitude, with speed-ups that increase as the system gets larger. Moreover, we find that AAJ significantly outperforms the Generalized Minimal Residual (GMRES) method in the range of problems considered here, with the relative performance again improving with size of the system. Overall, the proposed method represents a simple yet efficient technique that is particularly attractive for large-scale parallel solutions of linear systems of equations. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free