Hi Luca, On 2017-10-18, Luca De Feo <de...@lix.polytechnique.fr> wrote: > However, what's the use of such a function with > implementation-dependent outputs? > > If I understand Martin's argument correctly, he is saying that > .reduce() *could* be used for a schoolbook "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." > > However for .reduce() to be useful for such applications, we would > need to have at least *some* documented guarantee on its output.
Why? The result of the schoolbook implementation of Buchberger's algorithm will result in *a* Gröbner basis, regardless of the concrete choice of execution order in the implementation of polynomial reduction; and if a reduced Gröbner basis is computed, it is *unique*. >> But at least it is clear that the .reduce() method does polynomial >> reductions and continues till no further reduction is possible; > > I agree with your analysis, but "no reduction is possible" is > ambiguous: different textbooks mean different things by it (some mean > Travis' algorithm, some others agree with Cox, Little and O'Shea). > > I would formulate it more precisely as "no monomial in the output is > divisible by the leading monomial of any polynomial in I". This seems > to be true given the examples I have, it would be good to have a > confirmation (hidden somewhere in Singular's docs?) Well, reducing the leading term is enough to get a Gröbner basis, but you need tail reductions to compute the reduced Gröbner basis. And Singular provides both options; I am sure Sage can use that, too. Best regards, Simon -- 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.
