Convolutions, Fast Fourier Transform and polynomials (2022)

#1

Post by clearprop » Sun, Jun 30, 2024, 9:08 PM UTC

Convolutions, Fast Fourier Transform and polynomials (2022)
alvarorevuelta.com

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

#2

Post by bjornsing » Sun, Jun 30, 2024, 9:54 PM UTC

Funny feeling: Looking at the title I felt a bit puzzled. Then scrolling the article the concepts and their (well known) connections came back to me.

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

#3

Post by programjames » Sun, Jun 30, 2024, 10:09 PM UTC

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

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

#4

Post by adamnemecek » Sun, Jun 30, 2024, 10:48 PM UTC

I think that all machine learning is solving a convolutional equation.

This paper talks about it in the context of RL https://arxiv.org/abs/1712.06115 but most approaches fit within that paradigm.

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

#5

Post by e-khadem » Sun, Jun 30, 2024, 11:02 PM UTC

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

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

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

#6

Post by salty_biscuits » Sun, Jun 30, 2024, 11:04 PM UTC

adamnemecek wrote: post #4

I think that all machine learning is solving a convolutional equation. This paper talks about it in the context of RL https://arxiv.org/abs/1712.06115 but most approaches fit within that paradigm.

Basically kernel methods right?

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

#7

Post by adamnemecek » Sun, Jun 30, 2024, 11:15 PM UTC

salty_biscuits wrote: post #6

adamnemecek wrote: post #4

I think that all machine learning is solving a convolutional equation. This paper talks about it in the context of RL https://arxiv.org/abs/1712.06115 but most approaches fit within that paradigm.

Basically kernel methods right?

Yes, it is there. There might be more.

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

#8

Post by xphos » Sun, Jun 30, 2024, 11:25 PM UTC

e-khadem wrote: post #5

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

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe....

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

#9

Post by programjames » Sun, Jun 30, 2024, 11:28 PM UTC

e-khadem wrote: post #5

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

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.

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

#10

Post by programjames » Sun, Jun 30, 2024, 11:29 PM UTC

xphos wrote: post #8

e-khadem wrote: post #5

Earlier quoted context omitted.

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe... .

I prefer this reference: https://cp-algorithms.com/algebra/fft.html#number-theoretic-...