### 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.
*