Computing Eigenvalues Rapidly and/or Accurately

James Demmel

Mathematics and Computer Science

University of California at Berkeley

demmel@cs.berkeley.edu

We discuss recent algorithms for computing eigenvalues of symmetric matrices and singular values of general matrices with high speed and/or high accuracy. Unfortunately both goals are not yet achievable simultaneously in all cases.

We begin with recent work, joint with M. Gu and H. Ren, on a divide-and-conquer algorithm for the SVD. This is currently the fastest serial algorithm available for current superscalar architectures and memory hierarchies.

Second, we describe a parallel algorithm, due to B. Parlett and I. Dhillon, for the symmetric tridiagonal eigenproblem. While still under development, this algorithm, which is similar to inverse iteration, promises to be highly accurate, guaranteed O(n^{2}) in cost, and embarrassingly parallel. It could become the algorithm of choice on serial as well as parallel machines.

Third, we discuss a family of high accuracy algorithms for the singular value decomposition, which greatly extend the class of matrices whose SVDs can be computed to high relative accuracy, i.e. with the smallest singular values computed with as many correct digits as the largest. This is joint work with M. Gu, S. Eisenstat, I. Slapnicar, K. Veselic, and Z. Drmac.