Stability Analysis and Fast Algorithms for Triangularization of Toeplitz Matrices

 Haesun Park 
        Computer Science Department, University of Minnesota,
      	Minneapolis, MN 55455, U.S.A. (e-mail: hpark@cs.umn.edu).
        The work of this author was supported in part by 
        the National Science Foundation grant CCR-9209726.}
 
 Lars Eld\'en
        Department of Mathematics, 
        Link\"oping University, S--581\ 83 Link\"oping, Sweden,
	(e-mail: laeld@math.liu.se).


Revised May 25, 1995.}

ABSTRACT

A new $O(mn)$ algorithm for triangularizing an $m \times n$
Toeplitz matrix is presented. 
The algorithm is based on the previously developed 
recursive algorithms that exploit the Toeplitz structure and compute
each row of the triangular factor via updating and downdating steps.
A forward error analysis for this existing recursive algorithm
is presented, which allows us to
monitor the conditioning of the problem, and use the
method of corrected semi-normal equations to obtain higher accuracy
for certain ill-conditioned matrices.  Numerical experiments show
that the new algorithm improves the accuracy significantly while the
computational complexity stays in $O(mn)$.