Open mathzeta opened 3 years ago
Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.
What is the status of this ticket? Looking at the Gitlab repo, it seems like that code might be ready for review. Should that be submitted for review on this ticket?
Thanks for looking into it, as I did not worked on it for a long time. I just updated the instructions there for GBNP v1.0.4. From a quick skim, it is almost ready:
# optional: gbnp
or gap_gbnp
in the doctests.growth
method, following GBNP, returns either an integer, a list, or a string. I suppose there are better interfaces.Branch: u/mathzeta2/31446_gbnp_wrapper
Here is an updated version from that repo, which I think is ready for review.
Author: Guy Blachar, Tomer Bauer
Stalled in needs_review
or needs_info
; likely won't make it into Sage 9.5.
It seems like there is a merge issue going on - I'm having trouble viewing the diff, and I'm getting the warning
Warning: Merge failed for 9a3773bcd7c0c544d22f3dfd3b74f422543bc2d3
It needs a simple rebase to the latest develop.
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b97f0f2 | Merge branch 'develop' of https://github.com/sagemath/sage into develop |
44ade13 | Initial version of GBNP wrapper |
088be99 | GBNP: remove periods from INPUT fields |
85ea4e8 | Update GBNP install instructions for v1.0.5 |
e8d3ec0 | GBNP: Full docstrings for internal functions. |
See #34138 for a native Sage version for the exterior algebra.
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b06ceec | Merge branch 'develop' of https://github.com/sagemath/sagetrac-mirror into develop |
a3972b8 | Initial version of GBNP wrapper |
87091cf | GBNP: remove periods from INPUT fields |
ff087de | Update GBNP install instructions for v1.0.5 |
09afe05 | GBNP: Full docstrings for internal functions. |
It looks like there has been a bad merge as there are a number of changes that do not appear related to this ticket. It might be best to cherry-pick the relevant commits into a new branch based off develop
.
O git! Why thou'rt mercurial and not Mercurial?
Let's see if the patchbots will be happy with the new branch.
Last 10 new commits:
6d47b68 | A little more documentation fixes |
01ab094 | Merge branch 'u/klee/28096' of git://trac.sagemath.org/sage into develop |
1975da3 | Merge branch 'develop' of git://trac.sagemath.org/sage into develop |
4729539 | Merge branch 'develop' of git://github.com/sagemath/sage into develop |
b97f0f2 | Merge branch 'develop' of https://github.com/sagemath/sage into develop |
b06ceec | Merge branch 'develop' of https://github.com/sagemath/sagetrac-mirror into develop |
a840700 | Initial version of GBNP wrapper |
0d7f789 | GBNP: remove periods from INPUT fields |
2363c3b | Update GBNP install instructions for v1.0.5 |
da42864 | GBNP: Full docstrings for internal functions. |
Changed branch from u/mathzeta2/31446_gbnp_wrapper to u/mathzeta2/31446_gbnp_wrapper2
Changed branch from u/mathzeta2/31446_gbnp_wrapper2 to u/mathzeta2/31446_gbnp_wrapper3
Branch pushed to git repo; I updated commit sha1. New commits:
d293e67 | GBNP: Simple doc change for patchbot |
Branch pushed to git repo; I updated commit sha1. New commits:
a37d6af | GBNP: Minor doc typo |
The docs seem to build fine for me, so does the failing of the "build documentation" badge is unrelated?
Changed keywords from none to groebner basis
Yes; you can see from the patchbot that the doc built okay.
However, the manual building and installing of the package is not allowed I believe. It does seem to be included in the gap_packages
optional package (from looking at the spkg installation file). So you probably just need to mark the doctests as # optional - gap_packages
and tell the user to install that.
Replying to @tscrim:
Yes; you can see from the patchbot that the doc built okay.
Thanks.
However, the manual building and installing of the package is not allowed I believe. It does seem to be included in the
gap_packages
optional package (from looking at the spkg installation file). So you probably just need to mark the doctests as# optional - gap_packages
and tell the user to install that.
It seems that gap_packages includes GBNP v1.0.3 released 2016-03-08, per their changelog, and the "manual install" here suggests v1.0.5 released 2022-03-09. There are no doctest errors using v1.0.3, but it might be a good idea to update gap_packages in a new ticket.
If I have to guess why the manual install instructions are there, then it has to do with the initial development of this wrapper, which was done using a binary Sage or on Windows (or both). So it was impossible to use gap_packages which requires a compiler, IIRC. The manual install with extracting one tarball is possible in such case, that relied on this obsolete Wiki page. This is still a convenient way to install GAP packages that do not require any compiler.
Do we have anywhere in the Sage docs an explanation how to install optional GAP packages (not the one for gap_packages), or links to the GAP docs? It is a question that come up in ask.sagemath.org from time to time. For this ticket, I suppose using # optional - gap_packages
is a solution while telling the user the recommended way is to install gap_packages, but still leave the manual instructions. Does this sound right?
Branch pushed to git repo; I updated commit sha1. New commits:
589e275 | GBNP: Use gap_packages and update install instructions |
Replying to @mathzeta:
Replying to @tscrim:
Yes; you can see from the patchbot that the doc built okay.
Thanks.
However, the manual building and installing of the package is not allowed I believe. It does seem to be included in the
gap_packages
optional package (from looking at the spkg installation file). So you probably just need to mark the doctests as# optional - gap_packages
and tell the user to install that.It seems that gap_packages includes GBNP v1.0.3 released 2016-03-08, per their changelog, and the "manual install" here suggests v1.0.5 released 2022-03-09. There are no doctest errors using v1.0.3, but it might be a good idea to update gap_packages in a new ticket.
+1 This usually happens with new GAP versions, but it doesn't have to happen in sync.
Do we have anywhere in the Sage docs an explanation how to install optional GAP packages (not the one for gap_packages), or links to the GAP docs? It is a question that come up in ask.sagemath.org from time to time. For this ticket, I suppose using
# optional - gap_packages
is a solution while telling the user the recommended way is to install gap_packages, but still leave the manual instructions. Does this sound right?
The first thing we (or at least I) usually tell people is to install gap_packages
, which has become easier for non-developers IIRC.
I am a very strong -1 on including the "manual" instructions here in anything associated with this ticket. I do not want anything to hint at anything that looks "very official" that hasn't been rigorously tested by the build team.
These instructions can go on some Sage wiki page or something like that, but as a general instruction (of course, with an appropriate warning).
I should also say I am -1 on having any installation instructions. There are other places in Sage already for this. IMO, it is sufficient just to tell the user they need to install it.
Branch pushed to git repo; I updated commit sha1. New commits:
3798b50 | GBNP: Remove manual install instructions |
OK, I have removed the manual install instructions, but kept the paragraph telling that gap_packages is needed. Because gap_packages contains only a small fraction of the available GAP packages, and libgap makes it easier to interface many packages, I think there should be an official place that tells how one can try to install and use new GAP packages. Of course it should tell the state of support (i.e., none) for such endeavors.
Replying to @tscrim:
I should also say I am -1 on having any installation instructions. There are other places in Sage already for this. IMO, it is sufficient just to tell the user they need to install it.
Grepping for sage -i
returns different places in the docs where an optional package is needed. It makes it easier for users to have this information on the same page.
Fair enough. I do agree that it is useful to tell the user directly what to do to get the file to work for "most" users. Although having a more standard page with more robust instructions would be better. That doesn't need to be done here though.
Next I am going to get into the main code comments:
I think this should fit together better with the free algebra implementations that are currently in Sage. I see two obvious ways to do this:
implementation
keyword to FreeAlgebra
.gap()
(and similar) method that returns (and stores) the gap object corresponding to the FreeAlgebra_generic
implementation and other objects. Then you only need to add a algorithm="gap"
argument for the groebner_basis()
method (which would be the default and only one currently accepted).I would do option (2) as it means better exposure and it means we don't have yet-another-implementation. Plus, you are already almost there anyways with subclassing. It's a bit more work, but it will make for a much nicer result IMO. You won't have to mark so many tests as optional either.
I disagree with the letterplace
implementation that returns another ideal rather than a tuple-like object for the GB. This is very different than polynomial rings:
sage: S.<a,b,c> = QQ[]
sage: S.ideal([a*b, b*c-a])
Ideal (a*b, b*c - a) of Multivariate Polynomial Ring in a, b, c over Rational Field
sage: _.groebner_basis()
[a^2, a*b, b*c - a]
sage: type(_)
<class 'sage.rings.polynomial.multi_polynomial_sequence.PolynomialSequence_generic'>
Hence, I think your GB method should return a tuple.
Your interface file is not (just) an interface, it contains an implementation within Sage using the interface. Although if you go with option (2) above, the only things that would really survive would be the _x2y
functions (which gives the interface). Interface files typically go in the interfaces
folder. If you go with (1) above, then I think you should separate the implementation into a separate file (which could be in the free_algebra.py
file) too.
The function names _x2y
are either not descriptive enough or the documentation is not reflecting their generality. I would rename them something like x2y_free_algebra_element
. For an interface file, I think it is important that they are publicly visible.
Not necessary, but it would be nice to have something that checks containment of ideals by reducing the generators of one to the other.
Minor point, but I would like this reverted:
- :maxdepth: 2
+ :maxdepth: 1
as I like the current version.
Replying to @tscrim:
Fair enough. I do agree that it is useful to tell the user directly what to do to get the file to work for "most" users. Although having a more standard page with more robust instructions would be better.
sage.features.gap.GapPackage
should be used for this
Branch pushed to git repo; I updated commit sha1. New commits:
81f11dd | Revert :maxdepth: to 2 in doc |
Replying to @mkoeppe:
sage.features.gap.GapPackage
should be used for this
It is already used.
Replying to @tscrim:
Minor point, but I would like this reverted:
- :maxdepth: 2 + :maxdepth: 1
as I like the current version.
Reverted.
I agree that it is better to have an API consistency for methods called groebner_basis
in Sage, including the commutative case. For the bigger code changes suggested above, it means diving further into the FreeAlgebra
implementation, which I do not have the time currently. Few points to consider: Making sure only the deglex term order is implemented. In _sage2gap
the monoid generators of a free algebra F
(i.e. F.monoid().gens()
) work, but F.gens()
do not work with it. I see that they are objects of different classes, and I just used the first thing that worked. One implementation goal of GBNP is being able to store partial computations, as they might not even terminate, and resume later. All of this should be considered when refactoring.
Replying to @mathzeta:
For the bigger code changes suggested above, it means diving further into the
FreeAlgebra
implementation, which I do not have the time currently.
I don't think there is that much to change. Most of it is just moving the code to free_algebra.py
, removing Gap
in front of names, and only initializing the GBNP when actually needing calling it, which you should do irregardless IMO. You also can get rid of things like
I = super(FreeAlgebra_generic, self).ideal(*gens, **kwds)
return GapIdeal(self, I.gens())
Few points to consider: Making sure only the deglex term order is implemented. In
_sage2gap
the monoid generators of a free algebraF
(i.e.F.monoid().gens()
) work, butF.gens()
do not work with it. I see that they are objects of different classes, and I just used the first thing that worked.
I don't really understand this comment. Of course _sage2gap
only works with one of them, they are completely different classes (even though they have the same string representation).
One implementation goal of GBNP is being able to store partial computations, as they might not even terminate, and resume later. All of this should be considered when refactoring.
It doesn't do that; the onus is on the user to hold onto a reference to output and then build on that. Returning a tuple just means the user has to do one more step of Ip = R.ideal(I.groebner_basis())
instead of Ip = I.groebner_basis()
. I should also stated that a GB is not an ideal, so I would be somewhat surprised by the output being an ideal.
Some other comments:
Rename get_basis()
to basis()
, which should return a Family
. We should have different behaviors for known finite dimensional, which should just return everything. For the infinite case, it is too bad BaseQA
does not iterate through the basis elements. So I think we can do a little helper class to generate things as needed:
class LazyBasis(UniqueRepresentation, Parent):
def __init__(self, Q):
self.Q = Q
self.ngens = Q.cover_ring().ngens()
self.basis = []
Parent.__init__(self, EnumeratedSets().Infinite(), facade=True)
def __getitem__(self, n):
if n < 0:
raise IndexError("infinite list")
if n < len(self.basis):
return self.basis[n]
Q = self.Q
self.basis = libgap.BaseQA(Q._gap_rels, self.ngens, n)
return self.basis[n]
def __iter__(self):
n = 0
while True:
yield self[n]
n += 1
So then we would have
def basis(self):
R = self.cover_ring()
def convert(x):
return _gap2sage(x, R)
if self.is_finite_dimensional():
res = libgap.BaseQA(Q._gap_rels, self.ngens, n)
return Family([covert(x) for x in res])
return Family(convert, LazyBasis(self))
get_matrices()
to get_structure_coefficients()
, which should also should have a basis=None
default that uses the full basis when it is finite dimensional.get_leading_monomials
method is there. It is strange thing for the quotient ring.reduce
, which is something for the ideal, not the quotient ring (where everything is already reduced).hilbert_series()
is a method of the ideal.if type(rels) == GapIdeal:
is better as if isinstance(rels, GapIdeal):
.
The GAP package GBNP, according to its documentation, "provides algorithms for computing Gröbner bases of noncommutative polynomials with coefficients from a field implemented in GAP and with respect to the “total degree first then lexicographical” ordering".
GBNP can be wrapped for Sage by including and adapting this project. The current implementation in Sage for noncommutative Gröbner bases wraps
letterplace
(from Singular) is restricted to weighted homogeneous elements, and it seem to be somewhat less efficient than GBNP. In any case, it is a good idea to have more than one engine for such tasks.Note that GAP supports function fields (including with more than one variable), but the
libgap
interface does not.CC: @mathzeta @tscrim @trevorkarn
Component: algebra
Keywords: groebner basis
Author: Guy Blachar, Tomer Bauer
Branch/Commit: u/mathzeta2/31446_gbnp_wrapper3 @
81f11dd
Issue created by migration from https://trac.sagemath.org/ticket/31446