Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions

Laura Grigori, Daniel Kressner, Nian Shao, Igor Simunec · 2026

Read Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions by Laura Grigori, Daniel Kressner, Nian Shao, Igor Simunec (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10248.txt.

Introduction

Laura Grigori, Daniel Kressner, Nian Shao, and Igor Simunec fix a flaw in fast Krylov tools. Krylov tools build a base for a large space step by step. A random form builds that base fast and with a sound shape. But it warps a key link.

The matrix it yields should match the one from the plain path. In the random path, it oft does not. That gap can slow or spike the solve. The team give a fix that brings the link back. They show it on eigenvalue tasks and on functions of a matrix. The fix keeps the speed and the shape.

Catalog record

CREATORLaura Grigori, Daniel Kressner, Nian Shao, Igor Simunec
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10248

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions Laura Grigori, Daniel Kressner, Nian Shao, Igor Simunec Abstract The randomized Arnoldi process has been used in large-scale scientific computing because it produces a well-conditioned basis for the Krylov subspace more quickly than the standard Arnoldi process. However, the resulting Hessenberg matrix is generally not similar to the one produced by the standard Arnoldi process, which can lead to delays or spike-like irregularities in convergence. In this paper, we introduce a modification of the randomized Arnoldi process that restores similarity with the Hessenberg matrix generated by the standard Arnoldi process. This is accomplished by enforcing orthogonality between the last Arnoldi vector and the previously generated subspace, which requires solving only one additional least-squares problem. When applied to eigenvalue problems and matrix function evaluations, the modified randomized Arnoldi process produces approximations that are identical to those obtained with the standard Arnoldi process. Numerical experiments demonstrate that our approach is as fast as the randomized Arnoldi process and as robust as the standard Arnoldi process. keywords Krylov subspace methods, randomized sketching, eigenvalue problems, matrix functions † † runningheads: Similarity-restoring randomized Arnoldi / Laura Grigori, Daniel Kressner, Nian Shao, Igor Simunec AMS 65F15, 65F25, 65F60, 68W20 1 Introduction Krylov subspace methods are among the most effective approaches for solving large-scale problems, ranging from the solution of linear systems, to the computation of eigenvalues and evaluation of matrix functions. Given a square matrix A\in\mathbb{C}^{n\times n} and a nonzero initial vector b\in\mathbb{C}^{n} , the m th Krylov subspace associated with A and b is generated by repeatedly multiplying A with b : \mathcal{K}_{m}(A,b):=\mathsf{span}\{b,Ab,\dotsc,A^{m-1}b\}. The Arnoldi process [ 12 , Sec. 10.5] is used to construct an orthonormal basis Q_{m} for \mathcal{K}_{m}(A,b) , whose main costs are m matrix-vector products with A , and the orthogonalization of Q_{m} via a Gram–Schmidt process with complexity \mathcal{O}(nm^{2}) . In particular, orthogonalization may dominate the computational cost when m becomes (moderately) large. Several strategies have been considered in the literature to reduce this cost, including incomplete orthogonalization [ 26 ] and restarting [ 27 ] . Recently, randomized orthogonalization has been proposed to reduce the cost of orthogonalization in the Arnoldi process, for instance with a randomized Gram–Schmidt method [ 1 , 2 ] or with a randomized Householder QR decomposition [ 14 ] . Given a (low-dimensional) subspace \mathcal{W}\subset\mathbb{C}^{n} , the randomized Gram–Schmidt method employs a subspace embedding \Omega\in\mathbb{C}^{d\times n} to sketch vectors in \mathcal{W} to \mathbb{C}^{d} with d\ll n , while approximately preserving their norms. Compared to standard Gram–Schmidt, the computation and communication costs are reduced because inner products are formed with sketched vectors of length d rather than with original length- n vectors. Instead of an orthonormal basis Q_{m} , randomized Gram–Schmidt generates an \Omega -orthonormal basis U_{m} , that is, the columns of \Omega U_{m} form an orthonormal basis. When using high-quality random subspace embeddings, such as the ones surveyed in [ 21 , Sec. 2] , this ensures — with high probability — that U_{m} is a well-conditioned basis. During the last few years, the resulting randomized Arnoldi process has been employed for the solution of various large-scale problems [ 30 , 23 , 15 , 8 , 9 , 13 , 6 ] . For a recent overview, we refer to [ 7 ] . While its performance gains make randomized Arnoldi an attractive choice, the transition from orthonormality to \Omega -orthonormality incurs certain nuisances. An important feature of standard Arnoldi is that it not only returns an orthonormal basis Q_{m} but also the Hessenberg matrix G_{m}=Q_{m}^{\mathsf{H}}AQ_{m} . The latter plays a crucial role in algorithms; for example, the eigenvalues of G_{m} are the so called Ritz values that approximate eigenvalues of A . Randomized Arnoldi also returns such an m\times m Hessenberg matrix, but this matrix is, in general, not similar to G_{m} and, in particular, its eigenvalues are different. This discrepancy can lead to both numerical and theoretical difficulties. For example, one may obtain complex eigenvalue approximations even when A is Hermitian [ 9 ] . More subtle issues arise in the context of linear systems and matrix functions, where convergence may be delayed [ 15 ] or exhibit sporadic spikes [ 30 ] . Moreover, from a theoretical viewpoint, establishing convergence results becomes highly challenging [ 23 ] because the numerical range of the Hessenberg matrix is difficult to control, as it is no longer contained in the numerical range of A . All of these issues are caused by the lack of similarity between the Hessenberg matrices and can be resolved by restoring this property. In this work, we propose a modification of randomized Arnoldi that constructs a Hessenberg matrix similar to the one generated by standard Arnoldi. The key idea is to make all basis vectors \Omega -orthonormal except for the last one, which is instead orthogonal to all previous vectors. Such a basis can be obtained by performing randomized Gram–Schmidt, followed by the solution of a least-squares problem that enforces orthogonality of the last vector. This general framework enables us to recover, in exact arithmetic, the same approximate solutions as the ones obtained through standard Arnoldi, while still exploiting much of the efficiency of randomized Gram–Schmidt. We demonstrate this approach by applying it to the randomized Krylov–Schur algorithm for eigenvalue problems and the randomized Arnoldi method for computing the action of matrix functions f(A)b . For eigenvalue problems, in addition to establishing its equivalence with standard Krylov–Schur in exact arithmetic, we also prove a backward stability result analogous to that of the standard Krylov–Schur method in [ 28 ] . Let us remark that the application to matrix functions is closely related to one of the approaches considered in [ 6 ] ; see Remark 5 below for more details. The remainder of the manuscript is organized as follows. In section 2 we review the standard and randomized Arnoldi process and introduce our similarity-restoring correction to randomized Arnoldi. In section 3 we apply the proposed framework to the randomized Krylov–Schur algorithm for eigenvalue problems, and in section 4 we employ it for the computation of matrix functions. Numerical comparisons with both standard and randomized algorithms are presented in section 5 . 2 A new variant of the randomized Arnoldi process 2.1 Arnoldi and randomized Arnoldi process Arnoldi process We start by briefly recalling the standard Arnoldi process, which first normalizes the initial vector by setting q_{1}=b/\|b\| and then computes, for k=1,2,\ldots , the basis vector q_{k+1} by performing a matrix-vector product with A and one step of the (classical) Gram–Schmidt process: w=Aq_{k},\quad g_{k}=Q_{k}^{\mathsf{H}}w,\quad\widetilde{q}_{k+1}=w-Q_{k}g_{k},\quad g_{k+1,k}=\lVert\widetilde{q}_{k+1}\rVert,\quad q_{k+1}=\widetilde{q}_{k+1}/g_{k+1,k}. Here and in the following, we will ignore the rare (and usually fortunate) event that the Arnoldi process breaks down because of \widetilde{q}_{k+1}=0 . Performing m steps, collecting the vectors q_{k} in an orthonormal matrix Q_{m} and the coefficients g_{k},g_{k+1,k} in an upper Hessenberg matrix G_{m} , we obtain the Arnoldi decomposition AQ_{m}=Q_{m}G_{m}+g_{m+1,m}q_{m+1}e_{m}^{\mathsf{H}}, (2.1) where e_{m}\in\mathbb{C}^{m} denotes the m th unit vector. When A is Hermitian, the Arnoldi process reduces to the Lanczos process, and the Hessenberg matrix G_{m} becomes a tridiagonal Hermitian matrix. Randomized Arnoldi process As mentioned in the introduction, orthogonalization can dominate the computational cost

Read the complete text