Communication Avoiding ILU0 Preconditioner

In this paper we present a communication avoiding ILU0 preconditioner for solving large linear systems of equations by using iterative Krylov subspace methods. Recent research has focused on communication avoiding Krylov subspace methods based on so-called s-step methods. However, there are not many...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2015-01, Vol.37 (2), p.C217-C246
Main Authors: Grigori, Laura, Moufawad, Sophie
Format: Article
Language:English
Subjects:
Computation
Computer Science
Convergence
Dissection
Distributed, Parallel, and Cluster Computing
Iterative methods
Linear systems
Mathematical analysis
Redundant
Subspace methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we present a communication avoiding ILU0 preconditioner for solving large linear systems of equations by using iterative Krylov subspace methods. Recent research has focused on communication avoiding Krylov subspace methods based on so-called s-step methods. However, there are not many communication avoiding preconditioners yet, and this represents a serious limitation of these methods. Our preconditioner allows us to perform $s$ iterations of the iterative method with no communication, through ghosting some of the input data and performing redundant computation. To avoid communication, an alternating reordering algorithm is introduced for structured and well partitioned unstructured matrices, which requires the input matrix to be ordered by using a graph partitioning technique such as k-way or nested dissection. We show that the reordering does not affect the convergence rate of the ILU0 preconditioned system as compared to k-way or nested dissection ordering, while it reduces data movement and is expected to reduce the time needed to solve a linear system. In addition to communication avoiding Krylov subspace methods, our preconditioner can be used with classical methods such as GMRES to reduce communication.
ISSN:1064-8275
1095-7197
DOI:10.1137/130930376