CONTINUATION METHODS FOR THE COMPUTATION OF ZEROS OF SZEGO POLYNOMIALS

Let {phi(j)}(infinity)(j=0) be a family of monic polynomials that are orthogonal with respect to an inner product on the unit circle. The po lynomials phi(j) arise in time series analysis and are often referred to as Szego polynomials or Levinson polynomials. Knowledge about the l ocation of their zeros is important for frequency analysis of time ser ies and for filter implementation. We present fast algorithms for comp uting the zeros of the polynomials phi(n) based on the observation tha t the zeros are eigenvalues of a rank-one modification of a unitary up per Hessenberg matrix H-n(0) of order n. The algorithms first determin e the spectrum of H-n(0) by one of several available schemes that requ ire only O(n(2)) arithmetic operations. The eigenvalues of the rank-on e perturbation are then determined from the eigenvalues of H-n(0) by a continuation method. The computation of the n zeros of phi(n) in this manner typically requires only O(n(2)) arithmetic operations. The alg orithms have a structure that lends itself well to parallel computatio n. The latter is of significance in real-time applications. (C) Elsevi er Science Inc., 1996