Choice of Modulo Polynomials

[JoWayne]

Great paper Andrew!!

Out of curiosity , how do you come up w/ the choice of modulo polynomials? Trial & error to figure out polynomial which'd give the minimal muls?
For cyclic convolutions, it's pretty simple(cyclotomic poly.) but I've always been intrigued by how one comes up w/ ones for acyclic conv. ( I did read Nussbaumer/HK Garg/Tolimieri/Blahut etc, but haven't been able to figure out a standard method yet).

Thanks!

[andravin]

The main concern is numeric accuracy, for this simple rational numbers seem to work best. Any selection of unique roots will give the minimal number of real multiplications.

…

On Tue, Nov 28, 2017 at 9:30 AM JoWayne ***@***.***> wrote: Great paper Andrew!! Out of curiosity , how do you come up w/ the choice of modulo polynomials? Trial & error to figure out polynomial which'd give the minimal muls? For cyclic convolutions, it's pretty simple(cyclotomic poly.) but I've always been intrigued by how one comes up w/ ones for acyclic conv. ( I did read Nussbaumer/HK Garg/Tolimieri/Blahut etc, but haven't been able to figure out a standard method yet). Thanks! — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#10>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AIEY5U6X1Qo2Dw0sLQ6Q8ooMKhFQ6qwDks5s7EM0gaJpZM4Qtnfs> .

[JoWayne]

Thanks for clarifying this!

[buttercutter]

@andravin

Why Fast Algorithms for Convolutional Neural Networks does not make use of modulo polynomial used in wincnn github ?

[andravin]

Hi @ProMach , I wrote the "Fast algorithms ..." paper before I wrote winCNN.

The paper uses a more general technique that can compute a much larger family of fast convolution algorithms. But this was overkill, because the subset of fast algorithms that use the minimum number of multiplications can just be computed with lagrange polynomial interpolation, which is the technique used by winCNN.

I have resisted writing a complete tutorial on fast convolution algorithms, because it is a rather involved subject that has been covered very well by a few different text books. I personally found "Fast Algorithms for Signal Processing" by Richard Blahut to be the best of them. But the "Digital Signal Processing Handbook" also covers the topic well. Really you should try to get access to such a text if you want to master this subject.