no. 13 · Wednesday 11 November 2026
Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective
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.
- comments
- Accepted to PPoPP 2027; 11 pages, 6 figures, 5 tables; supplemental material included as ancillary file
- fields
- Numerical Analysis