BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//NA-M-92-01
       ENTRY:: January 28, 1996
ORGANIZATION:: Stanford University, Department of Computer Science, Numerical
               Analysis Project
       TITLE:: A look-ahead algorithm for the solution of general Hankel
               systems
        TYPE:: Manuscript
      AUTHOR:: Freund, Roland W.
      AUTHOR:: Zha, Hongyuan
        DATE:: January 1992
       PAGES:: 32
    ABSTRACT:: The solution of linear systems of equations with Hankel
               coefficient matrices can be computed with only $O(n^2)$
               arithmetic operations, as compared to $O(n^3)$ operations for
               the general case. However, the classical Hankel solvers
               require the nonsingularity of all leading principal
               submatrices of the Hankel matrix. The known extensions of
               these algorithms to general Hankel systems can handle only
               exactly singular submatrices, but not ill-conditioned ones,
               and hence they are numerically unstable. In this paper, a
               stable procedure for solving general nonsingular Hankel
               systems is presented, using a look-ahead technique to skip
               over singular or ill-conditioned submatrices. The proposed
               approach is based on a look-ahead variant of the nonsymmetric
               Lanczos process that was recently developed by Freund,
               Gutknecht, and Nachtigal. We first derive a somewhat more
               general formulation of this look-ahead Lanczos algorithm in
               terms of formally orthogonal polynomials, which then yields
               the look-ahead Hankel solver as a special case. We prove some
               general properties of the resulting look-ahead algorithm for
               formally orthogonal polynomials. These results are then
               utilized in the implementation of the Hankel solver. We
               report some numerical experiments for Hankel systems with
               ill-conditioned submatrices.
       NOTES:: [Adminitrivia V1/Prg/19960128]
         END:: STAN//NA-M-92-01