ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 21 Jul 2011 16:33:10 -0500Univariate Polynomial Multiplicationhttp://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/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?Thu, 21 Jul 2011 11:30:28 -0500http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/Answer by niles for <p>What algorithms does sage use for univariate polynomial multiplication?</p>
<p>In particular, I am curious about the algorithm used for multiplication over finite fields and polynomials with coefficients in Z or Q.</p>
<p>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?</p>
http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12530#post-id-12530This 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:
sage: R.<t> = PolynomialRing(ZZ) # make the kind of ring I want to check
sage: f = R.random_element(); f # and an element
3*t^2 + t + 65
See what kind of objects they are:
sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain'>
sage: type(f)
<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
You can browse these source files in your local sage install at `$SAGE_ROOT/devel/sage-main/sage/rings/polynomial`, or you can [browse them online](http://hg.sagemath.org/sage-main/file/ce324e28c333/sage/rings/polynomial) (linked from the "Source Code" section of the main [Sage Development](http://www.sagemath.org/development.html) page).
Of course it helps if you know where to look; multiplication is implemented (often, including this case) by the `_mul_` method, so you can check it directly with
sage: f._mul_??
This will display the relevant part of the source code. There, you will see that this particular multiplication is implemented by `fmpz_poly_mul` -- this is a [FLINT](http://www.flintlib.org/) method, and you'd have to look at the FLINT source if you want to go further in this hunt . . .
A similar procedure will, I think, get you started with finding the implementations of the other multiplication algorithms you mentioned. Good luck!Thu, 21 Jul 2011 15:24:18 -0500http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12530#post-id-12530Comment by niles for <p>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:</p>
<pre><code>sage: R.<t> = PolynomialRing(ZZ) # make the kind of ring I want to check
sage: f = R.random_element(); f # and an element
3*t^2 + t + 65
</code></pre>
<p>See what kind of objects they are:</p>
<pre><code>sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain'>
sage: type(f)
<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
</code></pre>
<p>You can browse these source files in your local sage install at <code>$SAGE_ROOT/devel/sage-main/sage/rings/polynomial</code>, or you can <a href="http://hg.sagemath.org/sage-main/file/ce324e28c333/sage/rings/polynomial">browse them online</a> (linked from the "Source Code" section of the main <a href="http://www.sagemath.org/development.html">Sage Development</a> page).</p>
<p>Of course it helps if you know where to look; multiplication is implemented (often, including this case) by the <code>_mul_</code> method, so you can check it directly with </p>
<pre><code>sage: f._mul_??
</code></pre>
<p>This will display the relevant part of the source code. There, you will see that this particular multiplication is implemented by <code>fmpz_poly_mul</code> -- this is a <a href="http://www.flintlib.org/">FLINT</a> method, and you'd have to look at the FLINT source if you want to go further in this hunt . . .</p>
<p>A similar procedure will, I think, get you started with finding the implementations of the other multiplication algorithms you mentioned. Good luck!</p>
http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?comment=21453#post-id-21453Oh, I shouldn't have taken so long to write this answer!Thu, 21 Jul 2011 15:27:48 -0500http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?comment=21453#post-id-21453Answer by Mike Hansen for <p>What algorithms does sage use for univariate polynomial multiplication?</p>
<p>In particular, I am curious about the algorithm used for multiplication over finite fields and polynomials with coefficients in Z or Q.</p>
<p>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?</p>
http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12528#post-id-12528For integer polynomials, FLINT is used to do the multiplication. We look at the `_mul_` method since in Sage, `__mul__` is used to handle coercion and then dispatches to `_mul_`.
sage: R.<x> = ZZ[]
sage: x._mul_??
...
cpdef RingElement _mul_(self, RingElement right):
r"""
Returns self multiplied by right.
EXAMPLES::
sage: R.<x> = PolynomialRing(ZZ)
sage: (x - 2)*(x^2 - 8*x + 16)
x^3 - 10*x^2 + 32*x - 32
"""
cdef Polynomial_integer_dense_flint x = self._new()
sig_on()
fmpz_poly_mul(x.__poly, self.__poly,
(<Polynomial_integer_dense_flint>right).__poly)
sig_off()
return x
You can do a similar check to see that FLINT's `fmpq_poly_mul` is used for polynomials over the rationals.
The univariate polynomials over finite fields different based on the size of the field. For example, for small primes, FLINT is used:
sage: R.<x> = GF(next_prime(2^5))[]
sage: type(x)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
But for larger primes, NTL is used:
sage: R.<x> = GF(next_prime(2^64))[]
sage: type(x)
<type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>
To find out the exact algorithm / heuristics used, you'll need to delve into those packages.
Thu, 21 Jul 2011 14:48:18 -0500http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12528#post-id-12528Answer by mathmajor for <p>What algorithms does sage use for univariate polynomial multiplication?</p>
<p>In particular, I am curious about the algorithm used for multiplication over finite fields and polynomials with coefficients in Z or Q.</p>
<p>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?</p>
http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12531#post-id-12531Thank you for the quick help. This is exactly what I was looking for.Thu, 21 Jul 2011 16:33:10 -0500http://ask.sagemath.org/question/8241/univariate-polynomial-multiplication/?answer=12531#post-id-12531