PaperlayerView exact revision on arXiv

Source-linked AI summary

A parameterized block LU preconditioning for double saddle point problems

Hamed Aslani, Mehdi Najafi Kalyani, Davod Khojasteh Salkuyeh

arXiv:2609.12615v1math.NAcs.NA

TL;DR

Shift-splitting methods can incur dominant costs from shifted solves and converge slowly on large problems. This paper develops a two-parameter block LU preconditioner induced by a stationary iteration; the preconditioned matrices exhibit eigenvalue clustering around one and require fewer Krylov iterations in exact and inexact settings.

  • Problem

    Shift-splitting iterations require solving shifted linear systems, which can dominate large-scale computation, and may converge slowly as dimensions grow.

    Source: §1 · p. 3

  • Method

    The paper constructs a two-parameter block LU preconditioner for three-by-three saddle point problems using a stationary iteration, for use with Krylov methods such as GMRES and FGMRES.

    Source: §1 · p. 4, §2 · p. 5, §6 · p. 24

  • Results

    The proposed preconditioner yields eigenvalues clustered around one and reduces Krylov iterations in exact and inexact settings.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Avoiding explicit matrix inversions lowers practical computational cost and makes the inexact implementation computationally viable.

    Source: §1 · p. 4

    The demonstrated theoretical and numerical scope is a class of three-by-three saddle point problems, with further research directions remaining open.

    Source: §6 · p. 25

Abstract

from arXiv · show

We present a biparametric preconditioning technique for large, sparse, non-symmetric, and non-singular double saddle point problems. The preconditioner is induced using a stationary iteration method. It is also based on a two-parameterized block LU factorization of the coefficient matrix. To begin with, some convergence results of the iteration method are derived. Moreover, the spectral features exhibited by the preconditioned matrix are given. Finally, the presented preconditioner is conjuncted with the GMRES method. Numerical results demonstrate the satisfactory performance of the preconditioner.

1 Introduction

Double saddle point systems arise in scientific and engineering applications, but existing generalized saddle point methods do not apply directly to this problem class. The paper introduces a block preconditioner for Krylov methods and analyzes exact and inexact forms.

1 Introduction

  • Double saddle point systems arise in scientific and engineering applications, and existing methods for generalized saddle point problems do not apply directly to them.The paper identifies the need for new approaches to double saddle point problems.Source: §1 · pp. 1–2
  • Because the coefficient matrix is typically large and sparse, Krylov methods are appropriate, while preconditioning is used to improve computational efficiency.Source: §1 · p. 2
  • Shift-splitting iterations require shifted linear-system solves and can converge slowly, while constructing Schur complements can require expensive matrix inversions.The shifted systems are better conditioned than the original, but solving them remains a dominant cost in large-scale problems.Source: §1 · pp. 3–4
  • The proposed block preconditioning approach is intended for Krylov subspace methods such as GMRES and FGMRES.The paper's main novelty is a two-parameter block LU structure, with an inexact implementation intended to make the method computationally viable.Source: §1 · p. 4
  • The proposed preconditioner clusters eigenvalues around one, reduces Krylov iterations in exact and inexact settings, and avoids explicit inversions to lower practical cost.The paper studies the spectral properties of both P^-1K and the inexact form P̂^-1K.Source: §1 · p. 4

2 Suggested iterative method and its convergence

The section defines a stationary iteration through a splitting of the coefficient matrix and derives a convergence condition. Under that condition, the iteration reaches the unique solution regardless of its initial guess.

2 Suggested iterative method and its convergence

  • The method uses the splitting K = P − R, with S = BA^-1B⊤ and Q = CS^-1C⊤; for positive α and β, P is nonsingular.Source: §2 · p. 5
  • The splitting yields the stationary update x^(k+1) = Gx^(k) + c, where G = P^-1R and c = P^-1b.Source: §2 · p. 5
  • For α > 1/2, the iteration converges to the unique solution regardless of the initial guess.Source: §2 · p. 5
  • The convergence argument considers eigenpairs of G through the relation Rv = λPv and uses the nonzero second eigenvector component in its proof.Source: §2 · pp. 5–6

3 The spectral properties of the preconditioned matrix

The section characterizes eigenpairs of the preconditioned matrix across parameter cases and establishes a polynomial relation that yields a two-iteration GMRES result when α = 1.

3 The spectral properties of the preconditioned matrix

  • The eigenpairs for eigenvalue 1 depend on the parameter cases, including conditions involving α, β, and αβ.The theorem gives corresponding eigenvector forms for these cases.Source: §3 · p. 6
  • When α = β = 1, K = P, so every nonzero vector is an eigenvector with eigenvalue 1.Source: §3 · p. 6
  • When α = 1, the minimal polynomial of P−1K has degree 2, and GMRES converges to the exact solution within two iterations.The stated polynomial relation is (λ − 1)²(λ − 1/α) = 0.Source: §3 · p. 7

4 Inexact block preconditioners for the matrix K

The section presents three inexact preconditioner variants and analyzes how their approximations affect the spectrum. It reports eigenvalue clustering around 1 under stated conditions, supporting convergence of GMRES or FGMRES.

4 Inexact block preconditioners for the matrix K

  • The authors describe three inexact variants, using approximations ˆA; ˆA and ˆS; or ˆA, ˆS, and ˆQ.They analyze the eigenvalue distributions of the resulting preconditioned matrices separately.Source: §4 · pp. 7–8
  • For the inexact preconditioner in (19), all complex eigenvalues lie strictly inside the unit disk centered at 1, a clustering property the authors cite as justification for fast GMRES convergence.The parameters α and β can be tuned to reduce the disk radius.Source: §4 · p. 11
  • With sufficiently accurate approximations ˆA, ˆS, and ˆQ, eigenvalues satisfy |λ − 1|² ≤ 1 − δ for some δ > 0, supporting robust convergence of preconditioned FGMRES.The stated result covers both cases ¯Cy = 0 and ¯C ≠ 0.Source: §4 · pp. 11, 14
  • The inexact preconditioner is applied by computing v = ˆP−1w in each Krylov iteration through a linear-system solve.The section presents an algorithm for this computation.Source: §4 · p. 14

5 Numerical experiments

The experiments evaluate the proposed preconditioner with GMRES and FGMRES across three examples. The reported comparisons favor it over the alternatives in accuracy, iteration counts, or CPU time, with performance varying by example and α.

Example 1

  • At problem size 262411, GMRES with Q(α = 0.5) stagnated at relative residual 1.37 × 10−7, above the 10−7 stopping criterion; ˆP achieved higher accuracy than P̄ and Q.The Example 1 results also show ˆP⁻¹K eigenvalues more tightly clustered around 1 than those of K.Source: §5 · p. 16, Figure 1 · p. 16, Table 1 · p. 17
  • Example 1’s IT and CPU time stayed nearly flat for α = 0.5–10.The iteration count and CPU time showed little sensitivity to α over this interval.Source: §5 · p. 16, Figure 2 · p. 17

Example 2

  • In Example 2, ˆP required fewer iterations and less CPU time than P̄ and Q, and its preconditioned eigenvalues clustered.The comparisons used GMRES and FGMRES; the eigenvalue distribution is reported for h = 1/16.Source: §5 · p. 19, Figure 3 · p. 19, Table 3 · p. 20
  • In Example 2, IT fell from 14 to 10, rose to 13, then stayed near 13 for α ≥ 3; CPU time stabilized around 0.81.The CPU time first decreased from 0.89 to 0.62, then fluctuated slightly before stabilizing.Source: §5 · p. 19, Figure 4 · p. 22

Example 3

  • In Example 3, GMRES with ˆP outperformed P̄ in iterations and CPU time, was slightly better than Q, and FGMRES achieved better CPU times than Q.Numerical comparisons covered different values of p.Source: §5 · p. 22, Table 5 · p. 23, Table 6 · p. 23
  • In Example 3, for α ≥ 0.5, IT increased steadily from 12 to 50, while CPU time rose proportionally.The reported trend had no abrupt fluctuations or divergence.Source: §5 · p. 22, Figure 6 · p. 24

6 Conclusions and possible extensions for future work

The paper reports theoretical and numerical effectiveness for a class of three-by-three saddle point problems. It identifies extensions to more general block systems, adaptive parameter selection, and parallel implementations as future work.

6 Conclusions and possible extensions for future work

  • The biparametric LU-based iteration imposes convergence provisions involving only one parameter, and its induced preconditioner’s corresponding eigenpairs are derived.Source: §6 · pp. 24–25
  • Theoretical and numerical results demonstrate the framework’s effectiveness for a class of three-by-three saddle point problems.Source: §6 · p. 25
  • Extending the preconditioner to block systems with multiple saddle-point constraints and more complex coupling structures remains future work.Source: §6 · p. 25
  • An adaptive strategy for selecting α and β using spectral information, convergence behavior, or inexpensive matrix-property estimates is proposed as future work.Such a strategy could reduce manual parameter tuning and improve efficiency.Source: §6 · p. 25
  • Parallel implementations for large-scale saddle point problems are a future direction aimed at reducing computational cost and improving scalability.Source: §6 · p. 25
Loading 2609.12615v1…