6 ms·

Related: Fast Fourier Transform (FFT) can be used for polynomial interpolation in O(nlogn) time (if you get to choose the points, and use “complex roots of unit

Related: Fast Fourier Transform (FFT) can be used for polynomial interpolation in O(nlogn) time (if you get to choose the points, and use “complex roots of unity”), where n is the degree of the polynomial, and is used as a step in multiplication of polynomials in O(nlogn) as well. This video covers it well: https://youtu.be/h7apO7q16V0 https://youtu.be/h7apO7q16V0 Also, chapter 30 of CLRS: https://elec3004.uqcloud.net/ebooks/CLRS%20(2nd%20Ed)%20-%20Chapter%2030.FFT.pdf https://elec3004.uqcloud.net/ebooks/CLRS%20(2nd%20Ed)%20-%20...

duped 4y ago
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
- ninepoints 4y ago
  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).
  - duped 4y ago
    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.
    - enriquto 4y ago
      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.
      - deleted 4y ago
        [deleted]
- steppi 4y ago
  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.
  - rerdavies 4y ago
    Not sure why you would use FFTs to evaluate Lagrange interpolators, when Lagrange interpolators have a very pretty O(N) implementation.
    - steppi 4y ago
      Example please?
      - rerdavies 4y ago
        :-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization. https://news.ycombinator.com/edit?id=34720462 https://news.ycombinator.com/edit?id=34720462
    - mjcohen 4y ago
      There are n terms with n products so O(n^2).
    - foooobaba 4y ago
      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).
- photon12 4y ago
  Zero-knowledge proof generation, for one. Edit, see for example: https://www.zprize.io/prizes/accelerating-ntt-operations-on-an-fpga https://www.zprize.io/prizes/accelerating-ntt-operations-on-...
  - steppi 4y ago
    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.
selimthegrim 4y ago
Just as a side note this is chapter 32 in CLR for those of you not with the times.
rerdavies 4y ago
The most efficient implementation of Lagrange Interpolators is O(N). Calculate the left Product(0..i-1) of each term in left-to-right order, and the Product(i+1..N-1) of each term in right-to-left order. Your mileage may vary on a GPU.
- steppi 4y ago
  I think you're talking about evaluating the interpolating polynomial at a single value, but others are talking about getting all of the coefficients of the interpolating polynomial.
  - pkhuong 4y ago
    GP is referring to https://en.wikipedia.org/wiki/Lagrange_polynomial https://en.wikipedia.org/wiki/Lagrange_polynomial Build a table left[j] of product-of-ratios for i < j, and another right[k] for i > k, each in linear-time, and combine the two to find the product-of-ratio for i != m in linear time as well.
    - steppi 4y ago
      Right, and if we are trying to get all coefficients and are thus performing the polynomial multiplications symbolically, then performing the multiplications naively will take O(n^2) time but using FFT allows it to be done in O(n log n) time.
- credit_guy 4y ago
  I'm not aware of any algorithm for Lagrange interpolation that is O(N), and wikipedia does not know one either. What do you mean by left product and right product?
- rerdavies 4y ago
  :-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization. https://news.ycombinator.com/edit?id=34720462 https://news.ycombinator.com/edit?id=34720462
yesenadam 4y ago
"CLRS" apparently refers to https://en.wikipedia.org/wiki/Introduction_to_Algorithms https://en.wikipedia.org/wiki/Introduction_to_Algorithms And CLR (in a sibling comment) refers to the 1990 first edition.

duped 4y ago

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

ninepoints 4y ago
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).
- duped 4y ago
  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.
  - enriquto 4y ago
    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.
    - deleted 4y ago
      [deleted]
steppi 4y ago
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.
- rerdavies 4y ago
  Not sure why you would use FFTs to evaluate Lagrange interpolators, when Lagrange interpolators have a very pretty O(N) implementation.
  - steppi 4y ago
    Example please?
    - rerdavies 4y ago
      :-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization. https://news.ycombinator.com/edit?id=34720462 https://news.ycombinator.com/edit?id=34720462
  - mjcohen 4y ago
    There are n terms with n products so O(n^2).
  - foooobaba 4y ago
    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).
photon12 4y ago
Zero-knowledge proof generation, for one. Edit, see for example: https://www.zprize.io/prizes/accelerating-ntt-operations-on-an-fpga https://www.zprize.io/prizes/accelerating-ntt-operations-on-...
- steppi 4y ago
  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.

selimthegrim 4y ago

Just as a side note this is chapter 32 in CLR for those of you not with the times.

rerdavies 4y ago

The most efficient implementation of Lagrange Interpolators is O(N). Calculate the left Product(0..i-1) of each term in left-to-right order, and the Product(i+1..N-1) of each term in right-to-left order. Your mileage may vary on a GPU.

steppi 4y ago
I think you're talking about evaluating the interpolating polynomial at a single value, but others are talking about getting all of the coefficients of the interpolating polynomial.
- pkhuong 4y ago
  GP is referring to https://en.wikipedia.org/wiki/Lagrange_polynomial https://en.wikipedia.org/wiki/Lagrange_polynomial Build a table left[j] of product-of-ratios for i < j, and another right[k] for i > k, each in linear-time, and combine the two to find the product-of-ratio for i != m in linear time as well.
  - steppi 4y ago
    Right, and if we are trying to get all coefficients and are thus performing the polynomial multiplications symbolically, then performing the multiplications naively will take O(n^2) time but using FFT allows it to be done in O(n log n) time.
credit_guy 4y ago
I'm not aware of any algorithm for Lagrange interpolation that is O(N), and wikipedia does not know one either. What do you mean by left product and right product?
rerdavies 4y ago
:-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization. https://news.ycombinator.com/edit?id=34720462 https://news.ycombinator.com/edit?id=34720462

yesenadam 4y ago

"CLRS" apparently refers to https://en.wikipedia.org/wiki/Introduction_to_Algorithms https://en.wikipedia.org/wiki/Introduction_to_Algorithms And CLR (in a sibling comment) refers to the 1990 first edition.