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

Abstract

By extending the classical analysis techniques due to Samokish, Faddeev and Faddeeva, and Longsine and McCormick among others, we prove the convergence of 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 the 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.

Introduction

At the heart of many scientific simulations, particularly in quantum mechanics and structural engineering, lies the generalized eigenvalue problem: $Hu = \lambda Su$. Here, the goal is to find the eigenpairs $(\lambda, u)$ that satisfy this equation. While standard solvers exist, they often struggle with "ill-conditioned" problems—those where matrices are massive and sparse, eigenvalue gaps are tiny, or the matrix $S$ is nearly singular. Such problems are common in Partition-of-Unity Finite Element (PUFE) methods used for high-accuracy materials modeling.

This paper provides a rigorous mathematical foundation for the Preconditioned Steepest Descent with Implicit Deflation (PSD-id) method, offering the first formal convergence proof and nonasymptotic rate estimates for this class of algorithms.

The PSD-id Algorithm

The PSD-id method is an iterative approach that combines steepest descent with implicit deflation to find multiple eigenvalues sequentially. The core of the algorithm involves moving toward the solution by following the steepest gradient of the Rayleigh quotient, while ensuring the search remains orthogonal to previously discovered eigenpairs.

Algorithm 1: Preconditioned Steepest Descent with Implicit Deflation (PSD-id).

A critical component of this process is the preconditioner $K$. The authors analyze a flexible preconditioning strategy, specifically championing the indefinite shift-and-invert preconditioner: $\hat{K} = (H - \beta S)^{-1}$. While standard wisdom often suggests using positive-definite preconditioners, this research proves that an indefinite one, where the "shift" $\beta$ is updated as the algorithm progresses, becomes "locally accelerated."

Theoretical Insights and Convergence

The paper establishes two major theorems that rigorously prove convergence and provide a formula for the nonasymptotic rate. Key findings include:

  • Superlinear Convergence: Most iterative solvers converge at a constant linear rate. The authors prove that with the right shift-and-invert strategy, PSD-id achieves superlinear convergence—the error drops faster and faster as the algorithm approaches the true eigenvalue.
  • The Localization Condition: The authors identify a specific threshold where the approximate eigenvalue is close enough to the true value that the accelerated preconditioning kicks in.
  • Asymptotic Optimality: They demonstrate that an indefinite preconditioner is asymptotically optimal. It provides the necessary "boost" to resolve eigenvalues even when there is no clear spectral gap.

Numerical Validation

The theoretical results were verified using two primary numerical benchmarks:

  1. 1D Harmonic Oscillator: This classic Schrödinger equation problem demonstrated how PUFE discretization creates the exact type of ill-conditioning the PSD-id method is designed to solve.
  2. CeAl (Cerium-Aluminum) System: A real-world metallic triclinic system from electronic structure calculations. In this high-dimensional, extremely ill-conditioned problem (over 5,000 variables), the relative residual dropped from $10^{-2}$ to $10^{-10}$ in just a few iterations once the localization condition was met.

Conclusion and Future Work

While this work provides a definitive analysis for the single-vector PSD-id algorithm, the authors acknowledge that many high-performance computing applications utilize block methods (BPSD) to compute many eigenpairs simultaneously. A rigorous, full-scale convergence proof for these block methods remains an open challenge, but the insights gained from the PSD-id analysis provide a vital roadmap for future theoretical developments in the field.

Summary updated

Abstract

By extending the classical analysis techniques due to Samokish, Faddeev and Faddeeva, and Longsine and McCormick among others, we prove the convergence of 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 \psdid method. We show that with the 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 \psdid method for solving ill-conditioned Hermitian-definite generalized eigenvalue problems arising from electronic structure calculations. While rigorous and full-scale convergence proofs of preconditioned block steepest descent methods in practical use still largely eludes us, we believe the theoretical results presented in this paper sheds light on an improved understanding of the convergence behavior of these block methods.
BibTeX
@article{cai2018convergence,
  author = {Yunfeng Cai and Zhaojun Bai and John E. Pask and N. Sukumar},
  title = {{Convergence analysis of a locally accelerated preconditioned steepest descent method for Hermitian-definite generalized eigenvalue problems}},
  journal = {Journal of Computational Mathematics},
  year = {2018},
  doi = {10.4208/jcm.1703-m2016-0580},
}
Figure