Fast QR factorization of Vandermonde matrices (Q1263232)

Concerning the problem of fitting theoretical exponential modes to experimental data, the second step of Prony's two step algorithm from the year 1795 is considered here. For determining the coefficients, a system of linear equations is to be solved defined by a column Vandermonde matrix V. In case of \(m>n\), where m is the number of rows, n is the number of columns in V, the least squares solution is computed by solving the normal equations based on the Hilbert type matrix \(H=V^*V\). This solution is usually obtained by QR factorization. In this paper, a fast algorithm for computing the QR factors of a complex column Vandermonde matrix is developed, by taking advantage of the very special structure of V and H. A fast algorithm for Cholesky factorization of \(H^{-1}\) is derived using the technique of \textit{G. Heinig} and \textit{K. Rost} [Algebraic methods for Toeplitz like matrices and operators (1984; Zbl 0549.15013)]. This algorithm is used to derive an algorithm for determining the matrix Q in the factorization QR. The complexity of the algorithm is \(5mn+7n^ 2/2+O(m)\). The matrices Q and R may be computed independently. Two special cases for the row Vandermonde matrix with real elements or unit magnitude elements are also studied, and similar results are obtained.