Naslov
Deflation for the Symmetric Arrowhead and Diagonal-Plus-Rank-One Eigenvalue Problems

Autori
Barlow, Jesse L. ; Eisenstat, Stanley C. ; Jakovčević Stor, Nevena ; Slapničar, Ivan

Izvornik
SIAM Journal on Matrix Analysis and Applications (0895-4798) 43 (2022), 2; 681-709

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
symmetric arrow matrix ; diagonal-plus-rank-one matrix ; eigenvalue deflation ; Krylov-Schur ; symmetric Lanczos algorithm

Sažetak
We discuss the eigenproblem for the symmetric arrowhead matrix $C = (\begin{;smallmatrix}; D \& {;z}; {;z};^T & \alpha \end{;smallmatrix};)$, where $D \in \mathbb{;R};^{;n \times n};$ is diagonal, ${;z}; \in \mathbb{;R};^n$, and $\alpha \in \mathbb{;R};$, 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 ${;\mathcal{;O};(n^2)};$ comparisons. Although it is too costly for many applications, when we use it as a benchmark, we can analyze the effectiveness of ${;{;O};(n)};$ heuristics that are more practical approaches to deflation. We show that one such ${;\mathcal{;O};(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 ${;\mathcal{;O};(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 ${;\mathcal{;O};(n)};$ heuristic finds nearly as much deflation as the ${;\mathcal{;O};(n^2)};$ 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA