STABLE AND EFFICIENT SPECTRAL DIVIDE AND CONQUER ALGORITHMS FOR THE SYMMETRIC EIGENVALUE DECOMPOSITION AND THE SVD
STABLE AND EFFICIENT SPECTRAL DIVIDE AND CONQUER ALGORITHMS FOR THE SYMMETRIC EIGENVALUE DECOMPOSITION AND THE SVD
复制标题
DOI：
10.1137/120876605
复制
发表时间：
2013-01-01
影响因子：
3.1
通讯作者：
Higham, Nicholas J.
中科院分区：
文献类型：
--
作者：
Nakatsukasa, Yuji;Higham, Nicholas J.
谱分治算法通过递归地计算谱子集的不变子空间，并利用它将问题分解为两个更小的子问题，从而解决所有特征值和特征向量的特征值问题。在过去的40年里，已经开发了许多这样的算法，通常是由并行计算推动的，最近的目的是实现最小的通信成本。然而，现有的算法都没有被证明是后向稳定的，并且它们的算术代价都比目前使用的标准算法高得多。对于对称特征值问题和奇异值分解问题，我们提出了新的向后稳定的谱分治算法，得到了Ballard，Demmel，Holtz和Schwartz最近得到的通信代价的下界，并且运算次数在标准算法的一个小的恒定因子内。新算法建立在极分解的基础上，并利用了Nakatsukasa，Bai和Gygi最近开发的基于QR的动态加权Hley算法，该算法使用基于QR因式分解和矩阵乘法的三次收敛迭代来计算极分解。在通信成本主导算术成本的情况下，这些算法在高效、数值稳定的计算方面具有巨大的潜力。
Spectral divide and conquer algorithms solve the eigenvalue problem for all the eigen-values and eigenvectors by recursively computing an invariant subspace for a subset of the spectrum and using it to decouple the problem into two smaller subproblems. A number of such algorithms have been developed over the last 40 years, often motivated by parallel computing and, most recently, with the aim of achieving minimal communication costs. However, none of the existing algorithms has been proved to be backward stable, and they all have a significantly higher arithmetic cost than the standard algorithms currently used. We present new spectral divide and conquer algorithms for the symmetric eigenvalue problem and the singular value decomposition that are backward stable, achieve lower bounds on communication costs recently derived by Ballard, Demmel, Holtz, and Schwartz, and have operation counts within a small constant factor of those for the standard algorithms. The new algorithms are built on the polar decomposition and exploit the recently developed QR-based dynamically weighted Halley algorithm of Nakatsukasa, Bai, and Gygi, which computes the polar decomposition using a cubically convergent iteration based on the building blocks of QR factorization and matrix multiplication. The algorithms have great potential for efficient, numerically stable computations in situations where the cost of communication dominates the cost of arithmetic.