On the stability of the Bareiss and related Toeplitz
factorization algorithms
144. 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 Analysis and Applications 16 (1995), 40-57.
MR 95k:65030.
Also appeared as Technical Report TR-CS-93-14, Computer Sciences Laboratory,
ANU, November 1993, 18 pp.
arXiv:1004.5510v1
Abstract:
dvi (3K),
pdf (67K),
ps (23K).
Paper:
dvi (32K),
pdf (225K),
ps (91K).
Technical Report:
dvi (31K),
pdf (201K),
ps (95K).
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 positive)
the Levinson algorithm is not stable; certainly it
can give much larger residuals than the Bareiss algorithm.
Comments
For a preliminary version, see [126].
The stability results were later generalised by
Chandrasekharan and Sayed
[SIAM J. Matrix Anal. Appl. 17 (1996), 950-983]
and (independently) by M. Stewart and Van Dooren
[SIAM J. Matrix Anal. Appl. 18 (1997), 104-118];
see [177, Sec. 5.2]
for a discussion.
Go to next publication
Return to Richard Brent's index page