Nakatsukasa, Yuji; Higham, Nicholas J. Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD. (English) Zbl 1326.65049 SIAM J. Sci. Comput. 35, No. 3, A1325-A1349 (2013). Authors’ abstract: 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 G. Ballard et al. [SIAM J. Sci. Comput. 32, No. 6, 3495–3523 (2010; Zbl 1238.65018)], 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 Y. Nakatsukasa et al. [SIAM J. Matrix Anal. Appl. 31, No. 5, 2700–2720 (2010; Zbl 1215.65081)], 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. Reviewer: Juri M. Rappoport (Moskva) Cited in 3 ReviewsCited in 15 Documents MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 15A23 Factorization of matrices 65F30 Other matrix algorithms (MSC2010) 65G50 Roundoff error Keywords:symmetric eigenvalue problem; singular value decomposition; polar decomposition; QR factorization; dynamically weighted Halley iteration; subspace iteration; numerical stability; backward error analysis; communication-minimizing algorithms; spectral divide and conquer algorithms; eigenvectors Citations:Zbl 1238.65018; Zbl 1215.65081 Software:CALU; LAPACK; mctoolbox; Algorithm 880; nag PDFBibTeX XMLCite \textit{Y. Nakatsukasa} and \textit{N. J. Higham}, SIAM J. Sci. Comput. 35, No. 3, A1325--A1349 (2013; Zbl 1326.65049) Full Text: DOI Link