Deflation for the Symmetric Arrowhead and Diagonal-plus-rank-one Eigenvalue Problems

We discuss the eigenproblem for the symmetric arrowhead matrix C = (\bfzDT \alpha\bfz ), where D \in \BbbR n\times n is diagonal, z \in \BbbR n, and \alpha \in \BbbR, in order to examine criteria for when components of z may be set to zero. We show that whenever two eigenvalues of C are sufficiently close, some component of z may be deflated to zero, without significantly perturbing the eigenvalues of C, by either substituting zero for that component or performing a Givens rotation on each side of C. The strategy for this deflation requires \scrO (n2) comparisons. Although it is too costly for many applications, when we use it as a benchmark, we can analyze the effectiveness of \scrO (n) heuristics that are more practical approaches to deflation. We show that one such \scrO (n) heuristic finds all sets of three or more nearby eigenvalues, misses sets of two or more nearby eigenvalues under limited circumstances, and produces a reduced matrix whose eigenvalues are distinct in double the working precision. Using the \scrO (n) heuristic, we develop a more aggressive method for finding converged eigenvalues in the symmetric Lanczos algorithm. It is shown that except for pathological exceptions, the \scrO (n) heuristic finds nearly as much deflation as the \scrO (n2) algorithm that reduces an arrowhead matrix to one that cannot be deflated further. The deflation algorithms and their analysis are extended to the symmetric diagonal-plus-rank-one eigenvalue problem and lead to a better deflation strategy for the LAPACK routine dstedc.f.

Files

Metadata

Work Title Deflation for the Symmetric Arrowhead and Diagonal-plus-rank-one Eigenvalue Problems
Access
Open Access
Creators
  1. Jesse L. Barlow
  2. Stanley C. Eisenstat
  3. Nevena Jakovcevicstor
  4. Ivan Slapnicar
Keyword
  1. Symmetric arrowhead matrix
  2. Diagonal-plus-rank-one matrix
  3. Eigenvalue deflation
  4. Krylov-Schur
  5. Symmetric Lanczos algorithm
License In Copyright (Rights Reserved)
Work Type Article
Publisher
  1. SIAM Journal on Matrix Analysis and Applications
Publication Date May 2, 2021
Publisher Identifier (DOI)
  1. https://doi.org/10.1137/21M139205X
Deposited May 25, 2023

Versions

Analytics

Collections

This resource is currently not in any collection.

Work History

Version 1
published

  • Created
  • Added deflation_notes10_rev.pdf
  • Added Creator Jesse L. Barlow
  • Added Creator Stanley C. Eisenstat
  • Added Creator Nevena Jakovcevicstor
  • Added Creator Ivan Slapnicar
  • Published
  • Updated Work Title, Keyword, Publication Date Show Changes
    Work Title
    • DEFLATION for the SYMMETRIC ARROWHEAD and DIAGONAL-PLUS-RANK-ONE EIGENVALUE PROBLEMS
    • Deflation for the Symmetric Arrowhead and Diagonal-plus-rank-one Eigenvalue Problems
    Keyword
    • Symmetric arrowhead matrix, Diagonal-plus-rank-one matrix, Eigenvalue deflation, Krylov-Schur, Symmetric Lanczos algorithm
    Publication Date
    • 2022-01-01
    • 2021-05-02
  • Updated