Orthogonal eigenvectors without Gram-Schmidt

B. Parlett, UC Berkeley, USA

Wednesday, April 23
at 16.30
in HG E1.2

We give an outline of the ideas that lead to a provably O(n²) method for computing eigenvectors (orthogonal to working accuracy) for symmetric tridiagonal matrices independently of each other however close the eigenvalues may be.

The most radical property is to replace the given T by a product like LL', L' being the transpose of L, which is known to define all its eigenvalues to high relative accuracy. The second departure from standard approaches is to use little known algorithms, called differential qd algorithms, that have a property called mixed high relative accuracy. These algorithms allow us to use several different representations of the data, roughly one for each cluster of close eigenvalues, each of which defines its small eigenvalues to high relative accuracy. Another essential ingredient in the procedure is a choice for a right hand side in inverse iteration that is guaranteed to be rich in the desired eigenvector. Lastly we use a tree structure to relate the vectors computed from different representations.

This is joint work with Inderjit Dhillon (Comp. Sci., Univ. Texas, Austin, Texas). The method never slower than the Divide and Conquer approach and sometimes much faster.