Hacker News Reader

Comment by duped | Hacker News Reader

What applications require polynomial interpolation with such high order that an FFT is worth it? Why not use sinc interpolation if you're computing an FFT anyway?

sidenote: polynomial multiplication != interpolation

View on HN

Zero-knowledge proof generation, for one.

Edit, see for example: https://www.zprize.io/prizes/accelerating-ntt-operations-on-...

That’s pretty neat. I didn’t even think of finite fields when I made my other comment. Another example where mathematical curiosities prove useful in cryptography.

There's an aside in the linked section of CLRS that mentions that FFT based polynomial multiplication can be used for fast evaluation of Lagrange interpolation. I'm not aware of applications though, Lagrange interpolation isn't numerically stable; there are better interpolation methods for large datasets. It's more of a mathematical curiosity.

Not sure why you would use FFTs to evaluate Lagrange interpolators, when Lagrange interpolators have a very pretty O(N) implementation.

Example please?

:-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization.

https://news.ycombinator.com/edit?id=34720462

There are n terms with n products so O(n^2).

The FFT is not used for that. For multiplying two polynomials C(x) = A(x) B(x) then FFT is used to evaluate the polynomials (evaluated at complex roots of unity) to FIND the Lagrange interpolating polynomials for A(x), and B(x) in O(nlogn) time. Then the Lagrange interpolation is evaluated in O(n) time compute the y values for y= A(x)B(x), then FFT is used again to compute the coefficients of the final C(x). This is discussed on pages 825-827 of CLRS and the diagram on page 828 shows this in a nice diagram (the pointwise multiplication refers to evaluating the Lagrange interpolating polynomials).

FFT is almost never not worth it. Even at small scales, you should be using the FFT (and you are a daily user in audio/video/image contexts).

We have very different experiences then. "Small" scale to me is n < 64, which is right on the threshold of whether it's faster to run an n^2 algorithm that could be nlogn with an FFT (for 1-dimensional vectors) - depending on the algorithm, implementation, and hardware of course.

I've benchmarked FFT/non-FFT based approaches for almost everything in that scale for the last ten years and gotten quite different results.

An interesting case is two-dimensional interpolation. For example, for precise image resampling. In that case, due to the separability, the FFT is still O(nlog(n)), thus just as fast and much more precise than space-domain computations with 2D splines. Try to rotate 10 degrees iteratively an image 36 times with splines and with fft-based methods. Even 7 tap splines (which is a huge order) will utterly destroy the image contents; but it is just peanuts to the fft.

Reply on news.ycombinator.com