The research part of this CAREER project develops accurate and efficient numerical methods for a number of important problems including high relative accuracy (tiny percentage error) eigenvalue and singular value computations, updating the singular value decomposition (SVD), and distance problems in linear systems and control computations. Although current methods for solving them are abundant, many important questions remain unanswered. For example, a large number of recent papers describe numerical methods to compute all eigenvalues and singular values to high relative accuracy for a few isolated special classes of matrices, but a common explanation and a common numerical method are missing. As another example, the ability to rapidly update the SVD is critical in signal processing applications since problems are often real- time, but none of the current methods is efficient enough for this purpose. A goal is to provide a common explanation and a common numerical method for high relative accuracy eigenvalue and singular value computations. It turns out that the common explanation and common numerical method are applicable to many new interesting classes of matrices, arising from areas as diverse as combinatorics and numerical solution of ODE's and PDE's. The project also aims at providing rapid methods for updating the SVD, hence removing a major bottleneck in SVD-based methods for various signal processing applications. The education part of the project is to develop software tools so that students taking abstract mathematics courses can clearly envision and play with the sometimes abstract objects and results on the World-Wide Web with vivid graphical display. The plan also includes new graduate courses in numerical linear algebra with scientific and engineering applications.
