On the stability of basis construction in extended Krylov subspace methods
Abstract
Extended Krylov subspace methods (EKSMs) are a well known approach for approximating the action of a matrix function on a vector f(A)b, and their block versions are often used for solving Lyapunov and Sylvester matrix equations. EKSMs produce Laurent approximations to the underlying operator, which are generally more accurate per iteration than polynomial KSMs, without requiring a pole selection procedure as rational KSMs do. At the same time, due to the expansion of the search space by not only A but also by its inverse, a number of implementation choices must be made that can affect the stability of the algorithm in floating-point arithmetic. We concentrate on two variants that often appear in the literature and in code, based on whether new basis vectors are built via what we denote as ``mixed channels" or ``split channels." We characterize their loss of orthogonality with an easily computable metric and prove that when A is symmetric positive definite, mixed channels have better orthogonality than split channels; however, numerical experiments demonstrate that straightforward predictions are not possible for indefinite or nonsymmetric matrices. We also provide a modular MATLAB toolbox, \texttt{ektoolbox}, that contains new versions of EKSMs with low-synchronization Gram-Schmidt backbones.
Related
- Factorized Krylov subspace methods for solving large Sylvester equations
- Randomized Krylov Subspace Methods for Shifted Linear Systems
- pqSEDMD: Subspace Methods for Extended Dynamic Mode Decomposition Identification
- Efficient construction of subspace design codes over constant alphabet
- Finite-Precision Symmetric Krylov Methods: Exact Rounding Examples, Block Paige Identities,and a Variable-Block Lanczos Model
BibTeX
@misc{lund2026stability,
title = {{On the stability of basis construction in extended Krylov subspace methods}},
author = {Kathryn Lund and Marcel Schweitzer},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21603},
eprint = {2610.21603},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21603},
}
RIS
TY - UNPB
TI - On the stability of basis construction in extended Krylov subspace methods
AU - Kathryn Lund
AU - Marcel Schweitzer
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21603
UR - https://arxiv.org/abs/2610.21603
AB - Extended Krylov subspace methods (EKSMs) are a well known approach for approximating the action of a matrix function on a vector f(A)b, and their block versions are often used for solving Lyapunov and Sylvester matrix equations. EKSMs produce Laurent approximations to the underlying operator, which are generally more accurate per iteration than polynomial KSMs, without requiring a pole selection procedure as rational KSMs do. At the same time, due to the expansion of the search space by not only A but also by its inverse, a number of implementation choices must be made that can affect the stability of the algorithm in floating-point arithmetic. We concentrate on two variants that often appear in the literature and in code, based on whether new basis vectors are built via what we denote as ``mixed channels" or ``split channels." We characterize their loss of orthogonality with an easily computable metric and prove that when A is symmetric positive definite, mixed channels have better orthogonality than split channels; however, numerical experiments demonstrate that straightforward predictions are not possible for indefinite or nonsymmetric matrices. We also provide a modular MATLAB toolbox, \texttt{ektoolbox}, that contains new versions of EKSMs with low-synchronization Gram-Schmidt backbones.
ER -