#11667: Cache groebner basis independend of degree bound
--------------------------------------------------------------------------------------------+
Reporter: vbraun
| Owner: malb
Type: enhancement
| Status: needs_work
Priority: major
| Milestone: sage-4.7.2
Component: commutative algebra
| Keywords:
Work_issues: Error prone computations may be done explicitly, but must not be
the default | Upstream: N/A
Reviewer: Simon King
| Author: Volker Braun
Merged:
| Dependencies:
--------------------------------------------------------------------------------------------+
Comment(by SimonKing):
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11667#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
