UNIVERSITY OF COLORADO AT DENVER

PLACE: Mathematics Conference Room 626 UCD Building, 1250 14th St., Denver

TIME: 12:45 pm

DATE: February 28, 2000

Title:
        New Perspective in the Matrix Eigenvalue Problem

Speaker: Prof. B.N.Parlett
         Math. Dept. Univ. Calif., Berkeley

Abstract.
   We begin with a discussion of why eigenvalue computations
can give rise to mathematical questions of interest even to those 
with no connection to scientific computing.
The situation for small (n < 500) symmetric matrices is in good
shape as users of Matlab well know.  However there is one outstanding
problem: the method that computes orthogonal eigenvectors takes
O(n^3) operations and theory says that the job can be done in O(n^2)
operations when the matrix is tridiagonal.  Dense matrices are reduced 
to this form in a preliminary phase.
Current O(n^2) methods break down when the eigenvalues
are close together and then resort to Gram-Schmidt to be safe.

We will present some new ideas that lead to a way to compute
eigenvectors for different eigenvalues with no mutual communication
(perhaps on different processors) however close those eigenvalues
may be.  The cost is O(n) per eigenvalue.

One idea is that the given tridiagonal T must be discarded and
replaced by a better representation (the triangular factors).
Another key ingredient are some new non-linear transformations
called differential qd algorithms.  Finally there is a neat and
inexpensive way to obtain a good starting vector for inverse
iteration.

Expertise in matrix computations is NOT a prerequisite for this talk.