MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Fast multiplication of polynomials mod p

  • To: mathgroup at smc.vnet.net
  • Subject: [mg51028] Re: [mg50985] Fast multiplication of polynomials mod p
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Sat, 2 Oct 2004 03:17:56 -0400 (EDT)
  • References: <200410010847.EAA11443@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On 1 Oct 2004, at 17:47, 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.
>
You have not told us if you are using the opion Modulus->p in 
PolynomialMod and other polynomial related functions.
If you are and it is still slow I doubt that there is very much that 
can be done.

Andrzej Kozlowski
Chiba, Japan
http://www.akikoz.net/~andrzej/
http://www.mimuw.edu.pl/~akoz/


  • Prev by Date: Re: Re: Re: Re: Courier New Button, selecting cells without brackets
  • Next by Date: Re: Forcing functions
  • Previous by thread: Fast multiplication of polynomials mod p
  • Next by thread: Re: Fast multiplication of polynomials mod p