Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convolutions, Fast Fourier Transform and polynomials (2022)

alvarorevuelta.com

Post reply on HN
Print view View original

31–40 of 61 posts

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#31

Post by teleforce »

programjames wrote: post #3

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients as "constant time". You may as well abstract away the entire multiplication to begin with! If you take into account numerical precision, it's closer to O(n (log n)^3) [1]. [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

It will be great if we can minimize the multiplication errors and perhaps do away with the errors altogether by utilizing quaternion based operations describes in the OP article [1],[2],[3].

[1] One-Dimensional Quaternion Discrete Fourier Transform and an Approach to Its Fast Computation:

https://www.mdpi.com/2079-9292/12/24/4974

[2] Convolution Theorems for Quaternion Fourier Transform: Properties and Applications:

https://onlinelibrary.wiley.com/doi/10.1155/2013/162769

[3] On the Matrix Form of the Quaternion Fourier Transform and Quaternion Convolution:

https://arxiv.org/abs/2307.01836

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#32

Post by sigil »

pbsd wrote: post #18
sigil wrote: post #15

Who was the first person to propose FFTs for faster polynomial multiplication? Got curious about this recently. I’m not great at citation tracing, but did make it back to this 1995 paper by David Eppstein [0] where he uses it to efficiently solve Subset Sum after an incremental update. Surely Knuth’s TAOCP had it even earlier? The fact that FFT polynomial multiplication also lets you solve Exact Subset Sum with Repet…

Pollard [1], Nicholson [2], and Schonhage-Strassen [3] seem to have come up with it independently around the same time, using different approaches. Strassen is said to have discovered the Pollard approach in 1968 but there is no (written) record of it. It should also be noted that, while it was not exactly the birth of the FFT, Cooley-Tukey's 1965 paper [4] on it was what kickstarted research on FFT and its applicati…

Thank you!

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#33

Post by cperciva »

Randor wrote: post #29
cperciva wrote: post #26

Earlier quoted context omitted.

Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/

Thanks, not often we see Knuth erratas. :)

You never see "erratas", since "errata" is already the plural (of "erratum").

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#34

Post by nickcw »

You can use this method to multiply long numbers together. The key insight you need is that polynomial multiplication is the same as normal long number multiplication without doing carrying.

So suppose you have a 1000 digit number. You then take each digit and use it as the coefficient of a 1000 element polynomial. You can then multiply these polynomials together using the fft method as described in the article. To convert the result back to a number you need to do the carries. So if an element is bigger than 10 you carry the excess to the next digit. You then take the coefficients and turn them into numbers.

That's the basic idea. There is some subtlety I've glossed over due to precision needed for the carries and to be sure that rounding the fft result to the nearest integer is correct. That is the way big number multiplication is done in GMP which is the leading Library for this sort of thing.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#35

Post by nextaccountic »

cperciva wrote: post #26
eranation wrote: post #24

Earlier quoted context omitted.

This is why I keep coming back to HN. You read an interesting article, a little proud you understand half of it, read a question that already makes you feel like the stupidest person in the room, then read a clarifying answer by someone who probably got a Knuth reward check for correcting an errata in the art of computer programming.

Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/

Did he decide to include your better bound in future editions?

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#36

Post by clearprop »

nickcw wrote: post #34

You can use this method to multiply long numbers together. The key insight you need is that polynomial multiplication is the same as normal long number multiplication without doing carrying. So suppose you have a 1000 digit number. You then take each digit and use it as the coefficient of a 1000 element polynomial. You can then multiply these polynomials together using the fft method as described in the article. To c…

Thanks for the comment. That makes sense, since as you are saying, a base10 number can be expressed as a polynomial where x=10. Eg: 983 = 9x^2 + 8x + 3 aka [9, 8, 3]. Wondering how big the number has to be to make sense, and where this is used in practice.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#37

Post by clearprop »

eranation wrote: post #23

The key ”trick” of the operation seems to be this revelation: > In other words, performing the convolution of two signals in time domain is equivalent to multiplying them in the frequency domain. Great article, as it breaks down a complex idea into much smaller steps that even my math challenged mind can somehow grasp, but did I miss a step? Or is it left as an exercise to the reader to look up? I was already stretch…

Thanks! In case it helps: * Multiplying two polynomials as taught in school is in reality a convolution. * "performing the convolution of two signals in the time domain is equivalent to multiplying them in the frequency domain" * FFT allows us to convert from time domain to frequency domain * We use FFT to convert our polynomial to frequency domain. * If we are now in the frequency domain, we just need to multiply. Faster than a convolution.

Does it clarify the missing step? Happy to update the post with what's missing.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#38

Post by cperciva »

nextaccountic wrote: post #35
cperciva wrote: post #26

Earlier quoted context omitted.

Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/

Did he decide to include your better bound in future editions?

Yes. I believe proving the strict bound is one of the exercises now.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#39

Post by Kubuxu »

clearprop wrote: post #36
nickcw wrote: post #34

You can use this method to multiply long numbers together. The key insight you need is that polynomial multiplication is the same as normal long number multiplication without doing carrying. So suppose you have a 1000 digit number. You then take each digit and use it as the coefficient of a 1000 element polynomial. You can then multiply these polynomials together using the fft method as described in the article. To c…

Thanks for the comment. That makes sense, since as you are saying, a base10 number can be expressed as a polynomial where x=10. Eg: 983 = 9x^2 + 8x + 3 aka [9, 8, 3]. Wondering how big the number has to be to make sense, and where this is used in practice.

FFT is used extensively in curve based zero-knowledge cryptography, not for the purpose of splitting a single large number into smaller ones, but to interpolate and evaluate very large polynomials (for example of the degree 2^27).

All of this happens in a field of an elliptic curve so the complexity reduction is greatly appreciated.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#40

Post by Kubuxu »

joe_the_user wrote: post #21

Sure, the naive method of multiplying polynomials is slow in the degree of the polynomial. But when does one have to deal with two degree 100 polynomials? My impression is that this sort of method isn't used by computer algebra system for this reason.

Zero-knowledge cryptography frequently deals with polynomials of degree 2^20 - 2^27.
Post reply on HN