ON THE STABILITY OF THE BAREISS AND RELATED TOEPLITZ FACTORIZATION ALGORITHMS

A. W. BOJANCZYK, R. P. BRENT, F. R. DE HOOG, AND D. R. SWEET

Abstract

This paper contains a numerical stability analysis of factorization algorithms for computing the Cholesky decomposition of symmetric positive definite matrices of displacement rank 2. The algorithms in the class can be expressed as sequences of elementary downdating steps. The stability of the factorization algorithms follows directly from the numerical properties of algorithms for realizing elementary downdating operations. It is shown that the Bareiss algorithm for factorizing a symmetric positive definite Toeplitz matrix is in the class and hence the Bareiss algorithm is stable. Some numerical experiments that compare behavior of the Bareiss algorithm and the Levinson algorithm are presented. These experiments indicate that in general (when the reflection coefficients are not all of the same sign) the Levinson algorithm can give much larger residuals than the Bareiss algorithm.

Comments

Only the Abstract is given here. The full paper will appear as [2]. For a preliminary version, see [1].

References

1. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, Stability Analysis of Fast Toeplitz Linear System Solvers, Report CMA-MR17-91, Centre for Mathematical Analysis, ANU, August 1991, 23 pp. rpb126tr.

2. A. W. Bojanczyk, R. P. Brent, F. R. de Hoog, and D. R. Sweet, “On the stability of the Bareiss and related Toeplitz factorization algorithms”, SIAM J. Matrix Anal. Appl., to appear. Available as Report TR-CS-93-14, CS Lab, ANU, November 1993, 18 pp. rpb144.

(Bojanczyk) School of Electrical Engineering, Cornell University, Ithaca, NY 14853

(Brent) Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200

(de Hoog) CSIRO Division of Mathematics and Statistics, GPO Box 1965, Canberra, ACT 2601

(Sweet) Electronics Research Laboratory, Defense Science and Technology Organisation, Salisbury, SA 5108

1991 Mathematics Subject Classification. Primary 65F05; Secondary 65G05, 47B35, 65F30.

Key words and phrases. Toeplitz matrix, Bareiss algorithm, Levinson algorithm, numerical stability, positive-definite matrix, symmetric matrix.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1993, the authors.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb144a typeset using AMS-L^{A}TEX