Near-optimal convergence of Widlund's method and numerical exploration of different implementations

For linear systems arising from the discretization of certain classes of mathematical models, the splitting of the linear system into its Hermitian and skew-Hermitian parts has a physical meaning. If, in addition, the Hermitian part is positive definite, there exist Krylov subspace methods based on three-term recurrences where the Hermitian part is used as a preconditioner. Two such Krylov subspace methods are Widlund's method and Rapoport's method. In this paper we establish a ``near-optimal'' guarantee for the convergence of Widlund's method, showing that the overall convergence of Widlund's method is nearly as good as that of Rapoport's method. Specifically, we show that for every iteration $k$, there exists an iteration $j\leq k$ where the residual norm of Widlund's method is less than $\sqrt{k+1} $ times the residual norm of Rapoport's method at iteration $k$. This bound is sharp. We also provide a computational study on various implementations of Widlund's method in the exact and inexact cases, and show that certain implementations may stagnate while others do not, i.e., we look at the robustness of the different implementations. We recommend two implementations.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.23829
Primary Topic
Matrix Theory and Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Near-optimal convergence of Widlund's method and numerical exploration of different implementations

Daniel B. Szyld, Andrew J. Higgins, Logan O. Reed
arXiv (Cornell University)
Matrix Theory and Algorithms
preprint

Near-optimal convergence of Widlund's method and numerical exploration of different implementations

Daniel B. Szyld, Andrew J. Higgins, Logan O. Reed
preprint en

Abstract

For linear systems arising from the discretization of certain classes of mathematical models, the splitting of the linear system into its Hermitian and skew-Hermitian parts has a physical meaning. If, in addition, the Hermitian part is positive definite, there exist Krylov subspace methods based on three-term recurrences where the Hermitian part is used as a preconditioner. Two such Krylov subspace methods are Widlund's method and Rapoport's method. In this paper we establish a ``near-optimal'' guarantee for the convergence of Widlund's method, showing that the overall convergence of Widlund's method is nearly as good as that of Rapoport's method. Specifically, we show that for every iteration $k$, there exists an iteration $j\leq k$ where the residual norm of Widlund's method is less than $\sqrt{k+1} $ times the residual norm of Rapoport's method at iteration $k$. This bound is sharp. We also provide a computational study on various implementations of Widlund's method in the exact and inexact cases, and show that certain implementations may stagnate while others do not, i.e., we look at the robustness of the different implementations. We recommend two implementations.

arXiv (Cornell University)
Matrix Theory and Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon