Many questions in signal processing can be formulated as problems for positive definite Toeplitz and unitary (or orthogonal) Hessenberg matrices. For example, systems of linear filtering, recursive estimation, time series analysis, as well as in image processing. Furthmore, Pisarenko frequency estimates, also of interest in signal processing, can be computed using Toeplitz and unitary Hessenberg matrices as follows: a Toeplitz eigenvalue problem is solved; the Schur parameters associated with the orthogonal polynomials defined implicitly by the Toeplitz matrix are then used to construct a certain unitary Hessenberg matrix; the eigenvalues of this matrix are the frequency estimates sought. Using the close connection between the theory of polynomials orthogonal on the unit circle and these problems of linear algebra, the investigators have already developed competitive numerical methods for computing eignevalues and eigenvectors of unitary Hessenberg matrices for solving the inverse eigenvalue problem for unitary matrices, and for solving systems of linear equations with positive definite symmetric Toeplitz matrices. The purpose of this work is to further speed up the algorithms for the above problems and to investigate how they can be implemented efficiently on computers with vector and parallel architectures. The investigators also wish to gain a better understanding about the numerical properties, such as stability, of some of the algorithms mentioned so that fast reliable computer programs can be developed. The work should result in published fast stable algorithms for the above problems. Another application of fast Toeplitz solvers is the solution of integral equations. Iterative schemes with Toeplitz matrices as preconditioners will also be investigated. Encouraging preliminary results for an integral equation of plane potential theory on a piecewise smooth curve currently exist. This is a model problem for integral equations on a piecewise smooth curve or surface with a displacement kernel. Such integral equations are common in applications of the boundary element method. The project will investigate when Toeplitz matrices make good preconditioners. More generally, it will continue the investigation in and develop fast solution methods for integral equations by exploiting the structure of the system of equations obtained after discretization. Both direct and iterative schemes will be considered.
