A NOTE ON DOWNDATING THE CHOLESKY FACTORIZATION

A. W. BOJANCZYK, R. P. BRENT, P. VAN DOOREN, AND F. R. DE HOOG

Abstract

We analyse and compare three algorithms for “downdating” the Cholesky factorization of a positive definite matrix. Although the algorithms are closely related, their numerical properties differ. Two algorithms are stable in a certain “mixed” sense, while the other is unstable. In addition to comparing the numerical properties of the algorithms, we compare their computational complexity and their suitability for implementation on parallel or vector computers.

Comments

Only the Abstract is given here. The full paper appeared as [2]. For an application of downdating, see [1].

References

1. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, “QR factorization of Toeplitz matrices”, Numerische Mathematik 49 (1986), 81–94. MR 87k:65050. rpb092.

2. A. W. Bojanczyk, R. P. Brent, P. van Dooren and F. H. de Hoog, “A note on downdating the Cholesky factorization”, SIAM J. Sci. Stat. Comput. 8 (1987), 210–221. MR 88d:65049. A modified version appeared in Algorithms and Applications on Vector and Parallel Computers (edited by H. J. J. te Riele, Th. J. Dekker and H. A. van der Vorst), Elsevier, Amsterdam, 1987, 307–323. MR 89i:65042. Also appeared as Report CMA-R19-85, CMA, ANU, August 1985, 20 pp. rpb095.

(Bojanczyk, Brent) Centre for Mathematical Analysis, Australian National University, Canberra, ACT 2601, Australia

(van Dooren) Philips Research Laboratory, Av. van Becelaere 2, Box 8, B-1170 Brussels, Belgium

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

Current address, Bojanczyk: Department of Computer Science, Washington University, St Louis, Missouri 63130, USA

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

Key words and phrases. Cholesky factorization, numerical stability, computational complexity, parallel computation, forward error analysis, backward error analysis, mixed stability, downdating, updating, rank-one correction, Sigma-unitary transformation, hyperbolic transformation, orthogonal transformation.

We thank Professor G. H. Golub and Dr. M. A. Saunders for their helpful comments on a draft of this paper.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1987, SIAM.

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