Cache groebner basis independend of degree bound

[vbraun]

One of the basic tricks when working with Groebner bases is to compute only up to a certain degree bound. Right now we support that, but then we attempt to compute the complete Groebner basis for any subsequent operation (which is often impossible due to time/memory constraints).

This patch caches the Groebner basis independent of the degree bound.

Apply trac_11667_use_groebner_basis_with_degree_bound.patch

CC: @simon-king-jena @burcin

Component: commutative algebra

Work Issues: Error prone computations may be done explicitly, but must not be the default

Author: Volker Braun

Reviewer: Simon King

Issue created by migration from https://trac.sagemath.org/ticket/11667

[vbraun]

Author: Volker Braun

[simon-king-jena]

comment:2

I don't like that approach, for two reasons.

1. You remove @cached_method. When Rewrite cached_method in Cython #11115 finally gets reviewed, cached methods will be cythoned and will be amazingly fast - faster than even a Python method that does nothing more but returning a constant. So, one shouldn't remove @cached_method unless one has a good reason.

2. As much as I know, the use of degbound means computing a truncated Gröbner basis, but that is generally not a "Gröbner basis out to a certain degree", for inhomogeneous ideals. And even in the homogeneous case, computing a normal form only works for polynomials of at most the given degbound. So, using a truncated Gröbner basis is dirty, and therefore the user must not use it accidentally.

In other words, the approach of using a truncated Gröbner basis by default is error prone, potentially yields very difficult to debug problems, and violates the "explicit is better than implicit" mantra.

If the user wants to play dirty, then s/he can already do so: One can explicitly set the return value of a cached method. Hence, if the user really wants to use a Gröbner basis out to degree 5 and pretend it to be a complete Gröbner basis, then s/he can already do so - but that must never happen accidentally!

A valid approach would be to edit the places in which Gröbner bases are actually used, e.g., in the normal form computation. There, one could explicitly request a truncated Gröbner basis out to the degree of the polynomial that is going to be normalised.

And then, the groebner_basis method could be modified to handle the degbound argument more intelligently:

• There could be a new argument "force" that forces a new computation, regardless of what is in cache.

• If inappropriate (i.e., if the ideal happens to be inhomogeneous), degbound is ignored and a complete Gröbner basis is returned; with "force=True", the degbound is used in the inhomogeneous case as well.

• If a Gröbner basis G is known out to degree D (perhaps D=infinity) and the user requests a Gröbner out to a degree bound d less than or equal to D, then no new computation is computed, but G is returned. Actually, in that situation the arguments "algorithm" and "prot" are ignored as well, since it shouldn't matter whether G has been computed by Singular or by the toy implementation or by Magma. Of course, a new computation could be requested using "force=True".

Note that I have followed a similar approach in my implementation of Gröbner bases for free non-commutative associative homogeneous ideals - see #7797. With that approach, cached methods can not be used, but it would at least be for a good reason.

Note that an additional detail may be taken care of. As much as I know, if one knows a Gröbner basis g out to degree d of an ideal J and wants to compute a Gröbner basis G out to degree D>d, then it is easier to start the computation of G with g and not with J.

[simon-king-jena]

Reviewer: Simon King

[simon-king-jena]

Work Issues: Error prone computations may be done explicitly, but must not be the default

[johnperry-math]

comment:3

I think a solution to Simon's objections would be to create a separate function, perhaps truncated_groebner_basis. It can throw an exception (AttributeError?) if the ideal is not homogeneous (self.is_homogeneous()).

Note that an additional detail may be taken care of. As much as I know, if one knows a Gröbner basis g out to degree d of an ideal J and wants to compute a Gröbner basis G out to degree D>d, then it is easier to start the computation of G with g and not with J.

There is also no need to recompute S-polynomials of degree less than or equal to d. Does anyone know if Singular tracks that or is aware of it? If not, that might be a feature request upstream.

[vbraun]

comment:4

Breaking out the functionality of a fake groebner basis sounds good. I'd prefer partial_groebner_basis or incomplete_groebner_basis since it doesn't imply that its a truncation of anything. The docstring can then contain a big fat warning.

I don't see any good use case for a degree bound with inhomogeneous ideals, but that doesn't mean that it doesn't exist. For very specific ideals it might be useful to be able to compute with degree bounds even if it is not homogeneous, so I want to keep open that possibliity. We should probably show a warning in that case, though.

[johnperry-math]

comment:5

It seems to me that "truncated Gröbner basis" is a correct term for this, at least in the inhomogeneous case. See, for example, Definition 2.8 of "A new efficient algorithm for computing Gröbner bases (F4)" by J-C Faugére, Journal of Pure and Applied Algebra, vol 139 (1999) 61-88. In the homogeneous case, it is called a "degree d" Gröbner basis.

I'm not aware of "partial" or "incomplete" Gröbner basis in the literature, though perhaps they exist.

[simon-king-jena]

comment:6

I think "truncated_groebner_basis" is the correct name in inhomogeneous case. Namely, a "Gröbner basis G_d out to degree d of an ideal I" has the property that all leading monomials of I of degree less than or equal d are divisible by the leading monomial of an element of G. But if a degree bound is given then Singular simply disregards all S-polynomials of degree greater than d.

Hence, in the inhomogeneous case, it could be that the result obtained from a computation with degbound=d does not yield a Gröbner basis out to degree d: It may happen that some leading monomials in degree d only occur when one computes S-polynomials of a higher degree.

I think it is a good idea to add a new function for truncated GBs.

What about the following model?

• There is a new method "I.truncated_groebner_basis(d)". It is supposed to return a truncated Gröbner basis at least out to degree d. Hence, if a higher truncation or actually a complete basis is already in the cache (either in the cache of truncated_groebner_basis or groebner_basis) then it is returned. So, there is only a new computation if needed.

• If the optional parameter "degbound" is used, groebner_basis dispatches to truncated_groebner_basis, and raises a deprecation warning (of course mentioning the new method "truncated_groebner_basis"). It will in future (but not right now, for backward compatibility) only compute complete Gröbner bases.

• groebner_basis remains a cached method (using the fast decorator).

• truncated_groebner_basis uses a hand-made cache, since the cached method decorator would not be able to return a known Gröbner basis truncated at degree 10 if a truncated Gröbner basis at degree 5 is requested. It should also look into the cache of groebner_basis and see if it finds a complete basis.

Concerning John's question whether Singular preserves the information that all S-polynomials out to a certain degree are computed: I don't know. But the real question is not whether Singular keeps that information, but whether libsingular keeps that information. I know, for example, that Singular can provide polynomial rings with arbitrary attributes - but the field storing that information has not been wrapped in Sage. I think attributes for ideals can be used in Sage to some extent, but I don't know if (lib)singular really is able to continue a truncated GB computation.

[vbraun]

comment:7

My issue with the name is that the truncation of the Groebner basis computation is in general not the truncation of the Groebner basis. But it is for homogeneous ideals which is the main use case, so maybe we should use truncated_groebner_basis after all.

My main problem is not that I can't compute a truncated Groebner basis, it is that I want to be able to use it as if it were a complete Groebner basis. This is of course dangerous, but it is also an often-used trick. So there should be a way to do it. It didn't occur to me to meddle with the groebner_basis cache by hand, so we can't expect normal users to figure this out. How about truncated_groebner_basis(force=True) to do that?

[simon-king-jena]

comment:8

Replying to @vbraun:

My issue with the name is that the truncation of the Groebner basis computation is in general not the truncation of the Groebner basis.

Yes. And therefore (at least according to the terminology that I learnt) one has "Gröbner basis out to degree d" on the one hand (that is: the Gröbner basis is completely known out to degree d), and "Gröbner basis truncated at degree d" on the other hand (that is: all S-polynomials of degree at most d can be reduced to zero). For homogeneous ideals the two notions coincide.

This is of course dangerous, but it is also an often-used trick. So there should be a way to do it. It didn't occur to me to meddle with the groebner_basis cache by hand, so we can't expect normal users to figure this out. How about truncated_groebner_basis(force=True) to do that?

I don't understand what truncated_groebner_basis(force=True) is supposed to do. Do you mean that it should insert the truncated basis into the cache of the groebner_basis method (in the way I indicated earlier), such that it will be used in all subsequent normal form computations?

[vbraun]

comment:9

Replying to @simon-king-jena:

I don't understand what truncated_groebner_basis(force=True) is supposed to do. Do you mean that it should insert the truncated basis into the cache of the groebner_basis method (in the way I indicated earlier), such that it will be used in all subsequent normal form computations?

Yes, that is what I meant. This will ensure it is used in _all_ subsequent computations, not just normal forms.

[johnperry-math]

comment:10

Replying to @simon-king-jena:

Replying to @vbraun:

My issue with the name is that the truncation of the Groebner basis computation is in general not the truncation of the Groebner basis.

Yes.

I had never heard of a truncated Gröbner basis outside of this context. Learn something new every day.

If I understand correctly, Volker wants to use this even in the context of inhomogeneous ideals?

[simon-king-jena]

comment:11

Replying to @johnperry-math:

If I understand correctly, Volker wants to use this even in the context of inhomogeneous ideals?

Yes, but "wants to use" is perhaps the wrong wording. He wants to give the user the possibility to use this, error prone though it is in a non-homogeneous context.

Certainly truncation will not be the default, and certainly there will be a big fat warning message in the documentation, telling the user that Sage's money-back guarantee will expire if he/she uses that method. Or at least that is what I understood...

[johnperry-math]

comment:12

Replying to @simon-king-jena:

Yes, but "wants to use" is perhaps the wrong wording. He wants to give the user the possibility to use this, error prone though it is in a non-homogeneous context.

Yes, that was my intent by the phrase.

[johnperry-math]

comment:13

Replying to @vbraun:

Replying to @simon-king-jena:

I don't understand what truncated_groebner_basis(force=True) is supposed to do. Do you mean that it should insert the truncated basis into the cache of the groebner_basis method (in the way I indicated earlier), such that it will be used in all subsequent normal form computations?

Yes, that is what I meant. This will ensure it is used in _all_ subsequent computations, not just normal forms.

If the user subsequently called groebner_basis(), would it return the truncated version even if the correct basis was desired? If so, how would one avoid that? I could easily see someone in the future using truncated_groebner_basis(force=true) and someone else having problems because (s)he is unaware that groebner_basis() is returning a cached method.

[vbraun]

Rediffed for Sage-4.7.2.alpha2

[vbraun]

comment:14

Attachment: trac_11667_use_groebner_basis_with_degree_bound.patch.gz

Replying to @johnperry-math:

If the user subsequently called groebner_basis(), would it return the truncated version even if the correct basis was desired?

No. By definition, it this would not be desired after the user forced Sage to use the incomplete Groebner basis.

If so, how would one avoid that?

One would not. If you go out of your way to break it, you get to keep both pieces.

Your hypothetical ignorant user could have just as well modified the @cached_method cache and thus broken mathematical correctness. The truncated_groebner_basis() method will at least have documentation that warns against precisely this.