ISSN:
1572-9265
Keywords:
Toeplitz determinants
;
rational interpolation
;
coupled Vandermonde matrices
;
65F40
;
65D05
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Let n be a positive integer, let $$a_{ - n{\text{ + }}1} ,...,a_{ - 1} ,a_0 ,a_1 ,...,a_{n - 1} $$ be complex numbers and let $$T: = {\text{ [}}a_{k - 1} {\text{]}}_{k,l = 0}^{n - 1} $$ 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 $${\text{O(}}N\log ^2 N{\text{)}}$$ , 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1019189109351
