MCC Seminar

Inderjit Dhillon, University of Texas, Austin

DATE: Thursday, February 12, 2004
TIME: 11:00 A.M.
PLACE: 1003 MRL

TITLE: Fast Eigenvalue/Eigenvector Computation for Dense Symmetric Matrices

ABSTRACT

Computing the eigenvalues/eigenvectors of a dense symmetric matrix is a classical problem and usually proceeds in 3 phases: (i) reduce the matrix to tridiagonal form, (ii) solve the tridiagonal eigenproblem and (iii) back-transform to obtain eigenvectors of the original matrix. In this talk, we present the first O(n^2), numerically stable, embarrassingly parallel algorithm for phase (ii). All previous algorithms for this purpose were O(n^3) in complexity, and in practice, often accounted for 80% of the total time for solving large dense eigenproblems. The new algorithm achieves O(n^2) complexity by avoiding all Gram-Schmidt orthogonalization.

The crucial ingredients of the new algorithm are:

  1. using factored forms to achieve provably high relative accuracy,
  2. using "twisted factorizations" to compute approximate eigenvectors with provably small relative residual norms.
  3. using multiple factored forms to "separate" clustered eigenvalues, thereby automatically obtaining numerically orthogonal approximations to eigenvectors (no Gram-Schmidt).
An interesting facet of our work is that high accuracy in intermediate leads to a much faster overall algorithm.

Impressive speedups are obtained on matrices from the real-life applications of computational quantum chemistry (PNNL) and finite-element modeling (from Jeff Bennighof). The largest dense problem solved "in-core" on a 256-node parallel computer is of size 128,000 x 128,000 which takes about 8 hours of CPU time. A preliminary version of the sequential software is now included in the LAPACK public-domain library.

The work on the sequential algorithm is joint with Beresford Parlett of UC Berkeley, while the parallel algorithm has been developed jointly with Paolo Bientinesi and Robert van de Geijn of UT Austin.