TY - JOUR

T1 - DEFLATION for the SYMMETRIC ARROWHEAD and DIAGONAL-PLUS-RANK-ONE EIGENVALUE PROBLEMS

AU - Barlow, Jesse L.

AU - Eisenstat, Stanley C.

AU - Jakovcevicstor, Nevena

AU - Slapnicar, Ivan

N1 - Funding Information:
\ast Received by the editors January 14, 2021; accepted for publication (in revised form) October 22, 2021; published electronically May 2, 2022. https://doi.org/10.1137/21M139205X Funding: Research of Nevena Jakov\cv evi\c' Stor and Ivan Slapni\cv ar was supported in part by the Croatian Science Foundation grants iP-2014009-9540 and IP-2020-02-2240. \dagger Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA 16802 USA (barlow@cse.psu.edu). \ddagger Department of Computer Science, Yale University, New Haven, CT 06520-8285 USA. \S Faculty of Electrical Engineering, Mechanical Engineering, and Naval Architecture, University of Split, Split 21000, Croatia (nevena@fesb.hr). \P University of Split, Split 21000, Croatia (slap@fesb.hr).
Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85130520275&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130520275&partnerID=8YFLogxK

U2 - 10.1137/21M139205X

DO - 10.1137/21M139205X

M3 - Article

AN - SCOPUS:85130520275

SN - 0895-4798

VL - 43

SP - 681

EP - 709

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -