ANU Computer Science Technical Reports

TR-CS-95-03

Douglas R. Sweet and Richard P. Brent.
Error analysis of a partial pivoting method for structured matrices.
June 1995.
Shorter version to appear in Advanced Signal Processing Algorithms, Proc. SPIE 40th Annual Meeting, San Diego, July 1995. (rpb157tr).

[POSTSCRIPT (144492 bytes)]

Abstract: (abridged) Many matrices that arise in the solution of signal processing problems have a special displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of Toeplitz type. A recent method of Gohberg, Kailath and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. We perform a rounding error analysis on the Cauchy and Toeplitz variants of this method. It is shown that the error growth can be much larger than that encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed.

Technical Reports <Technical.Reports@cs.anu.edu.au>

Last modified: Tue May 13 14:55:38 EST 1997