# Changeset 7513:c52f4c723299

Ignore:
Timestamp:
11/16/07 04:41:41 (6 years ago)
Branch:
default
Message:

Rewrote hash functions for polynomial and fraction field elts to respect '=='

Location:
sage
Files:
14 edited

Unmodified
Removed
• ## sage/crypto/mq/mpolynomialsystem.py

 r7066 sage: sr = mq.SR(allow_zero_inversions=True) sage: F,s = sr.polynomial_system() sage: F.variables()[:10] [x101, x100, x103, x102, s002, w100, w101, w102, w103, k100] sage: F.variables()[:10]  # this output ordering depends on a hash and so might change if __hash__ changes [s000, k101, k100, s003, x102, x103, s002, w103, w102, x100]        # 32-bit [k101, k100, s003, x102, x103, s002, w103, w102, x100, x101]        # 64-bit """ V = set()
• ## sage/rings/finite_field_ext_pari.py

 r7155 The following is a native Python set: sage: set(k) set([0, 1, 2, 2*a + 1, a + 2, 2*a, 2*a + 2, a, a + 1]) set([0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2]) And the following is a SAGE enumerated set: sage: EnumeratedSet(k) {0, 1, 2, 2*a + 1, a + 2, 2*a, 2*a + 2, a, a + 1} We can also make a list via comprehension: {0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2} We can also make a list via comprehension: sage: [x for x in k] [0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2] -586939294780423730            # 64-bit sage: hash(GF(9,'a')) 205387690                      # 32-bit -8785304532306495574           # 64-bit -417021630                     # 32-bit 1006006598732398914            # 64-bit sage: hash(GF(9,'b')) -74532899                      # 32-bit 5852897890058287069            # 64-bit 995034271                      # 32-bit 8600900932991911071            # 64-bit """ return hash((self.__order, self.variable_name(), self.__modulus))
• ## sage/rings/finite_field_givaro.pyx

 r7155 EXAMPLES: sage: hash(GF(3^4, 'a')) 695660592                 # 32-bit -4281682415996964816      # 64-bit -417021630                # 32-bit 1006006598732398914       # 64-bit """ if self._hash is None:
• ## sage/rings/fraction_field_element.py

 r6528 def denominator(self): return self.__denominator def __hash__(self): """ This function hashes in a special way to ensure that generators of a ring R and generators of a fraction field of R have the same hash.  This enables them to be used as keys interchangably in a dictionary (since \code{==} will claim them equal). This is particularly useful for methods like subs on \code{ParentWithGens} if you are passing a dictionary of substitutions. EXAMPLES: sage: R.=ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: ((x+1)/(x^2+1)).subs({x:1}) 1 sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.=QQ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.=ZZ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.=QQ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: ((x+1)/(x^2+1)).subs({x:1}) 1 sage: d={x:1} sage: d[FractionField(R).0] 1 sage: hash(R(1)/R(2))==hash(1/2) True """ # This is same algorithm as used for members of QQ #cdef long n, d n = hash(self.__numerator) d = hash(self.__denominator) if d == 1: return n n = n ^ d if n == -1: return -2 return n def partial_fraction_decomposition(self): """
• ## sage/rings/ideal.py

 r6646 sage: i = ideal(1,t,t^2) sage: i Ideal (t, 1, t^2) of Univariate Polynomial Ring in t over Integer Ring Ideal (t^2, 1, t) of Univariate Polynomial Ring in t over Integer Ring sage: ideal(1/2,t,t^2) Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field
• ## sage/rings/polynomial/multi_polynomial.pxd

 r4451 cdef class MPolynomial(CommutativeRingElement): pass cdef long _hash_c(self)
• ## sage/rings/polynomial/multi_polynomial.pyx

 r6606 D[ETuple(tmp)] = a return D cdef long _hash_c(self): """ This hash incorporates the variable name in an effort to respect the obvious inclusions into multi-variable polynomial rings. The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. EXAMPLES: sage: T.=QQ[] sage: R.=ZZ[] sage: S.=ZZ[] sage: hash(S.0)==hash(R.0)  # respect inclusions into mpoly rings (with matching base rings) True sage: hash(S.1)==hash(T.0)  # respect inclusions into mpoly rings (with unmatched base rings) True sage: hash(S(12))==hash(12)  # respect inclusions of the integers into an mpoly ring True sage: # the point is to make for more flexible dictionary look ups sage: d={S.0:12} sage: d[R.0] 12 sage: # or, more to the point, make subs in fraction field elements work sage: f=x/y sage: f.subs({x:1}) 1/y """ cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap cdef long result_mon var_name_hash = [hash(v) for v in self._parent.variable_names()] cdef long c_hash for m,c in self.dict().iteritems(): #  I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. # This assumption is not true, but I think it is true enough for the purposes and it # it allows us to write fast code that omits terms with 0 coefficients.  This is # important if we want to maintain the '==' relationship with sparse polys. c_hash = hash(c) if c_hash != 0: # this is always going to be true, because we are sparse (correct?) # Hash (self[i], gen_a, exp_a, gen_b, exp_b, gen_c, exp_c, ...) as a tuple according to the algorithm. # I omit gen,exp pairs where the exponent is zero. result_mon = c_hash for p in m.nonzero_positions(): result_mon = (1000003 * result_mon) ^ var_name_hash[p] result_mon = (1000003 * result_mon) ^ m[p] result += result_mon if result == -1: return -2 return result # you may have to replicate this boilerplate code in derived classes if you override # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html # explains how __richcmp__, __hash__, and __cmp__ are tied together. def __hash__(self): return self._hash_c() cdef remove_from_tuple(e, int ind):
• ## sage/rings/polynomial/multi_polynomial_element.py

 r7226 else: return False def __hash__(self): #requires base field elements are hashable! return hash(tuple(self._MPolynomial_element__element.dict().items())) def lm(self):
• ## sage/rings/polynomial/multi_polynomial_ideal.py

 r7138 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching sage: I.groebner_basis('toy:buchberger') [-30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c, -2*b^2 - b*c + 1/2*b, -7/125*b - 42/25*c^3 + 79/125*c^2 - 3/125*c, a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, -5*b*c + 1/2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b] [a + 2*b + 2*c - 1, -6*b^2 - 8*b*c + 2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b, 7/250*b + 21/25*c^3 - 79/250*c^2 + 3/250*c, a^2 - a + 2*b^2 + 2*c^2, -5/3*b*c + 1/6*b - 2*c^2 + 2/3*c, -30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c] sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching sage: I.groebner_basis('toy:buchberger2') [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1, 7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2] [a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, -7/250*b - 21/25*c^3 + 79/250*c^2 - 3/250*c] sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching
• ## sage/rings/polynomial/multi_polynomial_libsingular.pyx

 r7287 else: return co.new_MP(parent, res) # you may have to replicate this boilerplate code in derived classes if you override # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html # explains how __richcmp__, __hash__, and __cmp__ are tied together. def __hash__(self): return self._hash_c() def __richcmp__(left, right, int op): return (left)._richcmp(right, op) p = pNext(p) return pd cdef long _hash_c(self): """ This hash incorporates the variable name in an effort to respect the obvious inclusions into multi-variable polynomial rings. The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. EXAMPLES: sage: R.=QQ[] sage: S.=QQ[] sage: hash(S(1/2))==hash(1/2)  # respect inclusions of the rationals True sage: hash(S.0)==hash(R.0)  # respect inclusions into mpoly rings True sage: # the point is to make for more flexible dictionary look ups sage: d={S.0:12} sage: d[R.0] 12 """ cdef poly *p cdef ring *r cdef int n cdef int v r = (self._parent)._ring if r!=currRing: rChangeCurrRing(r) base = (self._parent)._base p = self._poly cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap cdef long result_mon var_name_hash = [hash(vn) for vn in self._parent.variable_names()] cdef long c_hash while p: c_hash = hash(co.si2sa(p_GetCoeff(p, r), r, base)) if c_hash != 0: # this is always going to be true, because we are sparse (correct?) # Hash (self[i], gen_a, exp_a, gen_b, exp_b, gen_c, exp_c, ...) as a tuple according to the algorithm. # I omit gen,exp pairs where the exponent is zero. result_mon = c_hash for v from 1 <= v <= r.N: n = p_GetExp(p,v,r) if n!=0: result_mon = (1000003 * result_mon) ^ var_name_hash[v-1] result_mon = (1000003 * result_mon) ^ n result += result_mon p = pNext(p) if result == -1: return -2 return result def __iter__(self): """ cdef int is_constant_c(self): return p_IsConstant(self._poly, (self._parent)._ring) def __hash__(self): """ """ s = p_String(self._poly, (self._parent)._ring, (self._parent)._ring) return hash(s) def lm(MPolynomial_libsingular self):
• ## sage/rings/polynomial/polynomial_element.pxd

 r6677 cdef CompiledPolynomialFunction _compiled cdef truncate_c(self, long n) cdef long _hash_c(self) # UNSAFE, only call from an inplace operator
• ## sage/rings/polynomial/polynomial_element.pyx

 r7286 from sage.rings.integral_domain import is_IntegralDomain from sage.structure.parent_gens cimport ParentWithGens import polynomial_fateman def __iter__(self): return iter(self.list()) # you may have to replicate this boilerplate code in derived classes if you override # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html # explains how __richcmp__, __hash__, and __cmp__ are tied together. def __hash__(self): if self.degree() >= 1: return hash(tuple(self.list())) else: return hash(self[0]) return self._hash_c() cdef long _hash_c(self): """ This hash incorporates the variable name in an effort to respect the obvious inclusions into multi-variable polynomial rings. The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. EXAMPLES: sage: R.=ZZ[] sage: hash(R(1))==hash(1)  # respect inclusions of the integers True sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field True sage: R.=QQ[] sage: hash(R(1/2))==hash(1/2)  # respect inclusions of the rationals True sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field True sage: R.=IntegerModRing(11)[] sage: hash(R.0)==hash(FractionField(R).0)  # respect inclusions into the fraction field True """ cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap cdef long result_mon cdef long c_hash cdef long var_name_hash cdef int i for i from 0<= i <= self.degree(): if i == 1: # we delay the hashing until now to not waste it one a constant poly var_name_hash = hash((self._parent)._names[0]) #  I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. # This assumption is not true, but I think it is true enough for the purposes and it # it allows us to write fast code that omits terms with 0 coefficients.  This is # important if we want to maintain the '==' relationship with sparse polys. c_hash = hash(self[i]) if c_hash != 0: if i == 0: result += c_hash else: # Hash (self[i], generator, i) as a tuple according to the algorithm. result_mon = c_hash result_mon = (1000003 * result_mon) ^ var_name_hash result_mon = (1000003 * result_mon) ^ i result += result_mon if result == -1: return -2 return result def __float__(self): if self.degree() > 0: def __nonzero__(self): return len(self.__coeffs) > 0 def __hash__(self): if len(self.__coeffs) > 1: return hash(tuple(self.__coeffs)) elif len(self.__coeffs) == 1: return hash(self[0]) else: return 0 cdef void __normalize(self): x = self.__coeffs del x[n] n -= 1 # you may have to replicate this boilerplate code in derived classes if you override # __richcmp__.  The python documentation at  http://docs.python.org/api/type-structs.html # explains how __richcmp__, __hash__, and __cmp__ are tied together. def __hash__(self): return self._hash_c() def __richcmp__(left, right, int op): return (left)._richcmp(right, op)
• ## sage/rings/polynomial/polynomial_integer_dense_ntl.pyx

 r7284 include "../../ext/stdsage.pxi" from sage.rings.polynomial.polynomial_element cimport Polynomial (self.parent(), self.list(), False, self.is_gen()) def __getitem__(self, long n): r"""
• ## sage/rings/polynomial/toy_buchberger.py

 r6606 sage: buchberger(I) (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0 G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) (a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0 G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c]) (2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) (a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0 G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]) 15 reductions to zero. [a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c] The 'improved' Buchberger algorithm in constrast only performs 3 reductions to zero: sage: buchberger_improved(I) (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 2*b^2 + 6*b*c + 6*c^2 - b - 2*c G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => 0 G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0 G: set([a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c, 2*a*b + 2*b*c - b]) (2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => -61*c^3 + 55*c^2 + 53*b + 59*c G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a^2 + 2*b^2 + 2*c^2 - a, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a + 2*b + 2*c - 1, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (2*a*b + 2*b*c - b, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a^2 + 2*b^2 + 2*c^2 - a, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c) => 0 G: set([-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) 15 reductions to zero. [-5*b*c - 6*c^2 - 63*b + 2*c, -61*c^3 + 55*c^2 + 53*b + 59*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b] The 'improved' Buchberger algorithm in constrast only performs 3 reductions to zero: sage: buchberger_improved(I) (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => -2*b^2 - b*c - 63*b G: set([a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 5*b*c + 6*c^2 + 63*b - 2*c G: set([5*b*c + 6*c^2 + 63*b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (-2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b) => 0 G: set([5*b*c + 6*c^2 + 63*b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - b*c - 63*b, a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b]) (5*b*c + 6*c^2 + 63*b - 2*c, -2*b^2 - b*c - 63*b) => -11*c^3 + 12*c^2 - 30*b - 31*c G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) (5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b) => 0 G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) (-11*c^3 + 12*c^2 - 30*b - 31*c, 5*b*c + 6*c^2 + 63*b - 2*c) => 0 G: set([-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b]) G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a]) (2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 5*b*c + 6*c^2 + 63*b - 2*c G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c]) (5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b) => 22*c^3 - 24*c^2 + 60*b + 62*c G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) (2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 2*a*b + 2*b*c - b) => 0 G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) (5*b*c + 6*c^2 + 63*b - 2*c, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c) => 0 G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) (22*c^3 - 24*c^2 + 60*b + 62*c, 5*b*c + 6*c^2 + 63*b - 2*c) => 0 G: set([a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c]) 3 reductions to zero. [-11*c^3 + 12*c^2 - 30*b - 31*c, a^2 + 2*b^2 + 2*c^2 - a, 5*b*c + 6*c^2 + 63*b - 2*c, a + 2*b + 2*c - 1, -2*b^2 - b*c - 63*b, 2*a*b + 2*b*c - b] [a + 2*b + 2*c - 1, 2*b^2 + 6*b*c + 6*c^2 - b - 2*c, 5*b*c + 6*c^2 + 63*b - 2*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, 22*c^3 - 24*c^2 + 60*b + 62*c] AUTHOR:
Note: See TracChangeset for help on using the changeset viewer.