从算法视角重新审视仅求特征值的分治三对角特征值求解器
Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective
Ruiyi Zhan, Dajun Huang, Lu Shi, Shaoshuai Zhang
AI 速读 基于摘要
作者提出仅用每个合并节点的首末两行边界行构成递推来携带分治状态，将持久内存从二次降为线性，并在 CPU 与 GPU 上按去膨胀后的有效秩做细粒度调度。
cs.DC · math.NA
查看原文摘要
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.