The authors present a new O(mn) algorithm for triangularizing an m /spl times/ n Toeplitz matrix. 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. We monitor the conditioning of the downdating problems, and use the method of corrected semi-normal equations to obtain higher accuracy for ill-conditioned downdating problems. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in O(mn). >