Opened 8 years ago
Last modified 5 years ago
#11667 needs_work enhancement
Cache groebner basis independend of degree bound
Reported by: | vbraun | Owned by: | malb |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | commutative algebra | Keywords: | |
Cc: | SimonKing, burcin | Merged in: | |
Authors: | Volker Braun | Reviewers: | Simon King |
Report Upstream: | N/A | Work issues: | Error prone computations may be done explicitly, but must not be the default |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
Attachments (1)
Change History (19)
comment:1 Changed 8 years ago by
- Cc SimonKing burcin added
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Reviewers set to Simon King
- Status changed from needs_review to needs_work
- Work issues set to Error prone computations may be done explicitly, but must not be the default
comment:3 Changed 8 years ago by
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.
comment:4 Changed 8 years ago by
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.
comment:5 Changed 8 years ago by
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.
comment:6 Changed 8 years ago by
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.
comment:7 follow-up: ↓ 8 Changed 8 years ago by
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?
comment:8 in reply to: ↑ 7 ; follow-ups: ↓ 9 ↓ 10 Changed 8 years ago by
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 abouttruncated_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?
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 13 Changed 8 years ago by
Replying to SimonKing:
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 thegroebner_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.
comment:10 in reply to: ↑ 8 ; follow-up: ↓ 11 Changed 8 years ago by
Replying to SimonKing:
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?
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 years ago by
Replying to john_perry:
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...
comment:12 in reply to: ↑ 11 Changed 8 years ago by
Replying to SimonKing:
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.
comment:13 in reply to: ↑ 9 ; follow-up: ↓ 14 Changed 8 years ago by
Replying to vbraun:
Replying to SimonKing:
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 thegroebner_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.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
Replying to john_perry:
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.
comment:15 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:16 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:17 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:18 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
I don't like that approach, for two reasons.
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:
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.