Parallel QR Decomposition Of Toeplitz Matrices

Adam W. Bojanczyk; Richard P. Brent; Frank R. de Hoog

doi:10.1117/12.936873

4 April 1986 Parallel QR Decomposition Of Toeplitz Matrices

Adam W. Bojanczyk, Richard P. Brent, Frank R. de Hoog

Proceedings Volume 0696, Advanced Algorithms and Architectures for Signal Processing I; (1986) https://doi.org/10.1117/12.936873
Event: 30th Annual Technical Symposium, 1986, San Diego, United States

Abstract

We present a new algorithm for computing the QR factorization of an (m+1)x(n+1) Toeplitz matrix in O(mn) multiplications. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal mxn submatrices of the Toeplitz matrix are identical. The matrix R is generated row by row and the matrix Q column by column, starting from the first row and column respectively. Each row of R (column of Q) is calculated from the previous row (column) after three implicit modifications of rank-1 to the matrix R, one updating and two downdatings. The procedure for rank-1 updating is due to Gill, Golub, Murray and Saunders, while that for rank-1 downdating is new and can be regarded as the reverse of rank-1 updating. Both updating and downdating operate on rows of R (columns of Q) from left to right (from top to bottom) which makes efficient parallel implementation possible. The QR factorization can be obtained in O(m+n) parallel steps with 0(n) processors.

Citation Download Citation

Adam W. Bojanczyk, Richard P. Brent, and Frank R. de Hoog "Parallel QR Decomposition Of Toeplitz Matrices", Proc. SPIE 0696, Advanced Algorithms and Architectures for Signal Processing I, (4 April 1986); https://doi.org/10.1117/12.936873

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