Title:  Some New Progress in Matrix Computations 

Abstract: In this talk, we discuss our recent work on computing the singular 
value decomposition (SVD)  and analyzing numerical methods for solving
semi-definite programs (SDPs). 

We start with the special problem of updating the SVD, which is by
itself an important problem in signal processing applications.
Taking advantage of the rich analytic and algebraic structures in this
problem, we develop a version of the well-known fast multipole method
(FMM) to update the SVD at a cost about a factor of O(n)
less than direct updating. This method is a 1-dimensional
version of FMM that is based on judicious use of Chebyshev
polynomials and takes full advantage of level-3 BLAS 
whenever possible. For n = 1000, it can update the SVD with roughly
the same amount of accuracy as the direct method but is up to 10 times
faster. Better yet, this method is provably stable. Based on this
method, we further develop stable methods for solving the symmetric
eigenvalue problem and the SVD. Some recent work for solving these
problems is considered such a complete resolution that it is referred
to as the "Holy Grail". Interestingly, our methods are faster than the
Grail and yet provably stable.

We also consider issues arising from numerical methods for solving
the semi-definite programs (SDPs). The SDPs have a wide range of
applications in areas such as control theory and combinatorial
optimization. Over the last decade or so, a large number of
interior-point methods have been developed to solve the SDPs. However,
properly implementing these methods proved to be a surprisingly big 
challenge. We have systematically analyzed these methods in finite precision. 
This analysis provides a clear understanding of how SDP methods work in finite
precision. It has led to more robust implementations of SDP methods and discovery of 
more reliable and efficient methods.

This is joint work with Dr. Xuebin Chi


Ming