In this section, it is presented, how to use the building blocks for Buchberger algorithms for other tasks like estimating the number of solutions.
First, we observe the following:
- By implicit use of the field equations, the number of solutions is always finite.
- We consider finitely many monomials (as we have a degree bound of one per variable).
- The number of standard monomials (monomials not present in the leading ideal) is equal to the number of solutions.
- The leading ideal (w.r.t. to the increasing set of generators) growths monotonely in each step.
This gives a break condition for the number Buchberger algorithm. It becomes
clear at a certain point of the computations, that no more than
solutions exist.
However, if there are more than
solutions, the full Gröbner basis is computed by this presented algorithm.
def less_than_n_solutions(ideal,n):
l=interred(ideal)
g=GroebnerStrategy()
all_monomials=Monomial([Variable(i) for i in xrange(number_of_variables())]).divisors()
monomials_not_in_leading_ideal=all_monomials
for p in l:
g.addGenerator(p)
while g.npairs()>0:
monomials_not_in_leading_ideal=monomials_not_in_leading_ideal%g.minimalLeadingTerms
if len(monomials_not_in_leading_ideal)<n:
return True
g.cleanTopByChainCriterion()
p=g.nextSpoly()
p=g.nf(p)
if not p.isZero():
g.addGenerator(p)
monomials_not_in_leading_ideal=monomials_not_in_leading_ideal%g.minimalLeadingTerms
if len(monomials_not_in_leading_ideal)<n:
return True
else:
return False
2010-09-29