This project will develop fast and accurate numerical algorithms for linear algebra problems arising in engineering computations. One class of such problems concerns matrices with displacement structure. This is a general algebraic concept and includes the well-known classes of Toeplitz, Hankel, Vandermonde and Cauchy matrices. In practice there is the need for solving rapidly and accurately, both exactly-determined and over-determined linear systems involving such matrices. Furthermore, in some applications like inverse scattering for geophysical problems, there is also the need for the rapid factorization of such matrices. Another related class of problems arises in adaptive filtering applications, where there is a need to solve rapidly and accurately a sequence of structured linear problems that are related by low-rank changes. In a different vein, the computation of the eigenvalues and eigenvectors of symmetric pencils is another important problem. It frequently arises in finite-element analysis of engineering structures and associated model-reduction problems. New models and fast algorithms for the analysis of linear algebra problems with large bounded uncertainties will also be developed.
