Optimization and Systems Theory Seminar
March 18, 1997, 15.00-16.00


Professor William B. Gragg,
Department of Mathematics,
Naval Postgraduate School,
Monterey, California, USA

Stabilization of the unitary Hessenberg QR algorithm

Pisarenko's method is a fundamental algorithm of statistical signal processing and the spectral analysis of stationary time series. Its first phase involves finding the noise subspace, the eigenspace associated with the smallest eigenvalue(s) of a positive definite Toeplitz matrix, in one formulation. This stimulates much recent activity related with fast solution of Toeplitz systems of linear equations. The key mathematical ideas here go back to Schur (1917). The second phase, correctly formulated, involves computing eigenvalues, and first elements of normalized eigenvectors, of unitary Hessenberg (almost triangular) matrices. If this problem is formulated "as usual", as an eigenproblem for a companion matrix, it can be arbitrarily badly ill-conditioned. The problem in the correct formulation is well- conditioned, with its input data coming directly from Schur's algorithm, which is used for the first phase. In 1984 we showed that, in principle, this problem could be solved by the unitary Hessenberg QR (uhqr) algorithm, an O(n^2) process. There is also an inverse algorithm (iuhqr) which allows removal of data. Together, these two algorithms allow adaptive recursive least squares polynomial fits of data defined on the unit circle in the complex plane (trigonometic polynomials). These techniques have been "developed" in a number of papers with Ammar and Reichel. There are also continuous "Schur flows", analogous with "Jacobi flows" on real symmetric tridiagonals (Deift) but we shall not get into these pretty, but very academic, questions here. Our recent (1997!) stabilization of these algorithms is the main topic of this talk. It involves a few cute tricks, like the ones every person who does Scientific Computing should learn to do. Now we can handle problems of (essentially) arbitrarily high order. The mathematical lore of this whole area is very beautiful. Our result shows that it can also be very practical. Time should permit a brief introduction to to the (Laurent-) Pade table. This was the vehicle for my entry into this area. It has manifold other applications, including model reduction.


Calendar of seminars
Last update: March 10, 1997 by Anders Forsgren, andersf@math.kth.se.