What algorithms does sage use for univariate polynomial multiplication?
In particular, I am curious about the algorithm used for multiplication over finite fields and polynomials with coefficients in Z or Q.
More generally, is there an easy way to look under the hood and trace down the exact functions being called in the event I have a question like this again?
asked Jul 21 '11
For integer polynomials, FLINT is used to do the multiplication. We look at the
You can do a similar check to see that FLINT's
The univariate polynomials over finite fields different based on the size of the field. For example, for small primes, FLINT is used:
But for larger primes, NTL is used:
To find out the exact algorithm / heuristics used, you'll need to delve into those packages.
posted Jul 21 '11Mike Hansen
3675 ● 19 ● 43 ● 81
This is a pretty broad question, and I'm certainly not an expert in this area, but maybe I can get you pointed in the right direction. It's easy to look under the hood, but maybe (depending on your experience) not so easy to pin down exactly what's being called. Here's how I proceeded:
See what kind of objects they are:
You can browse these source files in your local sage install at
Of course it helps if you know where to look; multiplication is implemented (often, including this case) by the
This will display the relevant part of the source code. There, you will see that this particular multiplication is implemented by
A similar procedure will, I think, get you started with finding the implementations of the other multiplication algorithms you mentioned. Good luck!
Thank you for the quick help. This is exactly what I was looking for.
posted Jul 21 '11mathmajor
1 ● 3
Asked: Jul 21 '11
Seen: 174 times
Last updated: Jul 21 '11
powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.