#6473: ideal.interreduced_basis hangs forever
---------------------+------------------------------------------------------
Reporter: broune | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone: sage-4.1
Component: algebra | Keywords:
Reviewer: | Author:
Merged: |
---------------------+------------------------------------------------------
This completes in a fraction of a second:
{{{
sage: R.<a,b,c,d>=PolynomialRing(QQ,order="lex")
sage: ideal(a^16,a-b^16,b-c^16,c-d^15).interreduced_basis()
[d^61440, c - d^15, b - d^240, a - d^3840]
}}}
I stopped the following after more than an hour, which leads me to believe
that Sage is stuck in an infinite loop:
{{{
sage: R.<a,b,c,d>=PolynomialRing(QQ,order="lex")
sage: ideal(a^16,a-b^16,b-c^16,c-d^16).interreduced_basis()
}}}
The only difference between the two is that the power of d in the input
binomial involving c as the initial term is increased from 15 to 16. This
difference has no mathematical significance and should have no impact on
the computation time.
I suspect that the reason is that by default Sage uses Singular to
implement interreduced_basis, and Singular has limitations on the size of
exponents. See http://www.singular.uni-
kl.de/Manual/latest/sing_343.htm#SEC384 which in particular says
{{{
the maximal allowed exponent of a ring variable depends on the ordering of
the ring and is at least 32767.
}}}
In this case increasing the exponent from 15 to 16 makes the output have
an exponent of 16^4^=2^16^=65536, while leaving it at 15 puts it just a
bit below that, allowing to contain it within a 16 bit integer.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6473>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
