Fast QR factorization of Cauchy-like matrices

In this paper, we present two fast numerical methods for computing the QR factorization of an n×n Cauchy-like matrix C, C=QR, with data points lying on the real axis or on the unit circle in the complex plane. It is shown that the rows of the Q-factor of C are the eigenvectors of a rank structured matrix partially determined by some prescribed spectral data. This property establishes a basic connection between the computation of Q and the solution of an inverse eigenvalue problem for a rank structured matrix. Exploiting the structure of this problem enables us to develop quadratic time, i.e., O(n2), QR factorization algorithms.