[steppi]

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]

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

[foooobaba]

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).

[mjcohen]

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

[steppi]

Example please?

[rerdavies]

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

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