Numerous applications in sciences, engineering and mathematics give rise to problems involving structured matrices such as Toeplitz, Hankel, Vandermonde, controllability, observability, Cauchy, Bezoutians, along with many other patterns of structure. In many of these applications the use of standard mathematical software tools (such as MATLAB, Mathematica, Maple, LAPACK, etc.) is not appropriate, because their ignoring of structure requires unnecessary storage as well as an extremely large amount of CPU time. Secondly, many structured matrices, e.g., Hankel, Pick, Hilbert, Vandermonde, are extremely ill- conditioned, so that all available standard methods often fail to produce even one correct digit in the computed solution. The objective of this project is the study of theoretical and computational problems related to structured matrices which arise in several applied areas, including signal and image processing, system theory, and control theory. New accurate fast and superfast algorithms will be developed for several new classes of structured matrices, arising in rational matrix interpolation and approximation problems with norm constraints, in Gaussian quadrature as well as in signal and image processing. Along with these direct methods, the approach will be used to design new classes of preconditioners based on discrete real transforms to speed- up the convergence of the conjugate gradient method for block Toeplitz-plus-Hankel matrices.
