STABILITY ANALYSIS OF A GENERAL TOEPLITZ SYSTEM SOLVER

ADAM W. BOJANCZYK, RICHARD P. BRENT, AND FRANK R. DE HOOG

Abstract

We show that a fast algorithm for the QR factorization of a Toeplitz or Hankel matrix A is weakly stable in the sense that R^{T} R is close to A^{T} A. Thus, when the algorithm is used to solve the semi-normal equations R^{T} Rx = A^{T} b, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear system Ax = b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem min ∥Ax − b∥_{2}.

Comments

Only the Abstract is given here. The full paper appeared as [1], based in part on [3] and the preliminary report [2].

References

[1] A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, Stability analysis of a general Toeplitz system solver, Numerical Algorithms 10 (1995), 225-244.

[2] A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, A weakly stable algorithm for general Toeplitz systems, Technical Report TR-CS-93-15, CSL, ANU, August 1993 (revised June 1994). ftp://nimbus.anu.edu.au/

 pub/Brent/rpb143tr.dvi.Z

[3] R. P. Brent, Parallel algorithms and numerical stability for Toeplitz systems, invited paper presented at SIAM Conference on Linear Algebra in Signals, Systems and Control, Seattle, August 16-19, 1993.

 ftp://nimbus.anu.edu.au/pub/Brent/rpb143t.dvi.Z

School of Electrical Engineering, Cornell University, Ithaca, NY 14853-5401

E-mail address: adamb@toeplitz.ee.cornell.edu

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200

E-mail address: Richard.Brent@anu.edu.au

Division of Mathematics and Statistics, CSIRO, GPO Box 1965, Canberra, ACT 2601

E-mail address: frank@dmscanb.cbr.dms.csiro.au

1991 Mathematics Subject Classification. Primary 65F25; Secondary 47B35, 65F05, 65F30, 65Y05, 65Y10. Key words and phrases. Cholesky factorization, error analysis, Hankel matrix, least squares, normal equations,

orthogonal factorization, QR factorization, semi-normal equations, stability, Toeplitz matrix, weak stability. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, the authors. rpb143a typeset using AMS-L^{A}TEX.