Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective

summary

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…

In short

The paper revisits Divide and Conquer (D&C) for symmetric tridiagonal eigenvalue problems by introducing a boundary-row state (BR) to reduce memory usage from quadratic to linear space. This method eliminates the need for storing the full eigenvector matrix during recursion, improving performance and storage efficiency without sacrificing accuracy.

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 used across episodes

This episode discusses

The paper

Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective · Read on arXiv

University of Electronic Science and Technology of China

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.

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.

More episodes

← Home