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 (Publisher's DOI)






Full text (publisher's version  intranet only)





