Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective".
Jane: Here's the gist of the paper. Divide and Conquer (D&C) is a widely used algorithmic strategy for symmetric eigenvalue decomposition that can be improved by reducing internal state to achieve linear space complexity The key observation is that the conquer phase only needs selected boundary rows/columns rather than the full accumulated eigenvector matrix By propagating these boundary rows directly through the recursion, the proposed algorithm reduces the memory requirement from quadratic to linear space while also eliminating unnecessary matrix-vector work in the conventional lazy-replay formulation The paper identifies a boundary-row dependency that causes conventional eigenvalue-only D&C to retain dense eigenvector state The key observation behind our method is that lazy replay keeps too much information for the eigenvalue-only problem At each merge, the parent does not require the full child basis; it only requires the two boundary rows that define the secular vector This observation separates eigenvalue-only D&C from full-eigenvector D&C and creates an opportunity to reduce memory from quadratic to linear Algorithmic Invariant and Correctness The authors define boundary-row state (BR) as the replacement for dense eigenvector state in eigenvalue-only D&C The internal values-only D&C path reconstructs a requested boundary row by replaying a chain of GEMV-like transformations, while BR instead propagates boundary rows by the local recurrence Bv =
BL; BR: Sv Lemma 3.1 proves that the secular vector z in Eq.
Tom: (6) is fully determined by bhi(QL) and blo(QR) Theorem 3.3 confirms that BR computes the same eigenvalues as conventional D&C in exact arithmetic Complexity and Performance Gains The analysis shows that while BR does not reduce the asymptotic cost of the secular root solves, it removes the replay term and avoids writing a dense local secular-vector block The leading merge-path costs show that TBR(n) = (2csec + 4)n squared + O(n log n), which is better than Tlazy (n) = (csec + crep + 4)n squared + O(n log n), indicating a constant-factor reduction in the D&C merge path The asymptotic gain is in storage, as BR stores only linear-size boundary rows and compact secular data resulting in an auxiliary state of O(n) excluding input tridiagonal arrays and output eigenvalues Implementation and Evaluation The CPU and GPU code paths implement the same algorithmic modification to tridiagonal D&C, replacing persistent full-eigenvector or replay state with the boundary-row state The CPU implementation exposes OpenMP parallelism without adding thread-dependent workspace GPU experiments show that the values-only D&C path avoids the large quadratic cuSOLVER workspace and is faster than cuSOLVER on all measured N = 49152 tridiagonal-stage cases The results make the boundary clear, showing that BR is not a universal subquadratic eigensolver but makes the D&C design point available to eigenvalue-only workloads without carrying full eigenvector state Spectral Structure Dependence The speedup observed in experiments depends on the spectrum structure, with uniform and normal families producing near-linear BR timings in the measured large-N range Toeplitz and clustered families are harder cases where both DSTERF and BR fit close to quadratic growth The paper concludes that BR is especially effective for spectra where D&C deflation and selected-row propagation keep the merge work close to linear, while its most general guarantee is linear auxiliary storage Numerical Accuracy For all benchmark rows with a DSTERF reference, BR produced eigenvalues close to the reference under the normalized metrics defined above The fixed-seed pseudo-random cross-checks cover uniform and normal diagonal distributions through N = 65,536, while the structured checks cover Toeplitz, clustered, and reduced-dense tridiagonal inputs These normalized checks are consistent with the conditioned-error argument in Section 3.2.2 The paper reports forward and backward errors rather than raw eigenvalue differences so that the reduced-dense case is compared on the same scale as synthetic cases BR is not a universal subquadratic eigensolver but makes the D&C design point available to eigenvalue-only workloads without carrying full eigenvector state The prototypes show the practical effect of this reduced state On CPUs, BR reaches problem sizes near the LP64 workspace limit and reduces the internal values-only D&C state from quadratic replay storage to linear boundary-row storage With parallel leaf initialization, the CPU BR prototype is faster than both DSTERF and MKL’s internal D&C path on the completed pseudo-random and structured rows On an H100, the values-only D&C path avoids the large quadratic cuSOLVER workspace and is faster than cuSOLVER on all measured N = 49152 tridiagonal-stage cases The results make the boundary clear References
1: Hervé Abdi and Lynne J Williams.
Tom: Principal component analysis
3: Paolo Bientinesi, Inderjit S Dhillon, and Robert A Van De Geijn.
Paper summary: Tom: So, looking at the full paper Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective, the main point is that they found a way to make eigenvalue only divide and conquer practical for memory constrained workloads.
Jane: They achieve this by introducing boundary rows as a state replacement for the dense eigenvector matrix during the conquer phase, reducing memory usage from quadratic to linear space while keeping the secular equation structure intact.
Lu: The paper argues that this method is important because it separates eigenvalue-only D andC from full eigenvector D andC and shows why libraries default to QR-based methods when only eigenvalues are requested, which was a key insight for them.
Meng: From an engineering standpoint, the practical implication is that we can deploy these solvers on hardware with tight memory constraints without hitting those quadratic workspace limits because they operate with linear auxiliary storage instead.
Lalam: The paper doesn't claim it's a universal subquadratic eigensolver; it explicitly states that its speedup depends on the spectrum structure, being most effective where D andC deflation and selected-row propagation keep the merge work close to linear.
Tom: So, for anyone interested in this, the title Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective suggests they are looking at old ideas and showing how a specific structural change can unlock a practical application for symmetric tridiagonal problems.
Jane: It’s about taking an established algorithm, D andC, and tailoring the internal state to match the exact needs of just finding eigenvalues, rather than trying to solve the full eigenvector problem simultaneously.
Conclusion: Tom: So, we're wrapping up this look at the paper Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective, and the main thing is they’ve taken an old idea and made it work for problems where you only need eigenvalues.
Jane: I mean, they're focusing on how a standard divide and conquer method can be tweaked so it doesn't keep all that dense eigenvector data around during the merging steps.
Lu: Right, they call this boundary-row state, which is basically replacing the heavy eigenvector matrix with just a few key rows that define where we need to go next.
Meng: From an engineering standpoint, this means we can stop spending huge amounts of memory on storing those full matrices when we only care about the eigenvalues.
Tom: And they showed that even though it doesn't change the core calculation cost for finding the roots themselves, it cuts down on a lot of unnecessary work during the merge path.
Jane: So, what does this mean for someone just trying to run an eigenvalue problem on a machine with limited memory? It suggests you can use these divide and conquer methods without hitting those quadratic memory limits.
Lu: The paper is really arguing that we need to separate the eigenvalue-only version from the full eigenvector version because they handle the state very differently.
Meng: I guess what I’m seeing is that for production systems where you only need eigenvalues, this approach could make a big difference in deployment cost and speed at scale.
Tom: It’s about taking a well-known algorithm and making it more efficient for specific tasks by changing how it manages its internal state.
Jane: And the authors are quite clear about when this is most effective, pointing out that the performance actually depends on the shape of the data you're working with.
Lu: They find that uniform or normal families of numbers run really well, but for more complex structures like Toeplitz or clustered data, it still behaves close to quadratic growth in terms of merge time.
Meng: So it’s not a magic cure for every single problem type; you still get those quadratic slowdowns on the harder structures.
Tom: It’s a practical tool, not some universal fix, but it makes the divide and conquer design viable for eigenvalue-only workloads without carrying that massive full eigenvector state around.
Jane: This is a good example of how focusing on what you actually need can open up new ways to handle tough numerical problems.
Lu: And I’m sure the next part of this research will explore how this boundary-row idea connects to other types of matrix representations.
University of Electronic Science and Technology of China
cs.DC, cs.NA, math.NA
Submitted: 2026-05-26
Updated: 2026-11-10
Comments: Accepted to PPoPP 2027; 11 pages, 6 figures, 5 tables; supplemental material included as ancillary file
Code: https://github.com/icl-utk-edu/magma
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 65/100
The gist: Divide and Conquer (D&C) is a widely used algorithmic strategy for symmetric eigenvalue decomposition that can be improved by reducing internal state to achieve linear space complexity The key…
Key concepts
- Boundary-Row State (BR)
- This is a replacement for dense eigenvector state in eigenvalue-only D&C. Instead of keeping all eigenvectors, BR only propagates selected boundary rows through the recursive steps. This significantly reduces memory requirements from quadratic to linear space.
- Lazy Replay Formulation
- The conventional D&C approach uses a lazy replay formulation where the parent node needs the full child basis. The paper argues this keeps too much information, necessitating dense eigenvector state. BR avoids this by only requiring boundary rows at each merge step.
- Secular Vector
- The secular vector is a key component in solving the eigenvalue problem, specifically related to Eq. (6). The authors prove that the secular vector can be fully determined using only the boundary rows from the parent and child nodes, which is crucial for implementing the BR approach.
Terminology
Summary
Divide and Conquer (D&C) is a widely used algorithmic strategy for symmetric eigenvalue decomposition that can be improved by reducing internal state to achieve linear space complexity The key observation is that the conquer phase only needs selected boundary rows/columns rather than the full accumulated eigenvector matrix By propagating these boundary rows directly through the recursion, the proposed algorithm reduces the memory requirement from quadratic to linear space while also eliminating unnecessary matrix-vector work in the conventional lazy-replay formulation
Motivation for Boundary-Row State
The paper identifies a boundary-row dependency that causes conventional eigenvalue-only D&C to retain dense eigenvector state The key observation behind our method is that lazy replay keeps too much information for the eigenvalue-only problem At each merge, the parent does not require the full child basis; it only requires the two boundary rows that define the secular vector This observation separates eigenvalue-only D&C from full-eigenvector D&C and creates an opportunity to reduce memory from quadratic to linear
Algorithmic Invariant and Correctness
The authors define boundary-row state (BR) as the replacement for dense eigenvector state in eigenvalue-only D&C The internal values-only D&C path reconstructs a requested boundary row by replaying a chain of GEMV-like transformations, while BR instead propagates boundary rows by the local recurrence Bv = [BL; BR]Sv Lemma 3.1 proves that the secular vector z in Eq. p. 2 This section turns the observation into an algorithmic
invariant. It defines boundary-row state, proves that this
state is sufficient to reproduce the same secular problems
as conventional D&C, and derives the resulting work and
storage model. For any D&C merge
with child eigenvector matrices 𝑄𝐿 and 𝑄𝑅, the secular vector
𝑧 in Eq. (6) is fully determined by bhi(𝑄𝐿) and blo(𝑄𝑅).Where the paper says it
Where the paper says it
Complexity and Performance Gains
The analysis shows that while BR does not reduce the asymptotic cost of the secular root solves, it removes the replay term and avoids writing a dense local secular-vector block The leading merge-path costs show that TBR(n) = (2csec + 4)n squared + O(n log n), which is better than Tlazy (n) = (csec + crep + 4)n squared + O(n log n), indicating a constant-factor reduction in the D&C merge path The asymptotic gain is in storage, as BR stores only linear-size boundary rows and compact secular data resulting in an auxiliary state of O(n) excluding input tridiagonal arrays and output eigenvalues
Implementation and Evaluation
The CPU and GPU code paths implement the same algorithmic modification to tridiagonal D&C, replacing persistent full-eigenvector or replay state with the boundary-row state The CPU implementation exposes OpenMP parallelism without adding thread-dependent workspace GPU experiments show that the values-only D&C path avoids the large quadratic cuSOLVER workspace and is faster than cuSOLVER on all measured N = 49152 tridiagonal-stage cases The results make the boundary clear, showing that BR is not a universal subquadratic eigensolver but makes the D&C design point available to eigenvalue-only workloads without carrying full eigenvector state
Spectral Structure Dependence
The speedup observed in experiments depends on the spectrum structure, with uniform and normal families producing near-linear BR timings in the measured large-N range Toeplitz and clustered families are harder cases where both DSTERF and BR fit close to quadratic growth The paper concludes that BR is especially effective for spectra where D&C deflation and selected-row propagation keep the merge work close to linear, while its most general guarantee is linear auxiliary storage
Numerical Accuracy
For all benchmark rows with a DSTERF reference, BR produced eigenvalues close to the reference under the normalized metrics defined above The fixed-seed pseudo-random cross-checks cover uniform and normal diagonal distributions through N = 65,536, while the structured checks cover Toeplitz, clustered, and reduced-dense tridiagonal inputs These normalized checks are consistent with the conditioned-error argument in Section 3.2.2 The paper reports forward and backward errors rather than raw eigenvalue differences so that the reduced-dense case is compared on the same scale as synthetic cases
Conclusion
BR is not a universal subquadratic eigensolver but makes the D&C design point available to eigenvalue-only workloads without carrying full eigenvector state The prototypes show the practical effect of this reduced state On CPUs, BR reaches problem sizes near the LP64 workspace limit and reduces the internal values-only D&C state from quadratic replay storage to linear boundary-row storage With parallel leaf initialization, the CPU BR prototype is faster than both DSTERF and MKL’s internal D&C path on the completed pseudo-random and structured rows On an H100, the values-only D&C path avoids the large quadratic cuSOLVER workspace and is faster than cuSOLVER on all measured N = 49152 tridiagonal-stage cases The results make the boundary clear
References
[1] Hervé Abdi and Lynne J Williams. 2010. Principal component analysis
[3] Paolo Bientinesi, Inderjit S Dhillon, and Robert A Van De Geijn. 2005. A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations
[4] J. J. M. Cuppen. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem
[7] Gene H Golub and Charles F Van Loan. 2013. Matrix computations
[8] Roger Grimes, Henry Krakauer, John Lewis, Horst Simon, and SuHai Wei. 1987. The solution of large dense generalized eigenvalue problems on the Cray X-MP/24 with SSD
[10] Ming Gu and Stanley C Eisenstat. 1995. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem
[14] A Melman. 1995. Numerical solution of a secular equation
[17] Notker Rösch, Sven Krüger, Vladimir A Nasluzov, and Alexei V Matveev. 2005. ParaGauss: The density functional program paragauss for complex systems in chemistry
[19] Françoise Tisseur and Jack Dongarra. 1999. A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures
[22] David S Watkins. 1982. Understanding the QR algorithm
[4] J. J. M. Cuppen. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem
[6] Inderjit S Dhillon and Beresford N Parlett. 2004. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
[7] Gene H Golub and Charles F Van Loan. 2013. Matrix computations
[8] Roger Grimes, Henry Krakauer, John Lewis, Horst Simon, and SuHai Wei. 1987. The solution of large dense generalized eigenvalue problems on the Cray X-MP/24 with SSD
[10] Ming Gu and Stanley C Eisenstat. 1995. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem
[14] A Melman. 1995. Numerical solution of a secular equation
[17] Notker Rösch, Sven Krüger, Vladimir A Nasluzov, and Alexei V Matveev. 2005. ParaGauss: The density functional program paragauss for complex systems in chemistry
[19] Françoise Tisseur and Jack Dongarra. 1999. A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures
[22] David S Watkins. 1982. Understanding the QR algorithm
[4] J. J. M. Cuppen. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem
[6] Inderjit S Dhillon and Beresford N Parlett. 2004. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
[7] Gene H Golub and Charles F Van Loan. 2013. Matrix computations
[8] Roger Grimes, Henry Krakauer, John Lewis, Horst Simon, and SuHai Wei. 1987. The solution of large dense generalized eigenvalue problems on the Cray X-MP/24 with SSD
[10] Ming Gu and Stanley C Eisenstat. 1995. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem
[14] A Melman. 1995. Numerical solution of a secular equation
[17] Notker Rösch, Sven Krüger, Vladimir A Nasluzov, and Alexei V Matveev. 2005. ParaGauss: The density functional program paragauss for complex systems in chemistry
[19] Françoise Tisseur and Jack Dongarra. 1999. A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures
[22] David S Watkins. 1982. Understanding the QR algorithm
[4] J. J. M. Cuppen. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem
[6] Inderjit S Dhillon and Beresford N Parlett. 2004. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
[7] Gene H Golub and Charles F Van Loan. 2013. Matrix computations
[8] Roger Grimes, Henry Krakauer, John Lewis, Horst Simon, and SuHai Wei. 1987. The solution of large dense generalized eigenvalue problems on the Cray X-MP/24 with SSD
[10] Ming Gu and Stanley C Eisenstat. 1995. A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem
[14] A Melman. 1995.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Boundary-row D&C Algorithm Implementation: The proposed boundary-row D&C algorithm reduces memory requirement from quadratic to linear space while eliminating unnecessary matrix-vector work in conventional lazy-replay formulations. This allows it to be practical for memory constrained eigenvalue only workloads on CPUs and GPUs.
-
State Management for Eigenvalue Only Computations: The system can maintain a linear size boundary row state instead of dense intermediate transformations, which changes the memory behavior from storing dense intermediate transformations to storing linear-size spectral and boundary data. This makes D&C practical for eigenvalue only workloads by avoiding the quadratic space cost of conventional D&C.
-
Parallelism Exposure on Modern Hardware: The algorithm retains the parallel merge structure that motivates D&C while removing the main reason libraries fall back to QR-like routines when only eigenvalues are requested. This exposes more parallelism than the low-memory QR/QL path when the spectrum permits useful deflation.
-
Performance Gains on Structured Spectra: On structured inputs like Toeplitz and clustered families, the boundary-row D&C formulation provides significant speedups over DSTERF and cuSOLVER, demonstrating a conditional performance claim where "BR is especially effective for spectra where D&C deflation and selected-row propagation keep the merge work close to linear."
-
Hardware Specific Optimization: The implementation includes optimized CPU and GPU paths that expose the boundary-row state contract on both architectures. On GPUs, this avoids the large quadratic workspace of conventional D&C, showing speedups up to 5.73 times on clustered inputs compared to cuSOLVER.
Abstract
Divide-and-conquer (D&C) is the natural parallel strategy for symmetric tridiagonal eigenvalue decomposition, yet eigenvalue-only solvers fall back to serial QR algorithm because the quadratic transform state each merge carries exhausts memory at scale. In this paper, we demonstrate that each merge stage in D&C needs only two boundary rows, the first and last rows of a node's eigenvector block, and these close into a recurrence whose parent rows follow from its children's and local merge data alone, so the state is carried up the tree with nothing replayed and persistent memory drops from quadratic to linear. Because this state keeps no replay workspace, adapting the schedule to each merge's post-deflation active rank is a scheduling choice, so both CPU and GPU spend finer-grained parallelism only where substantial secular work survives. We evaluate optimized CPU and GPU implementations, with complexity and correctness analysis, against QR, bisection, and D&C routines in standard libraries.
Related papers
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends
- AgentWeave: Efficient Distributed Agent Serving via Flow Decomposition