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

DevFeed: [Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective](<https://devfeed.tech/articles/revisiting-eigenvalue-only-divide-and-conquer-tridiagonal-eigensolver-from-algorithmic-perspective-127788.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2605.26599>)

Author: Ruiyi Zhan, Dajun Huang, Lu Shi, Shaoshuai Zhang

Published: 2026-11-11T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [Distributed Systems & Parallel Computing](<https://devfeed.tech/topics/distributed-systems-parallel-computing.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-na](<https://devfeed.tech/tags/cs-na.md>), [divide-and-conquer](<https://devfeed.tech/tags/divide-and-conquer.md>), [gpu](<https://devfeed.tech/tags/gpu.md>), [linear](<https://devfeed.tech/tags/linear.md>), [math-na](<https://devfeed.tech/tags/math-na.md>), [memory](<https://devfeed.tech/tags/memory.md>), [merge](<https://devfeed.tech/tags/merge.md>), [optimized](<https://devfeed.tech/tags/optimized.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [parallelism](<https://devfeed.tech/tags/parallelism.md>), [perspective](<https://devfeed.tech/tags/perspective.md>), [rank](<https://devfeed.tech/tags/rank.md>), [schedule](<https://devfeed.tech/tags/schedule.md>), [scheduling](<https://devfeed.tech/tags/scheduling.md>), [serial](<https://devfeed.tech/tags/serial.md>), [stage](<https://devfeed.tech/tags/stage.md>)

## AI overview

The paper's eigenvalue-only divide-and-conquer method reduces persistent memory from quadratic to linear by carrying just the first and last rows of each node's eigenvector block through a recurrence, without replaying merge work. It adapts parallel scheduling to each merge's post-deflation active rank, applying finer-grained parallelism where substantial secular computation remains on both CPU and GPU. The authors report complexity and correctness analyses and comparisons of optimized CPU and GPU implementations with standard-library QR, bisection, and divide-and-conquer routines; the supplied abstract does not state comparative results.

## Source excerpt

arXiv:2605.26599v2 Announce Type: replace 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.