Eigenvalue computation has pervasive applications across most
branches of science and engineering. In this talk I will present our
recent highly accurate and efficient algorithms for structured
eigenvalue problems.

In finite precision computations the
accuracy of the tiniest eigenvalues can quickly be lost to round-off
errors. This is unfortunate since these tiny eigenvalues are often
very accurately determined by the data and are of considerable
physical significance. For example, in Electrical Impedance
Tomography, the SVD of a particular Vandermonde matrix allows us to
recover the conductivity of the interior of an object. A
similar approach in inverse scattering gives rise to the same
computational problem. Another example is 3D target recognition in
which the eigenvalues of the covariance matrix of a vehicle's 3D
coordinates become the 'signature' that can be used to recognize the
vehicle; this method is independent of the angle of observation and
hence overcomes a major drawback in two dimensions.

The foregoing applications are
examples of problems that have benefited immensely from the new
highly accurate eigenvalue algorithms that we have developed. Our
algorithms, unlike the conventional ones, respect and exploit the
underlying combinatorial and algebraic matrix structure and compute
all eigenvalues to high relative accuracy without the need for extra
precision.

In the talk I will focus in particular on our new algorithm for
computing eigenvalues of random matrices, a computational problem
whose solution has eluded researchers for over 40 years.

Dr. Koev did his doctoral work under the supervision of Professor
James Demmel and received his Ph.D. in mathematics from the
University of California, Berkeley in 2002. He is currently a
postdoctoral researcher in the mathematics department at M.I.T. His
interests are in accurate and efficient matrix computations, applied
multivariate statistical analysis and random matrix theory.