Ask Your Question
2

Verbose option for interreduced_basis() function?

asked 2021-06-22 22:36:28 +0200

jimmyjo6867 gravatar image

updated 2021-06-23 18:45:22 +0200

I was trying to see how/which reductions were being computed for a non-reduced grobner basis. Is there anyway to see the intermediate steps/reduction steps, the interreduced_basis() makes?

Any help is much appreciated, thank you!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2021-06-23 17:57:10 +0200

rburing gravatar image

updated 2021-06-23 19:48:05 +0200

It seems like there is no such option. However we can program it ourselves:

from sage.misc.verbose import verbose

def my_reduce(f, G):
    verbose('Reducing {} with respect to {}'.format(f, G), level=1)
    p = f
    r = 0
    while not p.is_zero():
        lt = p.lt()
        candidate = next((g for g in G if g.lt().divides(lt)), None)
        if candidate is not None:
            coeff = lt // candidate.lt()
            verbose('Subtracting {} * ({})'.format(coeff, candidate), level=1)
            p -= coeff*candidate
        else:
            verbose('Term {} cannot be eliminated'.format(p.lt()), level=1)
            r += p.lt()
            p -= p.lt()
    return r

def my_reduce_groebner_basis(G):
    verbose('Reducing the Groebner basis {}'.format(G), level=1)
    i = 0
    while i < len(G):
        j = 0
        while j < len(G):
            if i != j and G[i].lt().divides(G[j].lt()):
                verbose('Removing {} since its leading term is divisible by that of {}'.format(G[j],G[i]), level=1)
                G.pop(j)
            else:
                j += 1
        i += 1
    verbose('Normalizing:', level=1)
    for i in range(len(G)):
        if G[i].lc() != 1:
            verbose('Dividing {} by {}'.format(G[i], G[i].lc()), level=1)
            G[i] = G[i] / G[i].lc()
    verbose('Reducing each element with respect to the rest:', level=1)
    for i in range(len(G)):
        G[i] = my_reduce(G[i], [G[j] for j in range(len(G)) if j != i])
    return G

Example:

sage: R.<x,y> = PolynomialRing(QQ,order='deglex')
sage: G = [y^4 + x^2*y + y^3 - x*y, x*y + y^2, x*y^2 + y^3]
sage: R.ideal(G).basis_is_groebner()
True
sage: set_verbose(1)
sage: my_reduce_groebner_basis(G)
verbose 1 (my_reduce_groebner_basis) Reducing the Groebner basis [y^4 + x^2*y + y^3 - x*y, x*y + y^2, x*y^2 + y^3]
verbose 1 (my_reduce_groebner_basis) Removing x*y^2 + y^3 since its leading term is divisible by that of x*y + y^2
verbose 1 (my_reduce_groebner_basis) Normalizing:
verbose 1 (my_reduce_groebner_basis) Reducing each element with respect to the rest:
verbose 1 (my_reduce) Reducing y^4 + x^2*y + y^3 - x*y with respect to [x*y + y^2]
verbose 1 (my_reduce) Term y^4 cannot be eliminated
verbose 1 (my_reduce) Subtracting x * (x*y + y^2)
verbose 1 (my_reduce) Subtracting -y * (x*y + y^2)
verbose 1 (my_reduce) Term 2*y^3 cannot be eliminated
verbose 1 (my_reduce) Subtracting -1 * (x*y + y^2)
verbose 1 (my_reduce) Term y^2 cannot be eliminated
verbose 1 (my_reduce) Reducing x*y + y^2 with respect to [y^4 + 2*y^3 + y^2]
verbose 1 (my_reduce) Term x*y cannot be eliminated
verbose 1 (my_reduce) Term y^2 cannot be eliminated
[y^4 + 2*y^3 + y^2, x*y + y^2]
sage: set_verbose(0)
sage: R.ideal(G).groebner_basis()
[y^4 + 2*y^3 + y^2, x*y + y^2]
edit flag offensive delete link more

Comments

This is amazing! Thank you so much.

jimmyjo6867 gravatar imagejimmyjo6867 ( 2021-06-23 18:45:36 +0200 )edit
1

You're welcome! I just changed the name of the function because it's really calculating a reduced Groebner basis. Anyway, you can get what you want from it :)

rburing gravatar imagerburing ( 2021-06-23 19:51:20 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2021-06-22 22:36:28 +0200

Seen: 63 times

Last updated: Jun 23