Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants (Q1587027)

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.