Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD

By Yuji Nakatsukasa, Nicholas John Higham. 2013

112 citations recorded by the source corpus.

Spectral divide and conquer algorithms solve the eigenvalue problem for all the eigenvalues 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 decompos...

Subfields: Computational Mathematics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, positive): “Finally, our approach exploits the power iteration method [56] to compute the largest eigenvalue of TM k , which is backpropagation-friendly.”
Learning to Drop: Robust Graph Neural Network via Topological Denoising (2020, methodology): “The Power Iteration (PI) method with deflation procedure is one way to solve this problem [34, 36, 47].”