Randomized implicitly restarted Arnoldi method for the non-symmetric eigenvalue problem

DOI10.1137/24M1674352MaRDI QIDQ6902500zbMATH OpenFDO

Authors Jean-Guillaume de Damas, Laura Grigori

Publication date 11 November 2025

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1674352

zbMATH Keywords

Krylov subspace methodsnonsymmetric eigenvalue problemrandomizationrestarting Arnoldi

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Orthogonalization in numerical linear algebra (65F25)

Review text

This interesting paper studies a randomized implicitly restarted Arnoldi method for the non-symmetric eigenvalue problem. The context of the problem is the following. Consider the eigenvalue/eigenvector equation \(Au=\lambda u\) where \(A\in \mathbb R^{n\times n}\), \(u\in \mathbb R^n\), \(||u||=1\) and \(\lambda \in \mathbb C\). As is well known, the problem of finding the eigenvalues and/or eigenvectors of a given linear transformation has many applications in science and engineering.\N\NThis paper deals with the computation of a small subset of eigenpairs of a matrix \(A\) that may be large, sparse and nonsymmetric. The authors introduce a randomized algorithm for solving the nonsymmetric eigenvalue problem referred to as a randomized Implicitly Restarted Arnoldi method. Their method uses a sketch-orthogonal basis during the Arnoldi process while maintaining the Arnoldi relation and using in addition, a restarting scheme to focus on a certain part of the spectrum.\N\NThe paper is well written with a good set of references.

Cites work

• A key to choose subspace size in implicitly restarted Arnoldi method
• ARPACK Users' Guide
• Complex shift and invert strategies for real matrices
• Deflation Techniques for an Implicitly Restarted Arnoldi Iteration
• Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Further analysis of the Arnoldi process for eigenvalue problems
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
• Implicit Shifting in the QR and Related Algorithms
• Julia: a fresh approach to numerical computing
• Nearly tight oblivious subspace embeddings by trace inequalities
• Numerical methods for large eigenvalue problems
• On restarting the Arnoldi method for large nonsymmetric eigenvalue problems
• Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen-Loève expansion.
• Randomized flexible GMRES with deflated restarting
• Randomized Gram-Schmidt process with application to GMRES
• Randomized numerical linear algebra: Foundations and algorithms
• Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
• Sketching as a tool for numerical linear algebra
• The AAA algorithm for rational approximation
• The Advantages of Inverted Operators in Rayleigh–Ritz Approximations
• The distance of an eigenvector to a Krylov subspace and the convergence of the Arnoldi method for eigenvalue problems
• The Johnson-Lindenstrauss Transform: An Empirical Study
• The University of Florida sparse matrix collection

Cited in

(1)

• Randomized Householder QR

This page was built for publication: Randomized implicitly restarted Arnoldi method for the non-symmetric eigenvalue problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902500)