| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 469
Steven Delvaux, Luca Gemignani, Marc Van Barel
Fast QR factorization of Cauchy-like matrices
Abstract
In this paper we present two fast numerical methods for computing the QR factorization of a Cauchy-like matrix C with data points lying on the real axis or on the unit circle in the complex plane. An orthogonal-triangular decomposition of a matrix A ∈ Cn × n is a product of a unitary matrix U, a middle triangular matrix T, and another unitary matrix V such that A = UTV. If A is displacement structured, then a UTV decomposition of A can be found by computing the QR factorization of an associated Cauchy-like matrix C obtained from A by unitary transformations. Moreover, It is shown that the rows of the Q-factor of C give 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. Based on this connection in this paper we present two fast numerical methods for computing the QR factorization of C. Exploiting the structure of the associated inverse eigenvalue problem enables us to yield quadratic time algorithms using a linear memory space.
report.pdf (268K) / mailto: M. Van Barel