QR-factorization of Displacement Structured Matrices Using a Rank Structured Matrix Approach
Steven Delvaux, Luca Gemignani, Marc Van Barel · Birkhäuser Basel eBooks · 2010
A general scheme is proposed for computing the QR-factorization of certain displacement structured matrices, including Cauchy-like, Vandermonde- like, Toeplitz-like and Hankel-like matrices, hereby extending some earlier work for the QR-factorization of the Cauchy matrix. The algorithm employs a chasing scheme for the recursive construction of a diagonal plus semiseparable matrix of semiseparability rank r, where r is equal to the given displacement rank. The complexity is O(r 2 n 2 ) operations in the general case, and O(rn 2 ) operations in the Toeplitz- and Hankel-like case, where n denotes the matrix size. Numerical experiments are provided.