Title
Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants Coupled Vandermonde matrices and the superfast computation of Toeplitz determinants
Author
Faculty/Department
Faculty of Social Sciences. Communication Sciences
Publication type
article
Publication
Basel ,
Subject
Mathematics
Computer. Automation
Source (journal)
Numerical algorithms. - Basel
Volume/pages
24(2000) :1/2 , p. 99-116
ISSN
1017-1398
ISI
000088345500007
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Abstract
Let n be a positive integer, let a􀀀n+1, : : : , a􀀀1, a0, a1, : : : , an􀀀1 be complex numbers and let T := [ak􀀀l]n􀀀1 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.
E-info
https://repository.uantwerpen.be/docman/iruaauth/1f33dd/e60c6c3a5cf.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000088345500007&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000088345500007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000088345500007&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848