11 papers
Accelerating preconditioned Jacobi methods via perturbation-inspired pivoting
Nian Shao, Yuji Nakatsukasa
Perturbation theory for symmetric matrices shows that eigenvalues with small spectral gaps are more sensitive to off-diagonal perturbation, implying that different entries affect t…
Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent
Nian Shao, Yuji Nakatsukasa
Given a holomorphic matrix-valued function, the poles of its sketched resolvent are generically its eigenvalues. Once a good rational approximation of the sketched resolvent is obt…
Linear convergence of iterative contour integral-based eigensolvers for nonlinear eigenvalue problems
Daniel Kressner, Yuqi Liu, Jose E. Roman +2
Solving nonlinear eigenvalue problems is an important and challenging task in scientific computing. Contour integral-based approaches are attractive for such eigenvalue problems be…
Stabilizing the Rayleigh--Ritz procedure by randomization
Nian Shao
Extracting approximate eigenpairs from a prescribed subspace is of fundamental importance in eigenvalue computation. Although the standard Rayleigh--Ritz procedure is widely used f…
Lanczos with compression for symmetric eigenvalue problems
Angelo A. Casulli, Daniel Kressner, Nian Shao
The Lanczos method with implicit restarting is one of the most popular methods for finding a few exterior eigenpairs of a large symmetric matrix . Usually based on polynomial fi…
Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions
Laura Grigori, Daniel Kressner, Nian Shao +1
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…
A structural bound for cluster robustness of randomized small-block Lanczos
Nian Shao
The Lanczos method is a fast and memory-efficient algorithm for solving large-scale symmetric eigenvalue problems. However, its rapid convergence can deteriorate significantly when…
A preconditioned inverse iteration with an improved convergence guarantee
Foivos Alimisis, Daniel Kressner, Nian Shao +1
Preconditioned eigenvalue solvers offer the possibility to incorporate preconditioners for the solution of large-scale eigenvalue problems, as they arise from the discretization of…
On a randomized small-block Lanczos method for large-scale null space computations
Daniel Kressner, Nian Shao
Computing the null space of a large sparse matrix is a challenging computational problem, especially if the nullity -- the dimension of the null space -- is not small. When app…
EPIC: a provable accelerated Eigensolver based on Preconditioning and Implicit Convexity
Nian Shao, Wenbin Chen, Zhaojun Bai
This paper is concerned with the extraction of the smallest eigenvalue and the corresponding eigenvector of a symmetric positive definite matrix pencil. We reveal implicit convexit…
Riemannian Acceleration with Preconditioning for symmetric eigenvalue problems
Nian Shao, Wenbin Chen
The analysis of the acceleration behavior of gradient-based eigensolvers with preconditioning presents a substantial theoretical challenge. In this work, we present a novel framewo…