Share Email Print

Proceedings Paper

Error analysis of a fast partial-pivoting method for structured matrices
Author(s): Douglas Robin Sweet; Richard P. Brent
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Many matrices that arise in the solution of signal processing have a special displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of a Toeplitz type. A recent method of Gohberg, Kailath, and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. In this paper, a rounding error analysis is performed on the Cauchy and Toeplitz variants of the GKO method. It is shown the error growth depends on the growth in certain auxiliary vectors, the generators, which are computed by the GKO algorithms, It is also shown that in certain circumstances, the growth in the generators can be large, and so the error growth is much larger than would be encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed which may circumvent this problem.

Paper Details

Date Published: 7 June 1995
PDF: 15 pages
Proc. SPIE 2563, Advanced Signal Processing Algorithms, (7 June 1995); doi: 10.1117/12.211404
Show Author Affiliations
Douglas Robin Sweet, Defence Science and Technology Organisation (Australia)
Richard P. Brent, Australian National Univ. (Australia)

Published in SPIE Proceedings Vol. 2563:
Advanced Signal Processing Algorithms
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top