Deflation for the Symmetric Arrowhead and Diagonal-Plus-Rank-One Eigenvalue Problems
| Autor: | Barlow, Jesse L., Eisenstat, Stanley C., Jakovčević Stor, Nevena, Slapničar, Ivan |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | SIAM Journal on Matrix Analysis and Applications. 43:681-709 |
| ISSN: | 1095-7162 0895-4798 |
| DOI: | 10.1137/21m139205x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|