[Date Index]
[Thread Index]
[Author Index]
Re: Fast multiplication of polynomials mod p
*To*: mathgroup at smc.vnet.net
*Subject*: [mg51036] Re: [mg50985] Fast multiplication of polynomials mod p
*From*: Daniel Lichtblau <danl at wolfram.com>
*Date*: Sat, 2 Oct 2004 03:18:17 -0400 (EDT)
*References*: <200410010847.EAA11443@smc.vnet.net>
*Sender*: owner-wri-mathgroup at wolfram.com
Trav wrote:
> I'm running a huge job on Mathematica, and the bulk of the running
> time is used on computing products of polynomials mod prime p (the
> program has to handle hundreds of polynomials of degrees up to
> hundreds, maybe even a 1000, mod p). The generic PolynomialMod
> function is slow (at O(d^2), d being the degree). Is there any add-on
> to speed up this process? I do know there's a 'FiniteFields' package,
> but any other recommendations?
>
> [ I just realized that I need to perform Gaussian elimination mod p as
> well. And the matrix is not sparse. Is there a good Mathematica
> library for that? ]
>
> Thanks in advance.
There is fast dedicated technology built into the Algebra` context for
manipulating dense univariate polynomials, represented by coefficient
lists, modulo p. Here are the functions (they all are named
Polynomial...List).
In[2]:= ??Algebra`Polynomial*List
Algebra`PolynomialDerivativeModList Algebra`PolynomialPlusModList
Algebra`PolynomialDivisionModList Algebra`PolynomialPowerModList
Algebra`PolynomialExtendedGCDModList Algebra`PolynomialPthRootModList
Algebra`PolynomialFactorModList Algebra`PolynomialQuotientModList
Algebra`PolynomialGCDModList Algebra`PolynomialRemainderModList
Algebra`PolynomialMakeMonicModList Algebra`PolynomialSubtractModList
Algebra`PolynomialMinusModList Algebra`PolynomialTimesModList
The one you want is PolynomialTimesModList. To get an idea of speed I'll
show a brief demo. We start with code to generate random polynomials
modulo some given p (which actually need not be prime). We'll multiply a
pair of degree over 1000.
randomPoly[deg_, mod_, x_] :=
Table[Random[Integer,mod-1],{deg+1}] . x^Range[0,deg]
deg = 1200;
SeedRandom[1234];
p = Prime[1234];
poly1 = randomPoly[deg, p, x];
poly2 = randomPoly[deg, p, x];
Now let's see what PolynomialMod does.
In[9]:= Timing[prod1 = PolynomialMod[poly1*poly2,p];]
Out[9]= {5.61 Second, Null}
We can convert to lists, multiply, and convert back quite a bit faster.
In[10]:= Timing[
listpoly1 = CoefficientList[poly1,x];
listpoly2 = CoefficientList[poly2,x];
prod2list = Algebra`PolynomialTimesModList[listpoly1,listpoly2,p];
prod2 = prod2list . x^Range[0,Length[prod2list]-1];
]
Out[10]= {0.03 Second, Null}
We check the results for consistency.
In[11]:= prod1===prod2
Out[11]= True
Generally speaking you would want to do as much as possible of the
computation using the list representation, and only convert from/to
explicit polynomials, if at all, at the beginning and end of the process.
Gaussian elimination with integer matrices modulo p can be done via
RowReduce[matrix, Modulus->p]
Daniel Lichtblau
Wolfram Research
Prev by Date:
**Problem with Maximize and conditions.**
Next by Date:
**Re: Hyperbolic function identity**
Previous by thread:
**Re: Fast multiplication of polynomials mod p**
Next by thread:
**Time & space complexity for built-in-functions**
| |