Thanks! With your help I found solution to my problem but it wasn't
trivial. I'll describe my
steps because they might be helpful for someone.
Finally I wrote simple function, that evaluates polynomial at a
specified point:
def poly_eval (poly, a):
coeffs = poly.coefficients()
exp = f.exponents()
value = poly.base_ring()(0)
for i in range(len(coeffs)):
value += coeffs[i] * a^(exp[i])
return value
But at first I tried to dig into sage source code (this is the
benefits of open-source projects).
I found that Sage cannot evaluate polynomials of very high degree even
for rings,
where implementation isn't broken.
At first I changed GF(p) field to IntegerModRing(p):
sage: p = next_prime(10^50)
sage: modRing = IntegerModRing(p)
sage: R.<x> = PolynomialRing(modRing,sparse=True)
And after that I successeded in constructing
sage: f = x^(10^10)
But evaluation f(2) is failing with MemoryError in
File "polynomial_element.pyx", line 570, in
sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/
rings/polynomial/polynomial_element.c:6687)
File "/usr/local/sage-4.3.5/local/lib/python2.6/site-packages/sage/
rings/polynomial/polynomial_element_generic.py", line 386, in list
v = [zero] * (self.degree()+1)
I found out that Polynomial.__call__ method evaluates data via
CompiledPolynomialFunction,
but CompiledPolynomialFunction accept polynomials only in dense form,
because it accepts f.list() and
this method tries to allocate list with 10^10 elements.
I changed f to
sage: f = x^(10^50)
And evaluation gave me another exception because of conversion
f.degree() to long in
File "polynomial_element.pyx", line 499, in
sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/
rings/polynomial/polynomial_element.c:5606)
OverflowError: long int too large to convert to int
All evaluation of generic (even sparse) polynomials is based on
precondition that f.degree() can be
fit into long data type. And changing long variables into variable-
length integers can cause slowdown in
evaluation dense polynomials. So I found out that changing existing
sage code to support sparse
polynomials isn't easy task in general. But simple solution (poly_eval
function) can be used directly
or it can be added to the polynomial_element_generic.py if polynomial
is very sparse.
PS: maybe this should be send to sage-devel.
On 25 апр, 11:19, William Stein <[email protected]> wrote:
> On Sat, Apr 24, 2010 at 10:22 PM, Robert Bradshaw
>
>
>
>
>
> <[email protected]> wrote:
> > On Apr 24, 2010, at 5:36 PM, Michael Rybalkin wrote:
>
> >> How to get monomial with large exponent in the polynomial rings?
>
> >> For example I hsave polynomial ring over large finite field:
> >> p = next_prime(10^20)
> >> R.<x> = PolynomialRing(GF(p), sparse=True)
>
> >> Monomial x^(10^7) construction takes 2 seconds:
> >> time tmp = x^(10^7)
>
> >> Monomial x^(10^8) construction uses all 6 Gb server memory and cannot
> >> finish.
> >> And without 'sparse=True' option I cannot even get x^(10^6).
>
> >> What is the limitations for monomial exponents in polynomial rings?
> >> What can be done in my case? For example GAP handles this case without
> >> any problem.
>
> > Seems like the sparse=True flag is horribly broken for GF(p)[x]:
>
> > sage: p = next_prime(10^20)
> > sage: R.<x> = PolynomialRing(GF(p), sparse=True)
> > sage: type(x)
> > <type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
>
> > sage: R.<x> = PolynomialRing(QQ, sparse=True)
> > sage: x^(10^8)
> > x^100000000
>
> > - Robert
>
> This is now
>
> http://trac.sagemath.org/sage_trac/ticket/8762
>
> William
>
>
>
> > --
> > To post to this group, send email to [email protected]
> > To unsubscribe from this group, send email to
> > [email protected]
> > For more options, visit this group at
> >http://groups.google.com/group/sage-support
> > URL:http://www.sagemath.org
>
> --
> William Stein
> Professor of Mathematics
> University of Washingtonhttp://wstein.org
>
> --
> To post to this group, send email to [email protected]
> To unsubscribe from this group, send email to
> [email protected]
> For more options, visit this group
> athttp://groups.google.com/group/sage-support
> URL:http://www.sagemath.org
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
