Pith. sign in

REVIEW 2 major objections 4 minor 44 references

Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Definite Hermitian pencils can be diagonalized in near-matrix-multiplication time by a randomized, inverse-free divide-and-conquer algorithm that preserves definiteness at every recursion and beats the general pencil solver by a log factor.

desk verdict New shattering results for definite pencils, but the main algorithm as written overwrites the input before recursing—fixable, but load-bearing. read the letter →

arxiv 2505.21917 v1 pith:DGHIPBSG submitted 2025-05-28 math.NA cs.NA

James Demmel , Ioana Dumitriu , Ryan Schneider This is my paper
classification math.NAcs.NA MSC 15A2215B5765F15
keywords definitematrixpencilCrawfordnumbergeneralizedeigenvalueproblempseudospectralshatteringGaussianunitaryensembledivide-and-conquereigensolverinverse-freealgorithmsrandomizednumericallinearalgebra
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that the definite generalized eigenvalue problem—pairs of Hermitian matrices $(A,B)$ whose Crawford number $\gamma(A,B)$ is positive—admits a divide-and-conquer eigensolver that is both faster and more structure-aware than the fastest general pencil algorithm. The method randomizes by adding small structured perturbations (GUE or diagonal), proves that these preserve definiteness and shatter the real pseudospectrum, then recurses on subpencils $(U^H A U, U^H B U)$ so that real eigenvalues persist and spectral projectors can be computed by a faster Halley iteration. The headline result is a complexity of $O(n^{\omega_0} \log(n/\xi) \log(\log(n/\xi)+\log(n)\log(\gamma^{-1})))$ operations, replacing one log factor in the general bound with a log-log factor, at the cost of assuming a known lower bound $\gamma$ on the Crawford number. A sympathetic reader would care because definite pencils cover both the ordinary Hermitian eigenproblem and the symmetric-definite generalized eigenproblem with Gram-matrix weights, without requiring $A$ or $B$ to be positive definite, and because the inverse-free, parallel structure of the solver is preserved.

What carries the argument

The central machinery is the symmetric $\epsilon$-pseudospectrum $\Lambda^{\mathrm{sym}}_{\epsilon}(A,B)$, defined with Hermitian perturbations measured by $\sqrt{\|E\|_2^2+\|F\|_2^2}$, and its shattering by a grid of real points. The proof has four load-bearing pieces: (1) small GUE or diagonal random perturbations preserve definiteness and keep $\gamma(\tilde A,\tilde B) \ge \gamma(A,B)/2$; (2) random-matrix eigenvalue repulsion (from Minami and Aizenman et al.) guarantees a minimum gap $\omega = \mu^3\gamma(A,B)^2/n^5$; (3) a Bauer-Fike theorem for definite pencils confines the symmetric $\epsilon$-pseudospectrum to short intervals around the real eigenvalues; and (4) an eigenvector-conditioning bound $\kappa_2(X) \le \|(A,B)\|_2/\gamma(A,B)$ keeps the eigenvectors well conditioned. Recursion computes projectors with IF-DWH, an inverse-free dynamically weighted Halley iteration that implicitly approximates $\operatorname{sign}(B^{-1}A)$; because subproblems are formed as $(U^H A U, U^H B U)$, definiteness is preserved and the eigenvalues stay real. Lemma 4.1 is the trade-off that puts $\gamma$ in the complexity: at each level, $\epsilon$ must shrink by a factor $(1+\|(A,B)\|_2/\gamma)^{-1}$, so the number of Halley iterations depends on $\log(\gamma^{-1})$.

What would settle it

Run the full two-step algorithm on a family of definite pencils with $\gamma(A,B)$ a known polynomial in $n$, count the IF-DWH iterations needed at each recursive split, and compare the total operation count and failure rate against Corollary 4.4; a single pencil where the projector routine requires more than the stated $O(\log\log(\cdot))$ iterations, or where the failure probability exceeds $1-O(n^{-1})$, would falsify the claimed complexity.

Watch

Extended reading notes

Core claim

Corollary 4.4 is the paper's central claim: for any definite pencil $(A,B)$ with $\|A\|_2,\|B\|_2 \le 1$ and a known lower bound $\gamma \le \gamma(A,B)$, an exact-arithmetic randomized algorithm outputs an invertible $X$ and diagonal $\Lambda_A,\Lambda_B$ with $\|X^H A X - \Lambda_A\|_2 \le \xi$ and $\|X^H B X - \Lambda_B\|_2 \le \xi$, with probability at least $1 - O(n^{-1})$, in $O(n^{\omega_0} \log(n/\xi) \log(\log(n/\xi)+\log(n)\log(\gamma^{-1})))$ operations. The discovery is that pseudospectral shattering—the small random perturbation that regularizes eigenvalues and pseudospectra—can be done inside the Hermitian structure of a definite pencil, and that the resulting real eigenvalues unlock a faster projector computation. This makes the structured solver provably faster than the general divide-and-conquer algorithm it adapts, trading a $\log(n/\epsilon)$ factor for a $\log\log$ factor. The proof maintains definiteness at every recursion, so the spectrum remains real and the shattering grid becomes one-dimensional.

Load-bearing premise

The load-bearing premise is that a known lower bound $\gamma$ on the Crawford number is available and is not too small relative to $n$ and $\xi$, and that the projector subroutine inherited from the general framework converges in the promised number of iterations on every subproblem the recursion generates; if either fails, the complexity guarantee collapses.

Editorial extensions

If this is right

  • For definite pencils with a polynomially bounded reciprocal Crawford number, diagonalization costs $O(n^{\omega_0}\log(n/\xi)\log\log(n/\xi))$ up to additive terms—one log factor below the general divide-and-conquer bound.
  • The algorithm covers pencils where neither $A$ nor $B$ is positive definite, so it applies to cases where the standard Cholesky reduction $B=RR^H$ is unavailable or numerically unattractive.
  • Because the solver avoids matrix inversion, the communication lower bounds established for inverse-free eigensolvers remain available.
  • The same output quality—$\xi$ accuracy in both diagonal blocks with probability $1-O(n^{-1})$—holds for the diagonal-perturbation variant, provided the sampling density is bounded.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the diagonal-perturbation theorem could be extended past bounded densities to genuinely discrete floating-point sampling—the paper shows why its current bound is vacuous there—then banded or sparse definite pencils could plausibly be shattered while preserving their sparsity, opening a sparse specialized solver.
  • The numerical evidence in Section 3 suggests the restriction $\mu < \gamma(A,B)/(12\sqrt{2})$ is conservative: perturbations far larger than allowed kept the pencil definite and sometimes increased $\gamma$. A tighter perturbation theorem would improve the algorithm's constants and its practical reliability.
  • For exponentially small Crawford numbers, the term $\log(n)\log(\gamma^{-1})$ in the complexity destroys the promised speedup, so the practical value of this algorithm hinges on obtaining good lower bounds for $\gamma$, not just on the solver itself.
  • The paper leaves as an open question whether Wishart (positive-definite) perturbations, which can only increase $\gamma$ in favorable field-of-values quadrants, also enjoy a shattering guarantee; if proved, that would give an input-dependent preprocessing step that lifts $\gamma$ before recursion starts.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a randomized, inverse-free divide-and-conquer eigensolver for definite generalized eigenvalue problems, i.e., Hermitian pencils (A,B) with positive Crawford number γ(A,B). The main contributions are: (1) a structured version of pseudospectral shattering, where the perturbations are either diagonal or drawn from the Gaussian Unitary Ensemble and shattering is stated on the real line; (2) a divide-and-conquer procedure that maintains definiteness by using only right deflating subspaces and compressions U^H A U, U^H B U; and (3) an asymptotic complexity bound O(n^{ω0} log(n/ξ) log(log(n/ξ) + log n log γ^{-1})) for output accuracy ξ, assuming a known lower bound γ on the Crawford number. The proof of the shattering theorems is largely self-contained, while the divide-and-conquer correctness and the IF-DWH iteration count are inherited by reference from the authors' prior work [18,19].

Significance. If the results hold, this is a valuable contribution to randomized numerical linear algebra: it is the first structure-preserving pseudospectral-shattering analysis for definite pencils, and it replaces a log(n/ξ) factor with log(log(n/ξ) + log n log γ^{-1}) under a polynomial-in-n,ξ^{-1} Crawford-number assumption. The paper is explicit about its inverse-free and highly parallel nature, and it honestly flags the dependence on a known lower bound for γ(A,B). The shattering proofs (Theorems 3.8 and 3.9) are careful and self-contained modulo standard random-matrix inequalities, and Lemma 4.1 is a nontrivial containment result that is proved in detail. However, the central divide-and-conquer result is compromised by an internal inconsistency in Algorithm 1: the input matrices are overwritten before the recursive subproblems are formed, so the stated proof does not establish the advertised accuracy for the original pencil. This is a load-bearing issue, not a presentation concern.

major comments (2)
  1. [Algorithm 1, lines 7-21] The input matrices A and B are overwritten in line 7 by (A - g_i B, 2rB) and then again in line 10 by the IF-DWH iterates, yet line 21 forms the recursive subproblems (A11,B11) = (U_k^H A U_k, U_k^H B U_k) from these overwritten matrices. The proof of Theorem 4.3, item 8, compares A11 with U^H A U where A is the original input of the current call, so the proof is only consistent with an algorithm that keeps a copy of the input pencil and uses that copy in line 21. As written, the recursion diagonalizes the shifted/IF-DWH-transformed pencil rather than the original pencil, and the output accuracy of Theorem 4.3 and Corollary 4.4 for the original (A,B) does not follow. This is a load-bearing inconsistency and must be fixed, for example by introducing explicit copies A0,B0 of the current call's input and using those copies when forming A11,B11,A22,B22.
  2. [Theorem 4.3 and Corollary 4.4] Theorem 4.3 is only a proof sketch: it invokes [19, Theorem 4.8] for the overall correctness structure, and it relies on [18] for the convergence of IF-DWH, for Lemma 4.2, and for the iteration count (4.29) that is used in the complexity bound of Corollary 4.4. Since the advertised asymptotic speedup depends directly on that iteration count, the manuscript should either reproduce the needed statements as self-contained lemmas or clearly identify which parts of [18] are already formally published and which remain a preprint. Without this, the central complexity claim is not independently verifiable from the present manuscript.
minor comments (4)
  1. [Section 2.2, paragraph after (2.8)] There is a duplicated word in 'this can can be leveraged'; it should read 'this can be leveraged'.
  2. [Lemma 4.1, equation (4.4)] The block factorization assumes that the columns of X are ordered so that X1 spans the same subspace as U; a short sentence justifying this ordering of the eigenvector matrix would improve readability.
  3. [Theorem 3.9] The condition P[|X| > M_ρ] ≤ θ is used with θ such that 2nθ = O(n^{-1}); for a Gaussian density with fixed variance this requires M_ρ = Θ(√(log n)), and the text could state this explicitly so that the reader sees that the resulting probability bound remains O(1).
  4. [Corollary 4.4, first paragraph] The assumption ξ < nγ/√2 is used to ensure μ = ξ/(12n) satisfies the shattering hypothesis μ < γ(A,B)/(12√2); a one-sentence explanation of this implication would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new shattering theorems are derived from external concentration bounds, gamma is an input assumption rather than a fitted quantity, and the self-citations to [18,19] are published parameter-free analyses.

full rationale

The derivation chain is not circular. Section 3 proves structured pseudospectral shattering directly from external probabilistic results (Minami, Wegner, Aizenman et al.), Stewart's perturbation theorems, and Elsner-Sun eigenvector conditioning; no parameter is fitted to the later output, and no 'prediction' is a renamed fit. Corollary 4.4 combines that shattering guarantee with Algorithm 1, propagating the output error to the original pencil by the triangle inequality; the known lower bound gamma is a stated input assumption, not a quantity inferred from the computed diagonalization. The correctness of the divide-and-conquer step (Theorem 4.3) and the IF-DWH convergence count are imported from the authors' prior papers [18] and [19]; those are published, parameter-free analyses whose stated assumptions do not include the present theorem, so under the stated review rules they count as independent supporting evidence rather than load-bearing circular self-citation. The paper also explicitly discloses its lack of empirical testing and describes some strengthening bounds as 'out of reach', which are completeness or risk issues rather than circularity. A separate algorithmic/proof mismatch may exist: Algorithm 1 overwrites A,B at lines 7 and 9-11 before forming recursive subproblems at line 21, while Theorem 4.3's item 8 compares the subproblem against the original input pencil; this is a correctness concern, not a circularity, because it does not define a claimed result in terms of itself.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claim depends on standard random matrix local laws, Stewart and Elsner-Sun perturbation bounds, the assumption of a known Crawford-number lower bound, and two specialized subroutines from the authors' prior work (IF-DWH and GRURV). These are inputs and cited results rather than fitted parameters.

free parameters (2)
  • Perturbation size mu = mu < gamma(A,B)/(12 sqrt(2)); mu < xi/(12n) in Corollary 4.4
    An algorithmic parameter controlling random perturbations. It sets the shattering epsilon and the grid spacing; it is not fitted to data.
  • Crawford number lower bound gamma = input value satisfying 0 < gamma <= gamma(A,B)
    Appears as a divisor in shattering epsilon and in the complexity through log(gamma^{-1}). The speedup is only guaranteed when gamma is polynomial in n and xi^{-1}.
assumptions (6)
  • domain assumption The input pencil (A,B) is definite and a lower bound gamma <= gamma(A,B) is known on input.
    Definiteness preservation and all shattering/complexity statements depend on gamma; Section 1 and Algorithm 1 Requires.
  • standard math Local fluctuation bounds for GUE and random diagonal perturbations (Theorem 3.6) hold as cited.
    Founded on Minami [29] and Aizenman et al. [1]; used to prove minimum eigenvalue gap in Theorems 3.8 and 3.9.
  • standard math Stewart perturbation theorems for definite pencils (Theorems 2.1 and 2.2) and the Elsner-Sun bound (Lemma 2.3) hold.
    Used throughout Sections 3 and 4 to bound Crawford number decay, eigenvector perturbations, and singular values of A - zB.
  • domain assumption IF-DWH from [18] converges for real-eigenvalue pencils in the stated number of iterations and satisfies Lemma 4.2.
    The complexity gain in Corollary 4.4 is inherited from [18]; the proof is not reproduced here.
  • domain assumption GRURV from [5] provides randomized rank-revealing factorizations with the assumed failure probability and accuracy.
    Algorithm 1 uses GRURV in lines 12, 17, and 19; the proofs rely on its cited guarantees.
  • standard math Matrix multiplication and matrix inverse-free operations have complexity O(n^{omega0}) in the standard model.
    Complexity statements are expressed in terms of n^{omega0}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem." pith.science (2026). https://pith.science/paper/DGHIPBSG

@misc{pith2026250521917,
  author       = {Pith},
  title        = {Pith review of: Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DGHIPBSG}},
  note         = {Machine review of arXiv:2505.21917}
}
abstract

This paper presents a fast, randomized divide-and-conquer algorithm for the definite generalized eigenvalue problem, which corresponds to pencils $(A,B)$ in which $A$ and $B$ are Hermitian and the Crawford number $\gamma(A,B) = \min_{||x||_2 = 1} |x^H(A+iB)x|$ is positive. Adapted from the fastest known method for diagonalizing arbitrary matrix pencils [Foundations of Computational Mathematics 2024], the algorithm is both inverse-free and highly parallel. As in the general case, randomization takes the form of perturbations applied to the input matrices, which regularize the problem for compatibility with fast, divide-and-conquer eigensolvers -- i.e., the now well-established phenomenon of pseudospectral shattering. We demonstrate that this high-level approach to diagonalization can be executed in a structure-aware fashion by (1) extending pseudospectral shattering to definite pencils under structured perturbations (either random diagonal or sampled from the Gaussian Unitary Ensemble) and (2) formulating the divide-and-conquer procedure in a way that maintains definiteness. The result is a specialized solver whose complexity, when applied to definite pencils, is provably lower than that of general divide-and-conquer.

Figures

Figures reproduced from arXiv: 2505.21917 by the authors.

Figure 1
Figure 1. Pseudospectra of a 10 × 10 pencil (A, B), constructed so that B−1A is a Jordan block, before and after perturbation. The black curves trace the boundaries of ϵ-pseudospectra for two choices of ϵ; the eigenvalues they contained are marked with dark circles. In the rightmost plot we include a random grid that shatters the tighter pseudospectrum of the perturbed problem, identifying in red a potential split for use in … view at source ↗
Figure 2
Figure 2. Spectra and symmetric ϵ-pseudospectra of a 10 × 10 definite pencil (A, B), constructed as in (3.18), before and after perturbations. Eigenvalues are marked with ticks, while components of Λsym ϵ (A, B) are plotted with filled circles. (A, B) initially has a repeated eigenvalue at +1, which is highlighted in red, and each perturbation has size µ = 10−6 . Initially, γ(A, B) = 5.91 × 10−8 while in the remaining subfigu… view at source ↗
Figure 3
Figure 3. Impact of perturbation size on γ(A, e Be). Each plot presents a histogram of γ(A, e Be) for 200 GUE perturbations of a 500 × 500 definite pencil (A, B), which is constructed so that γ(A, B) = √ 2 × 10−7 . µ increases from left to right; at its smallest, it is equal to the bound from Theorem 3.8. We mark γ(A, B) and the upper bound γ(A, B) + 2µ q log(n) n with dashed black and red lines, respectively. The latter hold… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 41 canonical work pages

  1. [19]

    Demmel, I

    J. Demmel, I. Dumitriu, and R. Schneider. Generalized Pseudospectral Shattering and Inverse-Free Matrix Pencil Diagonalization. Foundations of Computational Mathematics , 2024

    work page 2024

  2. [18]

    Demmel, I

    J. Demmel, I. Dumitriu, and R. Schneider. Fast and inverse-free algorithms for deflating subspaces. arXiv:2310.00193, 2024

    arXiv 2024

  3. [1]

    Aizenman, R

    M. Aizenman, R. Peled, J. Schenker, M. Shamis, and S. Sodin. Matrix regularizing effects of Gaussian perturbations. Communications in Contemporary Mathematics , 19(03):1750028, 2017

    work page 2017

  4. [2]

    Z. Bai, J. Demmel, and M. Gu. An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. Numerische Mathematik , 76:279–308, 1997

    work page 1997

  5. [3]

    Z. D. Bai. Circular law. The Annals of Probability , 25(1):494–529, 1997

    work page 1997

  6. [4]

    Ballard, J

    G. Ballard, J. Demmel, and I. Dumitriu. Minimizing Communication for Eigenproblems and the Sin- gular Value Decomposition. Technical Report UCB/EECS-2011-14, EECS Department, University of California, Berkeley, Feb 2011

    work page 2011

  7. [5]

    Ballard, J

    G. Ballard, J. Demmel, I. Dumitriu, and A. Rusciano. A generalized randomized rank-revealing factor- ization. arXiv:1909.06524, 2019. 23

    arXiv 1909

  8. [6]

    Banks, J

    J. Banks, J. Garza-Vargas, A. Kulkarni, and N. Srivastava. Pseudospectral Shattering, the Sign Func- tion, and Diagonalization in Nearly Matrix Multiplication Time. Foundations of Computational Math- ematics, 23:1959–2047, 2023

    work page 1959

Show all 44 references
  1. [7]

    Banks, A

    J. Banks, A. Kulkarni, S. Mukherjee, and N. Srivastava. Gaussian Regularization of the Pseudospectrum and Davies’ Conjecture. Communications on Pure and Applied Mathematics , 74:2114–2131, 10 2021

    2021

  2. [8]

    Beavers and E

    A. Beavers and E. Denman. A new similarity transformation method for eigenvalues and eigenvectors. Mathematical Biosciences, 21(1):143–169, 1974

    1974

  3. [9]

    A. Y. Bulgakov and S. Godunov. Circular dichotomy of the spectrum of a matrix. Siberian Mathematical Journal, 29:734–744, 1988

    1988

  4. [10]

    Bunse-Gerstner

    A. Bunse-Gerstner. An algorithm for the symmetric generalized eigenvalue problem. Linear Algebra and its Applications , 58, 1984

    1984

  5. [11]

    Chandrasekaran

    S. Chandrasekaran. An efficient and stable algorithm for the symmetric-definite generalized eigenvalue problem. SIAM Journal on Matrix Analysis and Applications , 21(4):1202–1228, 2000

    2000

  6. [12]

    Collins, P

    B. Collins, P. Gawron, A. E. Litvak, and K. ˙Zyczkowski. Numerical range for random matrices. Journal of Mathematical Analysis and Applications , 418(1):516–533, 2014

    2014

  7. [13]

    C. R. Crawford. The Numerical Solution of the Generalized Eigenvalue Problem. PhD Thesis, 1970

    1970

  8. [14]

    C. R. Crawford. A Stable Generalized Eigenvalue Problem. SIAM Journal on Numerical Analysis , 13(6):854–860, 1976

    1976

  9. [15]

    C. R. Crawford and Y. S. Moon. Finding a positive definite linear combination of two Hermitian matrices. Linear Algebra and its Applications , 51:37–48, 1983

    1983

  10. [16]

    P. I. Davies, N. J. Higham, and F. Tisseur. Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem. SIAM Journal on Matrix Analysis and Applications, 23(2):472–493, 2001

    2001

  11. [17]

    Demmel, I

    J. Demmel, I. Dumitriu, and O. Holtz. Fast linear algebra is stable. Numerische Mathematik, 108:59–91, 2007

    2007

  12. [20]

    Elsner and J

    L. Elsner and J. Sun. Perturbation theorems for the generalized eigenvalue problem. Linear Algebra and its Applications , 48:341–357, 1982

    1982

  13. [21]

    Ford and G

    B. Ford and G. Hall. The generalized eigenvalue problem in quantum chemistry. Computer Physics Communications, 8(5):337–348, 1974

    1974

  14. [22]

    Graillat

    S. Graillat. A note on structured pseudospectra. Journal of Computational and Applied Mathematics , 191(1):68–76, 2006

    2006

  15. [23]

    C.-H. Guo, N. J. Higham, and F. Tisseur. An Improved Arc Algorithm for Detecting Definite Hermitian Pairs. SIAM Journal on Matrix Analysis and Applications , 31(3):1131–1151, 2010

    2010

  16. [24]

    Kressner, D

    D. Kressner, D. Lu, and B. Vandereycken. Subspace acceleration for the Crawford number and related eigenvalue optimization problems. SIAM Journal on Matrix Analysis and Applications , 39(2):961–982, 2018

    2018

  17. [25]

    A. N. Malyshev. Computing invariant subspaces of a regular linear pencil of matrices. Siberian Mathe- matical Journal, 30:559–567, 1989. 24

    1989

  18. [26]

    A. N. Malyshev. Parallel algorithm for solving some spectral problems of linear algebra. Linear Algebra and its Applications , 188-189:489–520, 1993

    1993

  19. [27]

    Mangasarian and E

    O. Mangasarian and E. Wild. Multisurface proximal support vector machine classification via generalized eigenvalues. IEEE Transactions on Pattern Analysis and Machine Intelligence , 28(1):69–74, 2006

    2006

  20. [28]

    C. Mehl. Jacobi-like algorithms for the indefinite generalized Hermitian eigenvalue problem. SIAM Journal on Matrix Analysis and Applications , 25(4):964–985, 2004

    2004

  21. [29]

    N. Minami. Local fluctuation of the spectrum of a multidimensional Anderson tight binding model. Communications in Mathematical Physics , 177(3):709–725, 1996

    1996

  22. [30]

    Nakatsukasa, Z

    Y. Nakatsukasa, Z. Bai, and F. Gygi. Optimizing Halley’s Iteration for Computing the Matrix Polar Decomposition. SIAM Journal on Matrix Analysis and Applications , 31(5):2700–2720, 2010

    2010

  23. [31]

    Schneider

    R. Schneider. Pseudospectral Divide-and-Conquer for the Generalized Eigenvalue Problem. PhD Thesis, 2024

    2024

  24. [32]

    D. S. Scott. Solving sparse symmetric generalized eigenvalue problems without factorization. SIAM Journal on Numerical Analysis , 18(1):102–110, 1981

    1981

  25. [33]

    R. Shah, N. Srivastava, and E. Zeng. Sparse pseudospectral shattering. arXiv:2411.19926, 2024

    2024 arXiv

  26. [34]

    G. W. Stewart. Perturbation bounds for the definite generalized eigenvalue problem. Linear Algebra and its Applications , 23:69–85, 1979

    1979

  27. [35]

    G. W. Stewart and J. Sun. Matrix Perturbation Theory . Computer Science and Scientific Computing. Elsevier Science, 1990

    1990

  28. [36]

    L. N. Trefethen and M. Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2020

    2020

  29. [37]

    F. Uhlig. On computing the generalized Crawford number of a matrix. Linear Algebra and its Applica- tions, 438(4):1923–1935, 2013

    1923

  30. [38]

    Veseli´ c

    K. Veseli´ c. A Jacobi eigenreduction algorithm for definite matrix pairs. Numerische Mathematik , 64:241–269, 1993

    1993

  31. [39]

    F. Wegner. Bounds on the density of states in disordered systems. Zeitschrift f¨ ur Physik B Condensed Matter, 44:9–15, 1981

    1981

  32. [40]

    J. Wishart. The Generalized Product Moment Distribution in Samples from a Normal Multivariate Population. Biometrika, 20A(1/2):32–52, 1928. A GRUR V and IF-DWH This appendix discusses the numerical details of two building blocks of our structured divide-and-conquer algorithm: ...

    1928

  33. [41]

    The eigenvalues of ( A, B) to the right of gi correspond to eigenvalues of ( A, B) in the right half plane

    After a grid point is selected, the pencil ( A, B) is shifted and scaled to obtain ( A, B) = (A − giB, 2rB), whose eigenvalues live in a union of intervals (−1, −l) ∪ (l, 1). The eigenvalues of ( A, B) to the right of gi correspond to eigenvalues of ( A, B) in the right half plane

  34. [42]

    Applying IF-DWH to ( A, B) produces a pencil ( Ap, Bp) that approximates sign( B−1A), implicitly, as B−1 p Ap. Since the (right) eigenvectors of ( A, B) and ( A, B) are the same, this simultaneously approximates the spectral projector of ( A, B) corresponding to eigenvalues to...

  35. [43]

    Finally, GRUR Vcomputes a rank-revealing factorization of this approximation, which can be ex- pressed as 1 2 B−1 p (Ap + Bp). Reading the rank from this factorization (which can be done without explicitly inverting the triangular matrices produced by GRUR V) allows us to chec...

  36. [44]

    This is a simple consequence of the fact that 1 2 (sign(A) − I) is a projector onto eigenvectors of A associated to the left half plane

    If the split is selected, a projector onto the right deflating subspace corresponding to the remaining eigenvalues can be obtained without calling IF-DWH a second time. This is a simple consequence of the fact that 1 2 (sign(A) − I) is a projector onto eigenvectors of A associ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.