arrow
Volume 37, Issue 6
Block Algorithms with Augmented Rayleigh-Ritz Projections for Large-Scale Eigenpair Computation

Haoyang Liu, Zaiwen Wen, Chao Yang & Yin Zhang

J. Comp. Math., 37 (2019), pp. 889-915.

Published online: 2019-11

Export citation
  • 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. 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 $C$ on a representative set of test problems to evaluate the performance of two variants of our algorithm. 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 that of several state-of-the-art eigensolvers.

  • AMS Subject Headings

65F15, 90C06

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

liuhaoyang@pku.edu.cn (Haoyang Liu)

wenzw@pku.edu.cn (Zaiwen Wen)

cyang@lbl.gov (Chao Yang)

yzhang@rice.edu (Yin Zhang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-37-889, author = {Liu , HaoyangWen , ZaiwenYang , Chao and Zhang , Yin}, title = {Block Algorithms with Augmented Rayleigh-Ritz Projections for Large-Scale Eigenpair Computation}, journal = {Journal of Computational Mathematics}, year = {2019}, volume = {37}, number = {6}, pages = {889--915}, 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. 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 $C$ on a representative set of test problems to evaluate the performance of two variants of our algorithm. 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 that of several state-of-the-art eigensolvers.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1910-m2019-0034}, url = {http://global-sci.org/intro/article_detail/jcm/13381.html} }
TY - JOUR T1 - Block Algorithms with Augmented Rayleigh-Ritz Projections for Large-Scale Eigenpair Computation AU - Liu , Haoyang AU - Wen , Zaiwen AU - Yang , Chao AU - Zhang , Yin JO - Journal of Computational Mathematics VL - 6 SP - 889 EP - 915 PY - 2019 DA - 2019/11 SN - 37 DO - http://doi.org/10.4208/jcm.1910-m2019-0034 UR - https://global-sci.org/intro/article_detail/jcm/13381.html KW - Extreme eigenpairs, Augmented Rayleigh-Ritz projection. AB -

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. 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 $C$ on a representative set of test problems to evaluate the performance of two variants of our algorithm. 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 that of several state-of-the-art eigensolvers.

Liu , HaoyangWen , ZaiwenYang , Chao and Zhang , Yin. (2019). Block Algorithms with Augmented Rayleigh-Ritz Projections for Large-Scale Eigenpair Computation. Journal of Computational Mathematics. 37 (6). 889-915. doi:10.4208/jcm.1910-m2019-0034
Copy to clipboard
The citation has been copied to your clipboard