full
search.png

Search

close.png

Cancel

arrow
Volume 36, Issue 5
Convergence Analysis of a Locally Accelerated Preconditioned Steepest Descent Method for Hermitian-Definite Generalized Eigenvalue Problems

Yunfeng Cai, Zhaojun Bai, John E. Pask & N. Sukumar

DOI: 10.4208/jcm.1703-m2016-0580

J. Comp. Math., 36 (2018), pp. 739-760.

Published online: 2018-06

Preview Purchase PDF 1283 25584

Cited by

google scholar semantic scholar
Export citation
  • Abstract

By extending the classical analysis techniques due to Samokish, Faddeev and Faddeeva, and Longsine and McCormick among others, we prove the convergence of the preconditioned steepest descent with implicit deflation (PSD-id) method for solving Hermitian-definite generalized eigenvalue problems. Furthermore, we derive a nonasymptotic estimate of the rate of convergence of the PSD-id method. We show that with a proper choice of the shift, the indefinite shift-and-invert preconditioner is a locally accelerated preconditioner, and is asymptotically optimal that leads to superlinear convergence. Numerical examples are presented to verify the theoretical results on the convergence behavior of the PSD-id method for solving ill-conditioned Hermitian-definite generalized eigenvalue problems arising from electronic structure calculations. While rigorous and full-scale convergence proofs of the preconditioned block steepest descent methods in practical use still largely elude us, we believe the theoretical results presented in this paper shed light on an improved understanding of the convergence behavior of these block methods.

  • Keywords

Eigenvalue problem, Steepest descent method, Preconditioning, Superlinear convergence.

  • AMS Subject Headings

65F08, 65F15, 65Z05, 15A12

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

yfcai@math.pku.edu.cn (Yunfeng Cai)

bai@cs.ucdavis.edu (Zhaojun Bai)

pask1@llnl.gov (John E. Pask)

nsukumar@ucdavis.edu (N. Sukumar)

  • BibTex
  • RIS
  • TXT
@Article{JCM-36-739, author = {Cai , YunfengBai , ZhaojunPask , John E. and Sukumar , N.}, title = {Convergence Analysis of a Locally Accelerated Preconditioned Steepest Descent Method for Hermitian-Definite Generalized Eigenvalue Problems}, journal = {Journal of Computational Mathematics}, year = {2018}, volume = {36}, number = {5}, pages = {739--760}, abstract = {

By extending the classical analysis techniques due to Samokish, Faddeev and Faddeeva, and Longsine and McCormick among others, we prove the convergence of the preconditioned steepest descent with implicit deflation (PSD-id) method for solving Hermitian-definite generalized eigenvalue problems. Furthermore, we derive a nonasymptotic estimate of the rate of convergence of the PSD-id method. We show that with a proper choice of the shift, the indefinite shift-and-invert preconditioner is a locally accelerated preconditioner, and is asymptotically optimal that leads to superlinear convergence. Numerical examples are presented to verify the theoretical results on the convergence behavior of the PSD-id method for solving ill-conditioned Hermitian-definite generalized eigenvalue problems arising from electronic structure calculations. While rigorous and full-scale convergence proofs of the preconditioned block steepest descent methods in practical use still largely elude us, we believe the theoretical results presented in this paper shed light on an improved understanding of the convergence behavior of these block methods.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1703-m2016-0580}, url = {http://global-sci.org/intro/article_detail/jcm/12455.html} }
TY - JOUR T1 - Convergence Analysis of a Locally Accelerated Preconditioned Steepest Descent Method for Hermitian-Definite Generalized Eigenvalue Problems AU - Cai , Yunfeng AU - Bai , Zhaojun AU - Pask , John E. AU - Sukumar , N. JO - Journal of Computational Mathematics VL - 5 SP - 739 EP - 760 PY - 2018 DA - 2018/06 SN - 36 DO - http://doi.org/10.4208/jcm.1703-m2016-0580 UR - https://global-sci.org/intro/article_detail/jcm/12455.html KW - Eigenvalue problem, Steepest descent method, Preconditioning, Superlinear convergence. AB -

By extending the classical analysis techniques due to Samokish, Faddeev and Faddeeva, and Longsine and McCormick among others, we prove the convergence of the preconditioned steepest descent with implicit deflation (PSD-id) method for solving Hermitian-definite generalized eigenvalue problems. Furthermore, we derive a nonasymptotic estimate of the rate of convergence of the PSD-id method. We show that with a proper choice of the shift, the indefinite shift-and-invert preconditioner is a locally accelerated preconditioner, and is asymptotically optimal that leads to superlinear convergence. Numerical examples are presented to verify the theoretical results on the convergence behavior of the PSD-id method for solving ill-conditioned Hermitian-definite generalized eigenvalue problems arising from electronic structure calculations. While rigorous and full-scale convergence proofs of the preconditioned block steepest descent methods in practical use still largely elude us, we believe the theoretical results presented in this paper shed light on an improved understanding of the convergence behavior of these block methods.

Yunfeng Cai, Zhaojun Bai, John E. Pask & N. Sukumar. (2020). Convergence Analysis of a Locally Accelerated Preconditioned Steepest Descent Method for Hermitian-Definite Generalized Eigenvalue Problems. Journal of Computational Mathematics. 36 (5). 739-760. doi:10.4208/jcm.1703-m2016-0580
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard