Title 



Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants
 
Author 



 
Abstract 



Let n be a positive integer, let an+1, : : : , a1, a0, a1, : : : , an1 be complex numbers and let T := [akl]n1 k,l=0 be a nonsingular n n complex Toeplitz matrix. We present a superfast algorithm for computing the determinant of T. Superfast means that the arithmetic complexity of our algorithm is O(N log2 N), where N denotes the smallest power of 2 that is larger than or equal to n. We show that det T can be computed from the determinant of a certain coupled Vandermonde matrix. The latter matrix is related to a linearized rational interpolation problem at roots of unity and we show how its determinant can be calculated by multiplying the pivots that appear in the superfast interpolation algorithm that we presented in a previous publication.   
Language 



English
 
Source (journal) 



Numerical algorithms.  Basel  
Publication 



Basel : 2000
 
ISSN 



10171398
 
Volume/pages 



24:1/2(2000), p. 99116
 
ISI 



000088345500007
 
Full text (Publishers DOI) 


  
Full text (publishers version  intranet only) 


  
