Low-rank updates of balanced incomplete factorization preconditioners

详细信息    查看全文

• 作者：J. Cerdán ; J. Marín ; J. Mas
• 关键词：Iterative methods ; Preconditioning ; Low rank update ; Balanced incomplete factorization ; Sparse linear systems
• 刊名：Numerical Algorithms
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：74
• 期：2
• 页码：337-370
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing; Algorithms; Algebra; Theory of Computation; Numerical Analysis;
• 出版者：Springer US
• ISSN：1572-9265
• 卷排序：74

文摘

Let Ax = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + PQT where \(P, Q \in \mathbb {R}^{n \times k}\) are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system Bx = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover, the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence.