Technical Report Number
We present a new algorithm for computing the QR factorization of an mxn Toeplitz matrix in O(mn) multiplications. The algorithm exploits the procedure for the rank-1 modification and the fact that successive columns of a Toeplitz matrix are related to each other. Both matrices Q and R are generated column by column, starting for their first columns. Each column is calculated from the previous column after rank-1 modification to the matrix R and a step of Gramm-Schmidt orthogonalization process applied to two auxiliary vectors.
Bojanczyk, Adam W., "The QR Decomposition of Toeplitz Matrices" Report Number: WUCS-87-1 (1987). All Computer Science and Engineering Research.