Source-linked AI summary
A variant of the block preconditioner for indefinite complex symmetric linear systems
Mehdi Makhdomi, Davod Khojasteh Salkuyeh
TL;DR
The paper targets large sparse complex symmetric systems with an indefinite symmetric part, where direct factorization is costly and preconditioner quality affects iterative convergence. It proposes the VBP block preconditioner, analyzes its convergence and preconditioned spectrum, and reports that experiments found it more computationally efficient and robust than the compared preconditioners.
Problem
Large sparse complex symmetric systems with an indefinite W are difficult for direct solvers because factorization can cause severe fill-in, while Krylov convergence depends heavily on preconditioner quality.
Method
The paper derives the VBP preconditioner by matrix splitting, analyzes its stationary iteration and preconditioned-matrix spectral properties, and applies it with FGMRES.
Results
Numerical experiments confirm that VBP outperforms the other considered preconditioners in computational efficiency and robustness.
Takeaways & Limitations
VBP provides a block-preconditioning approach for the targeted complex symmetric indefinite systems, with convergence guaranteed under the analyzed parameter condition.
Takeaways & Limitations
The analysis assumes W is symmetric indefinite and T is symmetric positive definite.
Abstract
from arXiv · showhide
In this paper, we propose an efficient preconditioner for solving indefinite complex symmetric linear systems within a block preconditioning framework. We analyze the convergence of the corresponding iterative method and investigate several spectral properties of the preconditioned matrix, including eigenvalue distributions and eigenvector structures. The new preconditioner is used to accelerate the convergence of the flexible version of GMRES. Numerical experiments are presented to illustrate the effectiveness of the proposed preconditioner, and comparisons with existing block preconditioners demonstrate its superior performance.
1 Introduction
The paper addresses large sparse complex symmetric linear systems with an indefinite symmetric part, where direct solvers suffer from fill-in and iterative methods require effective preconditioners. It introduces the VBP preconditioner for a real 2×2 block formulation and situates it among existing approaches.
- The complex system A x = d is reformulated as an equivalent real 2×2 block system by decomposing x and d into real and imaginary parts.
- The paper assumes W is symmetric indefinite and T is symmetric positive definite.
- Direct factorization of the large sparse 2×2 block system typically causes severe fill-in, prohibitive memory requirements, and degraded computational efficiency.
- Iterative Krylov methods such as GMRES and FGMRES preserve sparsity because they rely on matrix-vector multiplications.
- The proposed VBP preconditioner is derived from matrix splitting for large sparse 2×2 block complex symmetric indefinite systems.
- The study analyzes convergence and spectral properties, selects parameters, and evaluates VBP against VHSS, BS, and MBP in numerical experiments.
2 The VBP preconditioner and convergence analysis
This section constructs the VBP preconditioner and its stationary iteration, explains its implementation within GMRES or FGMRES, and analyzes convergence through the iteration matrix. Under a condition on α, the method converges, while γ does not affect the theoretical convergence or spectral analysis but helps numerically.
- The VBP preconditioner is introduced using parameters α > 0 and γ > 0 through a block matrix-splitting construction.
- Applying VBP within GMRES or FGMRES requires solving internal systems involving αI + T and T, both of which are symmetric positive definite.
- VBP iteration converges to the exact solution precisely when the iteration matrix has spectral radius below one.
- Under the stated condition on α, the iterative scheme converges to the unique solution for any initial guess.
- The convergence analysis establishes that the iteration matrix has real eigenvalues lying between −1 and 1 when the condition holds.
- The parameter γ does not influence theoretical convergence or preconditioned-matrix spectral properties, but it is effective in numerical experiments.
3 Eigenvalue analysis of P−1 VBPA
The analysis characterizes the preconditioned matrix through its eigenvalues, eigenvectors, and minimal polynomial. Its spectrum includes eigenvalue 1 and remaining real positive eigenvalues, while GMRES terminates in at most n + 1 steps in exact arithmetic.
- Eigenvalue distribution: The eigenvalues of the preconditioned matrix are related to those of the iteration matrix by ζ = 1 − λ.This connects the spectral analysis of the preconditioner with convergence analysis of the associated iteration.
- Eigenvalue distribution: The preconditioned matrix has eigenvalue 1 with algebraic multiplicity at least n, while remaining eigenvalues are real, positive, and lie in a specified interval.These remaining eigenvalues coincide with those of Θ1.
- Eigenvector structure: The eigenvector analysis distinguishes ζ = 1 from ζ ≠ 1 and establishes n + r linearly independent eigenvectors.For ζ = 1, there are exactly n linearly independent eigenvectors; the complete set contains n + r vectors.
- Krylov convergence: The minimal polynomial of the preconditioned matrix has degree at most n + 1.The result follows from the block upper triangular representation and the characteristic polynomial of Θ1.
- Krylov convergence: GMRES with the VBP preconditioner terminates in exact arithmetic in at most n + 1 steps for any right-hand side d.This conclusion follows directly from the minimal-polynomial bound.
4 Parameter selection
The preconditioner’s efficiency depends strongly on α and γ, motivating parameter estimation. The paper selects quasi-optimal values by minimizing the distance between the preconditioner and the original matrix, while treating γ as fixed when optimizing α.
- Parameter sensitivity: The overall efficiency of the PVBP is highly sensitive to the parameters α and γ.Effective parameter estimation is therefore needed within the VBP framework.
- Quasi-optimal estimation: Parameter selection minimizes the distance between the preconditioner PVBP and the original coefficient matrix A.The paper uses an algebraic estimation technique proposed by Huang.
- Quasi-optimal estimation: The quasi-optimal parameter α is obtained by minimizing f(α, γ) while treating γ as a constant.This yields an analytical expression for α within the VBP preconditioner.
5 Numerical Experiments
Numerical experiments compare PVBP with PBS, PVHSS, and PMBP on two complex symmetric indefinite systems. PVBP produces tightly clustered positive-real spectra, fast FGMRES convergence, and low sensitivity to parameter choices.
- Experimental setup: Experiments use FGMRES with inexact CG inner solves, three grid sizes, zero initial guesses, and averaged timing and iteration measurements.FGMRES uses a relative residual tolerance of 10^-6; inner CG uses tolerance 10^-2 and at most 500 iterations.
- Test problems: The test problems use finite-difference complex symmetric systems whose matrix W is symmetric indefinite under the selected parameter settings.Example 1 uses a five-point centered-difference negative Laplacian on a unit square; experiments set τ = 1 and ω = 10, 20.
- Spectral behavior: PVBP eigenvalues lie entirely in the positive real interval [1, 1.19], matching the theoretical spectral result.For Example 1, the eigenvalues are also significantly more tightly clustered around (1, 0) than those of PBS, PVHSS, and PMBP.
- Example 1: PVBP achieves the fewest FGMRES iterations and shortest CPU time across all tested grid levels in Example 1.The comparison covers τ = 1 with ω = 10 and ω = 20.
- Example 1: VBP-preconditioned FGMRES remains low-iteration across a wide range of α and γ values in Example 1.This indicates insensitivity to parameter variations on the 32 × 32 grid.
- Example 2: In Example 2, PVBP consistently yields the lowest iteration counts and least computational time for all tested grid resolutions.The comparisons use parameter pairs (τ = 10, ω = 10) and (τ = 10, ω = 20).
6 Conclusions
The paper proposes a matrix-splitting variant of the block preconditioner, analyzes convergence and spectral properties, and reports superior computational efficiency and robustness in numerical experiments.
- The proposed variant of the block preconditioner is based on a matrix splitting of the coefficient matrix.
- The corresponding stationary iterative method is analyzed for convergence, while the preconditioned matrix is investigated for spectral properties.
- Numerical experiments report that the proposed preconditioner outperforms the other considered preconditioners in computational efficiency and robustness.
- Table 8 compares FGMRES performance across different preconditioning strategies for Example 2 with τ = 10 and ω = 20.