Block algorithms with augmented Rayleigh-Ritz projections for large-scale eigenpair computation

DOI10.4208/JCM.1910-M2019-0034MaRDI QIDQ5127595zbMATH OpenOpenAlexFDO

Authors Haoyang Liu, Zaiwen Wen, Chao Yang, Yin Zhang

Publication date 27 October 2020

Published in Journal of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.06078

zbMATH Keywords

block algorithmsextreme eigenpairsaugmented Rayleigh-Ritz projection

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10)

Abstract: Most iterative algorithms for eigenpair computation consist of two main steps: a subspace update (SU) step that generates bases for approximate eigenspaces, followed by a Rayleigh-Ritz (RR) projection step that extracts approximate eigenpairs. So far the predominant methodology for the SU step is based on Krylov subspaces that builds orthonormal bases piece by piece in a sequential manner. In this work, we investigate block methods in the SU step that allow a higher level of concurrency than what is reachable by Krylov subspace methods. To achieve a competitive speed, we propose an augmented Rayleigh-Ritz (ARR) procedure and analyze its rate of convergence under realistic conditions. Combining this ARR procedure with a set of polynomial accelerators, as well as utilizing a few other techniques such as continuation and deflation, we construct a block algorithm designed to reduce the number of RR steps and elevate concurrency in the SU steps. Extensive computational experiments are conducted in Matlab on a representative set of test problems to evaluate the performance of two variants of our algorithm in comparison to two well-established, high-quality eigensolvers ARPACK and FEAST. Numerical results, obtained on a many-core computer without explicit code parallelization, show that when computing a relatively large number of eigenpairs, the performance of our algorithms is competitive with, and frequently superior to, that of the two state-of-the-art eigensolvers.

Recommendations

• Accelerating convergence by augmented Rayleigh-Ritz projections for large-scale eigenpair computation
• An iterative block Arnoldi algorithm with modified approximate eigenvectors for large unsymmetric eigenvalue problems
• A thick-restarted block Arnoldi algorithm with modified Ritz vectors for large eigenproblems
• Computing eigenpairs of Hermitian matrices in augmented Krylov subspace produced by Rayleigh quotient iterations
• Increasing the performance of the Jacobi-Davidson method by blocking

Cited in

(4)

• Accelerating convergence by augmented Rayleigh-Ritz projections for large-scale eigenpair computation
• An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations
• Projective block Lanczos algorithm for dense, Hermitian eigensystems
• Subspace methods with local refinements for eigenvalue computation using low-rank tensor-train format

This page was built for publication: Block algorithms with augmented Rayleigh-Ritz projections for large-scale eigenpair computation

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