Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Luca De Feo]

> The algorithm in question is described in “Ideals, Varieties, and
> Algorithms” by David Cox, John Little and Donal O’Shea in Section "§3 A
> Division Algorithm in k[x_1 , … , x_n]".

It is not:

sage: A. = PolynomialRing(QQ, order="lex")
sage: (x*y^2 + 1).reduce([x*y + 1, y+1])
x + 1
sage: (x*y^2 + 1).reduce([y+1, x*y + 1])
x + 1

whereas Example 1 in §3 gives remainder 2;

sage: A. = PolynomialRing(QQ, order="lex")
sage: (x^2*y + x*y^2 + y^2).reduce([x*y - 1, y^2 - 1])
2*x + 1
sage: (x^2*y + x*y^2 + y^2).reduce([y^2 - 1, x*y - 1])
2*x + 1

whereas Example 2 gives remainder x + y + 1.


> My understanding is it does the (naïve?) reduction algorithm:
>
> reducing = True
> while reducing:
> reducing = False
> for expr in I:
> if expr.leading_monomial().divides(cur.leading_monomial()):
> cur -= cur.leading_term() / expr.leading_term() * expr
> reducing = True

It does not:

sage: def travis_red(f, I):
: cur = f
: reducing = True
: while reducing:
: reducing = False
: for expr in I:
: if expr.lm().divides(cur.lm()):
: cur -= cur.lt() // expr.lt() * expr
: reducing = True
: return cur
:
sage: travis_red(x^2*y + x*y^2 + y^2, [y^2 - 1, x*y - 1])
2*x + y^2


> Singular itself does this (see pp. 51-52 of "A Singular Introduction
> to Commutative Algebra") and the text even speaks of a non-unique "NF
> [normal form] w.r.t. a non-standard basis", illustrating how the
> results are different when the basis is not standard (aka Gröbner)
> and how there is a unique canonical result when the basis is
> standard.

Singular seems to have changed algorithm since. The example 1.6.13
you're referring to computes slightly different:

sage: A. = PolynomialRing(QQ, order="degrevlex")
sage: f = x^2*y*z + x*y^2*z + y^2*z + z^3 + x*y
sage: f1 = x*y + y^2 - 1
sage: f2 = x*y
sage: f.reduce([f1, f2]) # same as in the example
y^2*z + z^3
sage: f.reduce([f2, f1]) # missing a xz monomial
y^2*z + z^3 - y^2 + 1


Luca

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[john_perry_usm]

Perhaps it would be clearer if the wording were changed to, "return a 
remainder," because there can be more than one, and strike the words 
between and including "the normal form" and "i.e.", because in many places 
"normal form" implies uniqueness. For instance, speaking of Cox, Little, 
and O'Shea, at least their second edition mentions that normal forms are 
unique (p. 80 and p. 85, Exercises 1 and 4). But not all texts take this 
route (see below).

Otherwise, I agree that the function should work with lists of polynomials 
that are not Gröbner bases; there are valuable reasons for it. For 
instance, when teaching commutative algebra one can illustrate easily that 
the remainder is not unique by using a basis is not Gröbner.

Singular itself does this (see pp. 51-52 of "A Singular Introduction to 
Commutative Algebra") and the text even speaks of a non-unique "NF [normal 
form] w.r.t. a non-standard basis", illustrating how the results are 
different when the basis is not standard (aka Gröbner) and how there is a 
unique canonical result when the basis is standard. So in fact on p. 44, 
"After weakening the requirements, there is no more uniqueness statement 
for the normal form" and on p. 46 the definition of normal form is applied 
to a list of polynomials, not to an ideal, basis of an ideal, or even 
standard (Gröbner) basis.

On Monday, October 16, 2017 at 12:35:11 PM UTC-5, Martin Albrecht wrote:
>
> Hi there, 
>
> this is already documented: 
>
> “ Return the normal form of self w.r.t. "I", i.e. return the 
>remainder of this polynomial with respect to the polynomials in 
>"I". If the polynomial set/list "I" is not a (strong) Groebner 
>basis the result is not canonical. 
> ” 
>
> Cheers, 
> Martin 
>
> Daniel Krenn  writes: 
> > On 2017-10-16 18:41, Luca De Feo wrote: 
> >> Here's a Sage session: 
> >> 
> >> sage: A. = QQ[] 
> >> sage: (x+y).reduce([(x-y), (x+y)]) 
> >> 0 
> >> sage: (x-y).reduce([(x-y), (x+y)]) 
> >> -2*y 
> >> 
> >> The docstring says reduce computes "the normal form of self 
> >> w.r.t. I, 
> >> i.e. [...] the remainder of this polynomial with respect to the 
> >> polynomials in I". 
> >> 
> >> Does anyone have any idea how this normal form is defined? It 
> >> doesn't 
> >> seem to depend on the order of the polynomials in I. 
> > 
> > It computes the polynomial "modulo" the given ideal (i.e. 
> > compute a 
> > Groebner basis of the ideal and reduce the given polynomial by 
> > this basis). 
> > 
> > My guess: If only a list of polynomials is given, then it is 
> > assumed 
> > that these form a Groebner basis, which seems not to be the 
> > case. 
> > 
> >>>From the source code, I can only tell it calls Singular's kNF, 
> >>>but I 
> >> can't find any doc for it. Maybe this function should be 
> >> underscored? 
> > 
> > Once we know what it does with lists, the documentation should 
> > be made 
> > precise. 
> > 
> > I am against underscoring, as for ideals as parameter, this is a 
> > standard operation. 
>
>
> -- 
>
> _pgp: https://keybase.io/martinralbrecht 
> _www: https://martinralbrecht.wordpress.com 
> _jab: martinr...@jabber.ccc.de  
> _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF 
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Travis Scrimshaw]

On Tuesday, October 17, 2017 at 4:50:20 AM UTC-5, Luca De Feo wrote:
>
> > It takes I as the generators of the ideal and uses that as the reduction 
> > set. 
>
> That's not a definition. I'm in front of a class asking what this 
> function does, and I'm unable to give a mathematical definition of 
> what Sage means by "reduction" modulo something that's not a Groebner 
> basis. 
>
> My understanding is it does the (naïve?) reduction algorithm:

reducing = True
while reducing:
reducing = False
for expr in I:
if expr.leading_monomial().divides(cur.leading_monomial()):
cur -= cur.leading_term() / expr.leading_term() * expr
reducing = True

So this is well-defined, but it doesn't guarantee a unique result: it 
depends on the ordering of I.

I agree with Martin, that this could have unintended consequences with 
doing things in quotient rings because IIRC this is the key function that 
is called for every operation. So having something that checks that the 
input is a GB could slow things down. IMO, it also makes sense to expose 
this to users.

Best,
Travis

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

['Martin R. Albrecht' via sage-devel]

Hi there,

I’m fairly certain that I wrote that code or was at least involved 
since I wrote most of the first version of the libsingular stuff, 
David’s commit output by `git blame` is a merge commit.


The algorithm in question is described in “Ideals, Varieties, and 
Algorithms” by David Cox, John Little and Donal O’Shea in Section 
"§3 A Division Algorithm in k[x_1 , … , x_n]".


I didn’t check, though, if under the hood Singular does some 
additional tricks which might modify the output when I is not a 
GB.


Cheers,
Martin

PS: Checking if something is a GB calls reduce to check. See 
`basis_is_groebner`.


Luca De Feo  writes:

+1 for doing something.

What about the following fix: When the input is a list/tuple, 
we check
if it is a Groebner basis or not. If it is, do the computation, 
if not,

print a warning or raise an error.


Sounds reasonable.

Other options would be:

- Just refuse list input.
- Always compute a Groebner basis.

Since it seems that David Roe wrote the original code, his 
opinion

would be very valuable.

Luca



--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinralbre...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

['Martin R. Albrecht' via sage-devel]

Hi there,

AFAIK if you do that you prevent high-level implementation of 
Gröbner basis algorithms in Sage which call reduce, 
i.e. polynomial division with remainders, on S-polynomials wrt to 
the current basis.


Cheers,
Martin

Daniel Krenn  writes:

On 2017-10-17 11:49, Luca De Feo wrote:
It takes I as the generators of the ideal and uses that as the 
reduction

set.


That's not a definition. I'm in front of a class asking what 
this
function does, and I'm unable to give a mathematical definition 
of
what Sage means by "reduction" modulo something that's not a 
Groebner

basis.

What it does is probably do the reduction using the list in 
reverse order

for this case.


"Probably" is not a mathematical definition. Besides, I think 
it's

more complicated than that.

Am I the only one who's regularly embarassed explaining Sage's 
quirks

to an audience of beginners (or not beginners)?


+1 for doing something.

What about the following fix: When the input is a list/tuple, we 
check
if it is a Groebner basis or not. If it is, do the computation, 
if not,

print a warning or raise an error.

Testing if something is a Groebner basis could be done by 
converting the

list to an object of

and use its method .is_groebner()

Daniel



--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinralbre...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Luca De Feo]

> +1 for doing something.
>
> What about the following fix: When the input is a list/tuple, we check
> if it is a Groebner basis or not. If it is, do the computation, if not,
> print a warning or raise an error.

Sounds reasonable.

Other options would be:

- Just refuse list input.
- Always compute a Groebner basis.

Since it seems that David Roe wrote the original code, his opinion
would be very valuable.

Luca

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Daniel Krenn]

On 2017-10-17 11:49, Luca De Feo wrote:
>> It takes I as the generators of the ideal and uses that as the reduction
>> set.
> 
> That's not a definition. I'm in front of a class asking what this
> function does, and I'm unable to give a mathematical definition of
> what Sage means by "reduction" modulo something that's not a Groebner
> basis.
> 
>> What it does is probably do the reduction using the list in reverse order
>> for this case.
> 
> "Probably" is not a mathematical definition. Besides, I think it's
> more complicated than that.
> 
> Am I the only one who's regularly embarassed explaining Sage's quirks
> to an audience of beginners (or not beginners)?

+1 for doing something.

What about the following fix: When the input is a list/tuple, we check
if it is a Groebner basis or not. If it is, do the computation, if not,
print a warning or raise an error.

Testing if something is a Groebner basis could be done by converting the
list to an object of

and use its method .is_groebner()

Daniel

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Luca De Feo]

> It takes I as the generators of the ideal and uses that as the reduction
> set.

That's not a definition. I'm in front of a class asking what this
function does, and I'm unable to give a mathematical definition of
what Sage means by "reduction" modulo something that's not a Groebner
basis.

> What it does is probably do the reduction using the list in reverse order
> for this case.

"Probably" is not a mathematical definition. Besides, I think it's
more complicated than that.

Am I the only one who's regularly embarassed explaining Sage's quirks
to an audience of beginners (or not beginners)?

Luca

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Travis Scrimshaw]

> Can you tell from this documentation what the function will compute 
> prior to running it? I can't. 
>

It takes I as the generators of the ideal and uses that as the reduction 
set.

>
> I agree with Daniel: this function does something useful and sensible 
> when I is an ideal, so it shouldn't be underscored. 
>
> But I have no idea of what it does when I is a list, except give an 
> undefined result congruent to self modulo the ideal generated by I. So 
> I again agree with Daniel: if we can figure out what this function 
> does, we should document it better. And I would go as far as adding 
> that if we can't figure it out, we should forbid list input. 
>
> What it does is probably do the reduction using the list in reverse order 
for this case. As previously mentioned, because it is not a Gröbner basis, 
there is no guarantee of a canonical result. So IMO it does what the 
documentation says it does.

Best,
Travis

 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Luca De Feo]

On Mon, Oct 16, 2017 at 7:35 PM, 'Martin R. Albrecht' via sage-devel
 wrote:
> Hi there,
>
> this is already documented:
>
> “ Return the normal form of self w.r.t. "I", i.e. return the
>   remainder of this polynomial with respect to the polynomials in
>   "I". If the polynomial set/list "I" is not a (strong) Groebner
>   basis the result is not canonical.
> ”

Can you tell from this documentation what the function will compute
prior to running it? I can't.

I agree with Daniel: this function does something useful and sensible
when I is an ideal, so it shouldn't be underscored.

But I have no idea of what it does when I is a list, except give an
undefined result congruent to self modulo the ideal generated by I. So
I again agree with Daniel: if we can figure out what this function
does, we should document it better. And I would go as far as adding
that if we can't figure it out, we should forbid list input.

Luca

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

['Martin R. Albrecht' via sage-devel]

Hi there,

this is already documented:

“ Return the normal form of self w.r.t. "I", i.e. return the
  remainder of this polynomial with respect to the polynomials in
  "I". If the polynomial set/list "I" is not a (strong) Groebner
  basis the result is not canonical.
”

Cheers,
Martin

Daniel Krenn  writes:

On 2017-10-16 18:41, Luca De Feo wrote:

Here's a Sage session:

sage: A. = QQ[]
sage: (x+y).reduce([(x-y), (x+y)])
0
sage: (x-y).reduce([(x-y), (x+y)])
-2*y

The docstring says reduce computes "the normal form of self 
w.r.t. I,

i.e. [...] the remainder of this polynomial with respect to the
polynomials in I".

Does anyone have any idea how this normal form is defined? It 
doesn't

seem to depend on the order of the polynomials in I.


It computes the polynomial "modulo" the given ideal (i.e. 
compute a
Groebner basis of the ideal and reduce the given polynomial by 
this basis).


My guess: If only a list of polynomials is given, then it is 
assumed
that these form a Groebner basis, which seems not to be the 
case.


From the source code, I can only tell it calls Singular's kNF, 
but I
can't find any doc for it. Maybe this function should be 
underscored?


Once we know what it does with lists, the documentation should 
be made

precise.

I am against underscoring, as for ideals as parameter, this is a
standard operation.



--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinralbre...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] What does MPolynomial_libsingular.reduce() do?

[Daniel Krenn]

On 2017-10-16 18:41, Luca De Feo wrote:
> Here's a Sage session:
> 
> sage: A. = QQ[]
> sage: (x+y).reduce([(x-y), (x+y)])
> 0
> sage: (x-y).reduce([(x-y), (x+y)])
> -2*y
> 
> The docstring says reduce computes "the normal form of self w.r.t. I,
> i.e. [...] the remainder of this polynomial with respect to the
> polynomials in I".
> 
> Does anyone have any idea how this normal form is defined? It doesn't
> seem to depend on the order of the polynomials in I.

It computes the polynomial "modulo" the given ideal (i.e. compute a
Groebner basis of the ideal and reduce the given polynomial by this basis).

My guess: If only a list of polynomials is given, then it is assumed
that these form a Groebner basis, which seems not to be the case.

>>From the source code, I can only tell it calls Singular's kNF, but I
> can't find any doc for it. Maybe this function should be underscored?

Once we know what it does with lists, the documentation should be made
precise.

I am against underscoring, as for ideals as parameter, this is a
standard operation.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] What does MPolynomial_libsingular.reduce() do?

[Luca De Feo]

Hi everyone,

Here's a Sage session:

sage: A. = QQ[]
sage: (x+y).reduce([(x-y), (x+y)])
0
sage: (x-y).reduce([(x-y), (x+y)])
-2*y

The docstring says reduce computes "the normal form of self w.r.t. I,
i.e. [...] the remainder of this polynomial with respect to the
polynomials in I".

Does anyone have any idea how this normal form is defined? It doesn't
seem to depend on the order of the polynomials in I.

>From the source code, I can only tell it calls Singular's kNF, but I
can't find any doc for it. Maybe this function should be underscored?

Cheers,
Luca

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.