ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 23 Jun 2021 19:51:20 +0200Verbose option for interreduced_basis() function?https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/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!Tue, 22 Jun 2021 22:36:28 +0200https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/Answer by rburing for <p>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? </p>
<p>Any help is much appreciated, thank you!</p>
https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?answer=57704#post-id-57704It 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]Wed, 23 Jun 2021 17:57:10 +0200https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?answer=57704#post-id-57704Comment by rburing for <p>It seems like there is no such option. However we can program it ourselves:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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]
</code></pre>
https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?comment=57710#post-id-57710You'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 :)Wed, 23 Jun 2021 19:51:20 +0200https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?comment=57710#post-id-57710Comment by jimmyjo6867 for <p>It seems like there is no such option. However we can program it ourselves:</p>
<pre><code>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
</code></pre>
<p>Example:</p>
<pre><code>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]
</code></pre>
https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?comment=57705#post-id-57705This is amazing! Thank you so much.Wed, 23 Jun 2021 18:45:36 +0200https://ask.sagemath.org/question/57686/verbose-option-for-interreduced_basis-function/?comment=57705#post-id-57705