Error analysis of a fast partial-pivoting method for structured matrices

Douglas Robin Sweet; Richard P. Brent

doi:10.1117/12.211404

7 June 1995 Error analysis of a fast partial pivoting method for structured matrices

Douglas Robin Sweet, Richard P. Brent

Proceedings Volume 2563, Advanced Signal Processing Algorithms; (1995) https://doi.org/10.1117/12.211404
Event: SPIE's 1995 International Symposium on Optical Science, Engineering, and Instrumentation, 1995, San Diego, CA, United States

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.

Citation Download Citation

Douglas Robin Sweet and Richard P. Brent "Error analysis of a fast partial pivoting method for structured matrices", Proc. SPIE 2563, Advanced Signal Processing Algorithms, (7 June 1995); https://doi.org/10.1117/12.211404

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available