Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants
type: Item
instance of: scholarly article
title: Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants
zbMATH Open document ID: 0960.65055
DOI: 10.1023/A:1019189109351
author: Peter Kravanja
author: Marc van Barel
published in: Numerical Algorithms
publication date: 2000-11-22T00:00:00Z
review text: The authors present a superfast algorithm for computing the determinant of a nonsingular \(n \times n\) Toeplitz matrix \(T\) with complex components. The arithmetic complexity of the new algorithm is \(O(N \log^2 N)\) where \(N\) denotes the smallest power of 2, which is larger than or equal to \(n\). It is shown that det\(T\) can be computed from the determinant of a coupled Vandermonde matrix \(V_C\). The latter is related to a linearized rational interpolation problem at the roots of unity. The determinant of \(V_C\) is computed in an efficient and accurate way by multiplying the pivots that appear in the superfast interpolation algorithm presented by the authors in previous publications. Results from numerical experiments are also reported to illustrate the accuracy and execution time of the new algorithm.
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 65D05
zbMATH DE Number: 1534766
zbMATH Keywords: Toeplitz determinants
zbMATH Keywords: rational interpolation
zbMATH Keywords: Vandermonde matrices
zbMATH Keywords: superfast algorithm
zbMATH Keywords: arithmetic complexith
zbMATH Keywords: numerical experiments
reviewed by: Neli Dimitrova
MaRDI profile type: Publication
full work available at URL: a:1019189109351
OpenAlex ID: W59552121
description: scientific article; zbMATH DE number 1534766