Estimating the number of solutions

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:

This gives a break condition for the number Buchberger algorithm. It becomes clear at a certain point of the computations, that no more than $ n$ solutions exist. However, if there are more than $ n$ 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-01-21