3 ms·

Huh, weird that this is making such big headlines. A fast (O(n log n)) inverse chirp z-transform was described 16 years ago in Alin Bostan's PhD thesis https://

by fdej 7y ago

Huh, weird that this is making such big headlines. A fast (O(n log n)) inverse chirp z-transform was described 16 years ago in Alin Bostan's PhD thesis https://specfun.inria.fr/bostan/these/These.pdf https://specfun.inria.fr/bostan/these/These.pdf Also in this more compact paper by Bostan and Schost: https://specfun.inria.fr/bostan/publications/BoSc05.pdf https://specfun.inria.fr/bostan/publications/BoSc05.pdf The new algorithm may be a different way to do it (I haven't studied the paper), but the authors ought to have cited previous work. Where does Nature find their referees?

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 ago
  That 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 ago
  The (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.

by fdej 7y ago

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 ago
That 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 ago
The (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.