On fixed-point, Krylov, and 2×2 block preconditioners for nonsymmetric problems

Ben S. Southworth, Abdullah Ali Sivas, Sander RhebergenSIAM J. Matrix Anal. Appl 2019 · DOI · OpenReview

TL;DR

This paper establishes a direct equivalence between the convergence of iterative methods applied to a 2x2 block system and its preconditioned Schur complement. This theoretical breakthrough provides crucial insights into designing effective block preconditioners for nonsymmetric problems, particularly those arising from discretizations of PDEs.

What Problem Does This Paper Address?

Many scientific and engineering problems, especially those involving discretized partial differential equations (PDEs) using methods like mixed-finite elements, lead to large, nonsymmetric linear systems with a 2x2 block structure. Solving these systems efficiently often relies on iterative methods, such as Krylov subspace methods (like GMRES), which in turn require effective preconditioners. While block preconditioners are commonly used, a deep theoretical understanding of their convergence behavior, especially for nonsymmetric systems, has been lacking. Specifically, the relationship between the convergence of a preconditioned 2x2 block system and its underlying Schur complement has not been fully elucidated, leading to challenges in designing optimal preconditioners.

Methods

The core of this paper lies in establishing a theoretical equivalence between the convergence of Krylov methods (and fixed-point iterations) applied to a 2x2 block system and the convergence of similar methods applied to its preconditioned Schur complement. The authors achieve this by analyzing polynomials of preconditioned operators. They introduce and analyze various block preconditioners, including block-triangular, block-diagonal, approximate block-LDU, and symmetric block-triangular forms. The theoretical framework focuses on understanding the relationship between minimizing polynomials of the preconditioned 2x2 operator and the preconditioned Schur complement. This equivalence allows for a more direct analysis of convergence properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical verification using a specific example.

Key Insights and Ideas

  • Schur Complement is Key: The paper strongly suggests that an effective preconditioner for the Schur complement is a necessary and sufficient condition for rapid convergence of preconditioned GMRES for 2x2 block systems. This is a powerful result for designing preconditioners.
  • Fixed-Point vs. Krylov Equivalence: A key finding is that for certain block preconditioners (like block-triangular), the convergence of fixed-point iterations is directly equivalent to the convergence of Krylov methods.
  • Symmetric Block-Triangular/LDU Offer Little Gain: Symmetric block-triangular and approximate block-LDU preconditioners offer minimal improvement over simpler block-triangular preconditioners, despite the added computational cost of computing approximate inverses.
  • Block-Jacobi is Roughly Twice as Slow: Block-Jacobi preconditioning generally requires about twice as many iterations as block-triangular preconditioning to reach a given tolerance.
  • Sign of Schur Complement Matters (Sometimes): For block-triangular preconditioners, the sign of the Schur complement approximation can significantly impact convergence, especially when inexact inverses are used. This is less pronounced for block-diagonal preconditioners.
  • Theory Extends to Inexact Inverses: The theoretical results, often derived assuming exact inverses of diagonal blocks, are shown to extend well to practical scenarios with inexact inverses.

Key Results

The paper provides theoretical proofs establishing the equivalence between the convergence of preconditioned 2x2 block systems and their Schur complements for various block preconditioners. Numerical results, particularly on a discretized Navier-Stokes problem, demonstrate that:

  • Block-triangular preconditioners (lower and upper) are generally efficient.
  • Symmetric block-triangular and approximate block-LDU preconditioners do not offer significant advantages over block-triangular ones.
  • Block-diagonal preconditioning takes approximately twice as many iterations as block-triangular preconditioning.
  • The theoretical findings hold for inexact inverses of the momentum block, with convergence rates showing a strong correlation to the momentum block's residual tolerance.

Limitations and Future Work

  • Exact Inverse Assumption: While the theory is often derived assuming exact inverses of diagonal blocks, the paper shows this extends to inexact inverses. However, the precise conditions and extent of this extension could be further explored.
  • Upper vs. Lower Block-Triangular: The paper notes a slight advantage of block-lower triangular over block-upper triangular preconditioning in their numerical tests, but the exact reasons are not fully understood and are an area of ongoing work.
  • General Block-Diagonal Preconditioners: The paper highlights that results for block-Jacobi do not directly extend to more general block-diagonal preconditioners where the diagonal blocks are not exact inverses.
  • Future Work: The authors suggest further investigation into the differences between upper and lower block-triangular preconditioning and exploring the practical implications of their theoretical findings in other application areas.

Summary updated

Abstract

The solution of matrices with $2\times 2$ block structure arises in numerous areas of computational mathematics, such as PDE discretizations based on mixed-finite element methods, constrained optimization problems, or the implicit or steady state treatment of any system of PDEs with multiple dependent variables. Often, these systems are solved iteratively using Krylov methods and some form of block preconditioner. Under the assumption that one diagonal block is inverted exactly, this paper proves a direct equivalence between convergence of $2\times2$ block preconditioned Krylov or fixed-point iterations to a given tolerance, with convergence of the underlying preconditioned Schur-complement problem. In particular, results indicate that an effective Schur-complement preconditioner is a necessary and sufficient condition for rapid convergence of $2\times 2$ block-preconditioned GMRES, for arbitrary relative-residual stopping tolerances. A number of corollaries and related results give new insight into block preconditioning, such as the fact that approximate block-LDU or symmetric block-triangular preconditioners offer minimal reduction in iteration over block-triangular preconditioners, despite the additional computational cost. Theoretical results are verified numerically on a nonsymmetric steady linearized Navier-Stokes discretization, which also demonstrate that theory based on the assumption of an exact inverse of one diagonal block extends well to the more practical setting of inexact inverses.
BibTeX
@article{southworth2019fixed,
  author = {Ben S. Southworth and Abdullah Ali Sivas and Sander Rhebergen},
  title = {{On fixed-point, Krylov, and 2×2 block preconditioners for nonsymmetric problems}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2019},
  doi = {10.1137/19m1298317},
}
Figure