3 ms·
The inverse chirp z-transform in that second paper is described as follows: Let us now focus on the computation of the inverse chirp transform. The idea is to
by yorwba 7y ago
The inverse chirp z-transform in that second paper is described as follows:
Let us now focus on the computation of the inverse chirp transform. The
idea is to use the Newton basis for intermediate computations: first perform
a Newton interpolation, then perform a conversion from the Newton basis to
the monomial basis. Both steps have complexities M(n) + O(n), which gives
the estimate of 2M(n) + O(n)
The function M(n)
denotes the cost of multiplying univariate polynomials of degree less
than n. Using FFT-based multiplication algorithms, M(n) can be taken in
O(n log(n) log(log(n)))
So they did not reach O(n log n).
- fdej 7y agoThat complexity bound applies to polynomials over more general coefficient rings which may not have roots of unity. Over the usual complex numbers the complexity is O(n log n).
- labawi 7y agoThe (log (log n)) factor in asymptotic complexity notation is almost meaningless. * log₂ log₂ 2⁶⁴ = 6, which is essentially a constant factor if N<2⁶⁴ * to be fair, you may need to consider (log log N), or even (log log N)² factors hidden in native computer word size if exceeding N = 2⁶⁴. * Today's machines have gone far from the classical computational complexity models, where data access patterns and locality matter orders of magnitude more than a factor which is essentially <= 6. I would not immediately discard a (log log n) factor, but for nearly all purposes, I would mostly disregard it. So if the only difference were O(n·log n) vs O(n·log n·log log n), then no, it would not be a big deal.