A family H of square matrices is efficiently structured if the number of independent parameters required to specify an arbitrary n by n member of H is approximately proportional to n when n is large. Toeplitz, Hankel, and Toeplitz-plus-Hankel matrices are examples of efficiently structured matrices, as are matrices of a given displacement rank, as defined by T. Kailath and his coauthors. The purposes of the proposed research are (a) to develop fast algorithms for finding individual eigenvalue-eigenvector pairs for general classes of efficiently structured Hermitian matrices, analogous to the principal investigator's algorithms for Toeplitz and Toeplitz-plus-Hankel matrices; (b) to study spectral properties of Toeplitz matrices (especially, the relationship between the even and odd spectra of real symmetric Toeplitz matrices); (c) to investigate the possibility of devising fast algorithms for finding the real eigenvalues of nonsymmetric Toeplitz matrices; and (d) to consider the spectral properties of Toeplitz-Sturm matrices. Efficiently structured Hermitian matrices arise in many important physical and scientific applications, including statistical problems involving prediction of future values of a random variable based on observations of its past values, signal processing (the science of extracting information from transmitted signals), and geophysical applications including the study of free oscillations of the Earth and seismic phenomena such as earthquakes. In studying these problems it is often necessary to determine individual eigenvalues of efficiently structured matrices of very high order (in the thousands). One of the main objectives of the proposed research is to develop numerical methods for finding these eigenvalues by methods whose complexity (computational requirements) is proportional to the second power of the order of the matrix, rather than to the third power of the order, as it is for standard computational methods that do not take advantage of the special structure of the matrix.
