Spectral divide-and-conquer algorithms for matrix eigenvalue problems (Fusion of theory and practice in applied mathematics and computational science)

Abstract

Conventional algorithms for the (symmetric or non-symmetric) eigenvalue decomposition and the singular value decomposition (SVD) are based on initially reducing the matrix to a condensed (tridiagonal, Hessenberg or bidiagonal) form. Unfortunately, they are not optimal in view of recent trends in computer architectures, which require minimizing communication along with the arithmetic cost. With collaborators thc author has been developing spectral divide-and-conquer algorithms, which can achieve both requirements. Spectral divide-and-conquer algorithms recursively decouple the problem into two smaller subproblems. This report summarizes the developments thus far and gives an overview of spectral divide-and-conquer algorithms for eigenvalue problems and the SVD, and point to ongoing directions. A large bulk of this report consists of collaborations with Nicholas J. Higham [19] and Roland W. Freund [20].