Share Email Print

Proceedings Paper

Parallel QR Decomposition Of Toeplitz Matrices
Author(s): Adam W. Bojanczyk; Richard P. Brent; Frank R. de Hoog
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 4 April 1986
PDF: 6 pages
Proc. SPIE 0696, Advanced Algorithms and Architectures for Signal Processing I, (4 April 1986); doi: 10.1117/12.936873
Show Author Affiliations
Adam W. Bojanczyk, Washington University (United States)
Richard P. Brent, Australian National University (Australia)
Frank R. de Hoog, CSIRO (Australia)

Published in SPIE Proceedings Vol. 0696:
Advanced Algorithms and Architectures for Signal Processing I
Jeffrey M. Speiser, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?