Paper
4 April 1986 Parallel QR Decomposition Of Toeplitz Matrices
Adam W. Bojanczyk, Richard P. Brent, Frank R. de Hoog
Author Affiliations +
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.
© (1986) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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
Lens.org Logo
CITATIONS
Cited by 2 scholarly publications.
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Signal processing

Matrices

Algorithm development

Rubidium

Computer science

Computer architecture

Transform theory

RELATED CONTENT

Old And New Algorithms For Toeplitz Systems
Proceedings of SPIE (February 23 1988)
Two-step Gram-Schmidt downdating methods
Proceedings of SPIE (November 20 2001)
Alternative To The SVD: Rank Revealing QR-Factorizations
Proceedings of SPIE (April 04 1986)
Multiplicative and zero-crossing representations of signals
Proceedings of SPIE (October 11 1994)

Back to Top