Jesse L. Barlow, Stanley C. Eisenstat, Nevena Jakovcevicstor, Ivan Slapnicar

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)681-709
Number of pages29
JournalSIAM Journal on Matrix Analysis and Applications
Issue number2
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Analysis


Dive into the research topics of 'DEFLATION for the SYMMETRIC ARROWHEAD and DIAGONAL-PLUS-RANK-ONE EIGENVALUE PROBLEMS'. Together they form a unique fingerprint.

Cite this