Fast QR factorization of Vandermonde matrices
type: Item
instance of: scholarly article
title: Fast QR factorization of Vandermonde matrices
zbMATH Open document ID: 0687.65025
DOI: 10.1016/0024-3795(89)90652-6
published in: Linear Algebra and its Applications
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65F10
zbMATH DE Number: 4126569
zbMATH Keywords: exponential mode fitting
zbMATH Keywords: Prony's two step algorithm
zbMATH Keywords: Vandermonde matrix
zbMATH Keywords: least squares solution
zbMATH Keywords: normal equations
zbMATH Keywords: Hilbert type matrix
zbMATH Keywords: QR factorization
zbMATH Keywords: fast algorithm
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: complexity
author: Cèdric J. Demeure
MaRDI profile type: Publication
full work available at URL: 0024-3795(89)90652-6
OpenAlex ID: W1972706155
cites work: Q3231529
cites work: Algebraic methods for Toeplitz-like matrices and operators
cites work: Efficient solution of linear systems of equations with recursive structure
cites work: Linear complexity parallel algorithms for linear systems of equations with recursive structure
cites work: Q5794082
cites work: Q5185900
cites work: A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
description: scientific article; zbMATH DE number 4126569