Add Groebner bases of noncommutative polynomials via GBNP

[mathzeta]

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

[mkoeppe]

comment:1

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.

[trevorkarn]

comment:3

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?

[mathzeta]

comment:4

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:

• The doctests there succeed. There are probably more tests to add from the GBNP docs and from its source code.
• Some functions and methods need proper "Sage-style" documentation. In particular adding # optional: gbnp or gap_gbnp in the doctests.
• An expert in libgap is useful, to check that the code is not doing something completely wrong.
• The growth method, following GBNP, returns either an integer, a list, or a string. I suppose there are better interfaces.

[mathzeta]

Branch: u/mathzeta2/31446_gbnp_wrapper

[mathzeta]

Commit: 9a3773b

[mathzeta]

comment:5

Here is an updated version from that repo, which I think is ready for review.

[mathzeta]

Author: Guy Blachar, Tomer Bauer

[mkoeppe]

comment:7

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[trevorkarn]

comment:8

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

[tscrim]

comment:9

It needs a simple rebase to the latest develop.

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 9a3773b to e8d3ec0

[tscrim]

comment:13

See #34138 for a native Sage version for the exterior algebra.

[sagetrac-git]

Changed commit from e8d3ec0 to 09afe05

[sagetrac-git]

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.

[tscrim]

comment:15

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.

[mathzeta]

comment:16

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.

[mathzeta]

Changed branch from u/mathzeta2/31446_gbnp_wrapper2 to u/mathzeta2/31446_gbnp_wrapper3

[mathzeta]

New commits:

8d22e8a	Initial version of GBNP wrapper
62badb2	GBNP: remove periods from INPUT fields
9525f34	Update GBNP install instructions for v1.0.5
581538d	GBNP: Full docstrings for internal functions.

EDIT: Test

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d293e67

GBNP: Simple doc change for patchbot

[sagetrac-git]

Changed commit from 581538d to d293e67

[sagetrac-git]

Changed commit from d293e67 to a37d6af

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a37d6af

GBNP: Minor doc typo

[mathzeta]

comment:20

The docs seem to build fine for me, so does the failing of the "build documentation" badge is unrelated?

[mathzeta]

Changed keywords from none to groebner basis

[tscrim]

comment:21

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.

[mathzeta]

comment:22

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?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

589e275

GBNP: Use gap_packages and update install instructions

[sagetrac-git]

Changed commit from a37d6af to 589e275

[tscrim]

comment:24

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).

[tscrim]

comment:25

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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3798b50

GBNP: Remove manual install instructions

[sagetrac-git]

Changed commit from 589e275 to 3798b50

[mathzeta]

comment:27

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.

[tscrim]

comment:28

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:

1. Have this be a new implementation via the implementation keyword to FreeAlgebra.
2. Add a 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.

[mkoeppe]

comment:29

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

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

81f11dd

Revert :maxdepth: to 2 in doc

[sagetrac-git]

Changed commit from 3798b50 to 81f11dd

[mathzeta]

comment:31

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.

[mkoeppe]

comment:32

Replying to @mathzeta:

Replying to @mkoeppe:

sage.features.gap.GapPackage should be used for this

It is already used.

Indeed, I missed that. If you want, you can add url=https://github.com/gap-packages/gbnp

[tscrim]

comment:33

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 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.

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))

• Rename 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.

• I don't understand why the get_leading_monomials method is there. It is strange thing for the quotient ring.

• Same for reduce, which is something for the ideal, not the quotient ring (where everything is already reduced).

• For regular polynomial rings, hilbert_series() is a method of the ideal.

• if type(rels) == GapIdeal: is better as if isinstance(rels, GapIdeal):.