[sage-devel] A Sage interface for FGb (Gröbner bases)
Hi everyone. I created a Sage wrapper for the C interface of FGb, which makes it easy to call FGb from within Sage. The sources are available on Github [1] and can be installed as a Python package into Sage: [1] https://github.com/mwageringel/fgb_sage FGb is a C-library by J. C. Faugère for computing Gröbner bases and supposedly it is one of the faster implementations that exist. It is included with Maple [2]. FGb is closed source, but comes with a C interface that is freely distributed for academic use. Some of the features: • The computations run in parallel. (This only seems to work for computations over finite fields.) • Elimination/block orders are supported. • It runs on Linux and Mac. (There seem to be some issues, though. I could not get FGb to work on my Ubuntu machine. It fails with an "Illegal instruction" error.) In my Sage interface, I implemented just two functions: computing Gröbner bases and elimination ideals. Supposedly, the FGb C-library supports other functionality like computing Hilbert polynomials, but that part of the library is not documented very well, so it does not make sense to try to create wrappers for that. The focus is finding a Gröbner basis which, once computed, can be used by Sage for further computations. I just wanted to share this. Maybe it is useful for someone. Markus [2] https://www-polsys.lip6.fr/~jcf/FGb/Maple/index.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Implementing rings of coordinates
Dear All,
I decided to try inheriting from polynomials, specifically from
`MPolynomialRing_polydict` and `MPolynomial_polydict`, but I noticed
something strange: is there any reason why `MPolynomialRing_polydict`
hardcodes `MPolynomial_polydict` as its element class?
I would have expected something like
```
class MPolynomialRing_polydict( MPolynomialRing_macaulay2_repr,
PolynomialRing_singular_repr, MPolynomialRing_base):
Element = MPolynomial_polydict
```
followed by the use of `Element` whenever this was needed. Instead this class
defines a method `_poly_class` which is only used once in `__init__` to
define generators (at line 142). Afterwards, every method that needs to build
elements imports again MPolynomial_polydict. This happens for example at line
437 for `__call__` and again at line 646 for `monomial_quotient`.
This obviously makes it complicated to add funtionality to the elements.
Thanks
S.
* Simon King [2018-11-21 12:03:24]:
Dear S.,
On 2018-11-20, VulK wrote:
I am trying to implement the ring of coordinates of a Lie group in the
perspective of Peter-Weyl theorem.
Concretely I would like to define a polynomial ring with infinitely many
generators each depending on two points on a lattice. These generators
satisfy many relations but, for the moment, I am happy to forget this fact.
Is this possible in the current sage framework? Which are the classes I
should inherit from?
From a quick look at available classes it looks like InfinitePolynomialRing
and InfinitePolynomial might be the one I am after but I do not see how to
change the indexing sets as I need apart from brute force: I could keep a
dictionary and hack _repr_ accordingly. Any better idea?
I guess as the author of InfinitePolynomial*, I should chime in.
Unfortunately I don't know the background of what you want to achieve.
In particular, I don't know what indexing set you need. Of course,
changing _repr_ in a sub-class is not a hack but common usage.
Perhaps I should try to explain the purpose of InfinitePolynomial: You
have a finite list of symbols and for each symbol you have a family of
generators indexed by natural numbers. Together, they generate a free
commutative K-algebra R (an "infinite polynomial ring"), where K is a field.
Then, the symmetric group S of the natural numbers acts on each family
of generators by permuting indices. Any ideal J in R that is (as a set)
invariant under the S-action is finitely generated in the sense that there
is a finite list of elements g1,...,gn of J such that the union of the
S-orbits of g1,...,gn generates J as an R-ideal. Moreover, ideal
containment can be effectively tested by some flavour of Gröbner basis
theory ("symmetric Gröbner bases").
The purpose of my implementation is to compute symmetric Gröbner bases
and test ideal containment.
Is any of that useful for your application? Or do you just need an
algebra with an indexed family of generators? Then, I suppose it is
possible to implement it using the stuff in sage.sets.family, together
with sage.combinat.free_module.CombinatorialFreeModule
Inspite of its name, CombinatorialFreeModule can be used to implement an
algebra. Beware, however, that it is all a very *general* implementation in
*Python* (not Cython) and (I think) quite convoluted and indirect [e.g.,
apparently one is supposed to implement multiplication of elements not
by providing _mul_ for the elements but by providing a method
product_on_basis for the ring, which is then used in a multiplication
method (again not of the elements but of the ring) that is provided by
the category of AlgebrasWithBasis that is then finally used in a
multiplication method for elements that (if I recall correctly) also is
implemented in Python and is inherited from the category framework].
So, my impression has been that CombinatorialFreeModule is by design not
to be competitive in terms of speed. But I am sure that other people will
disagree with me on that point.
I would recommend to find an appropriate Cython base class for your elements.
You'd sub-class it (in Cython, if you care for speed), by providing _mul_
and _lmul_ for the elements. The parent (i.e., ring) can very well be
implemented in Python, as typically speed matters less for the ring than
for its elements. I could actually imagine to use
CombinatorielFreeModule to implement the ring, but without relying on
product_on_basis, and use a Cython class for the elements.
And please do use the category and coercion framework! You may want to
read this thematic tutorial:
http://doc.sagemath.org/html/en/thematic_tutorials/coercion_and_categories.html
In a second moment I would like to be able to evaluate the element of this
ring at point on the group; is there a way to make them callable?
There is no default implementation for the __call__() method of ring
elements. So, I guess you can just provide it. It's the usual cython way
of making something callable.
Best regards,
Simon
--
You received
[sage-devel] Re: doctest result depending on --long
I think I made significant progress, but now I am in need of help. Progress means, that I reduced the example to a dozen of lines, containing three tests. I am in need of help, because I have no idea why these interact. Martin Am Dienstag, 20. November 2018 17:40:57 UTC+1 schrieb Frédéric Chapoton: > > known issue, see https://trac.sagemath.org/ticket/26586 > > F > > Le mardi 20 novembre 2018 17:26:17 UTC+1, Martin R a écrit : >> >> Dear all! >> >> I am in need of help again. At https://trac.sagemath.org/ticket/25864 I >> have a doctest whose output seems to depend on whether the option --long is >> passed or not. >> >> The doctest is in src/sage/combinat/posets/poset_examples.py: >> >> >> - >> EXAMPLES:: >> >> sage: P = posets.YoungDiagramPoset(Partition([2,2])); P >> Finite meet-semilattice containing 4 elements >> sage: P.cover_relations() >> >> - >> >> I now get (with the branch on the ticket applied) >> >> sage -t --long src/sage/combinat/posets/poset_examples.py >> ** >> File "src/sage/combinat/posets/poset_examples.py", line 1400, in >> sage.combinat.posets.poset_examples.Posets.YoungDiagramPoset >> Failed example: >> P.cover_relations() >> Expected nothing >> Got: >> [[(0, 0), (0, 1)], [(0, 0), (1, 0)], [(0, 1), (1, 1)], [(1, 0), (1, >> 1)]] >> >> versus >> >> sage -t src/sage/combinat/posets/poset_examples.py >> ** >> File "src/sage/combinat/posets/poset_examples.py", line 1400, in >> sage.combinat.posets.poset_examples.Posets.YoungDiagramPoset >> Failed example: >> P.cover_relations() >> Expected nothing >> Got: >> [[(0, 0), (1, 0)], [(0, 0), (0, 1)], [(1, 0), (1, 1)], [(0, 1), (1, >> 1)]] >> ** >> (note that the order of the output changed) >> >> There is one "long" doctest in the same file: >> >> - >> sage: posets.SSTPoset([3,2]).bottom() # long time (6s on >> sage.math, 2012) >> [[1, 1, 1], [2, 2]] >> >> - >> >> If I remove the long from there, the difference goes away, and I get the >> "long" version. >> >> If I run the doctest in the console, I get the "long" version. >> >> How can I debug this? >> >> Help is much appreciated! >> >> Martin >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: doctest result depending on --long
I think I made significant progress, but now I am in need of help. Progress means, that I reduced the example to a dozen of lines, containing three tests. I am in need of help, because I have no idea why these interact. Martin Am Dienstag, 20. November 2018 17:40:57 UTC+1 schrieb Frédéric Chapoton: > > known issue, see https://trac.sagemath.org/ticket/26586 > > F > > Le mardi 20 novembre 2018 17:26:17 UTC+1, Martin R a écrit : >> >> Dear all! >> >> I am in need of help again. At https://trac.sagemath.org/ticket/25864 I >> have a doctest whose output seems to depend on whether the option --long is >> passed or not. >> >> The doctest is in src/sage/combinat/posets/poset_examples.py: >> >> >> - >> EXAMPLES:: >> >> sage: P = posets.YoungDiagramPoset(Partition([2,2])); P >> Finite meet-semilattice containing 4 elements >> sage: P.cover_relations() >> >> - >> >> I now get (with the branch on the ticket applied) >> >> sage -t --long src/sage/combinat/posets/poset_examples.py >> ** >> File "src/sage/combinat/posets/poset_examples.py", line 1400, in >> sage.combinat.posets.poset_examples.Posets.YoungDiagramPoset >> Failed example: >> P.cover_relations() >> Expected nothing >> Got: >> [[(0, 0), (0, 1)], [(0, 0), (1, 0)], [(0, 1), (1, 1)], [(1, 0), (1, >> 1)]] >> >> versus >> >> sage -t src/sage/combinat/posets/poset_examples.py >> ** >> File "src/sage/combinat/posets/poset_examples.py", line 1400, in >> sage.combinat.posets.poset_examples.Posets.YoungDiagramPoset >> Failed example: >> P.cover_relations() >> Expected nothing >> Got: >> [[(0, 0), (1, 0)], [(0, 0), (0, 1)], [(1, 0), (1, 1)], [(0, 1), (1, >> 1)]] >> ** >> (note that the order of the output changed) >> >> There is one "long" doctest in the same file: >> >> - >> sage: posets.SSTPoset([3,2]).bottom() # long time (6s on >> sage.math, 2012) >> [[1, 1, 1], [2, 2]] >> >> - >> >> If I remove the long from there, the difference goes away, and I get the >> "long" version. >> >> If I run the doctest in the console, I get the "long" version. >> >> How can I debug this? >> >> Help is much appreciated! >> >> Martin >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Implementing rings of coordinates
Hi Simon,
thank you for the explanation. As you guessed I do not need ideals nor
Gröbner basis. Forget for the moment the matter of infinitely many
generators: what I would like to implement is a polynomial ring whose
variables are certain functions. One possible way to do this would be to wrap
around multivariate polynomials with a class that keeps a dictionary in
between the actual dummy variables in the ring and the functions I would like
as generators. I would then perform substitutions every time that's needed.
My impression though is that this will get soon very messy.
Going the CombinatorialFreeModule route sounds like a good option (speed is
not a concern at the moment) but I am not sure if there is any facility
already in place to build a monomial basis out of some generators.
Thanks again
Salvatore
* Simon King [2018-11-21 12:03:24]:
Dear S.,
On 2018-11-20, VulK wrote:
I am trying to implement the ring of coordinates of a Lie group in the
perspective of Peter-Weyl theorem.
Concretely I would like to define a polynomial ring with infinitely many
generators each depending on two points on a lattice. These generators
satisfy many relations but, for the moment, I am happy to forget this fact.
Is this possible in the current sage framework? Which are the classes I
should inherit from?
From a quick look at available classes it looks like InfinitePolynomialRing
and InfinitePolynomial might be the one I am after but I do not see how to
change the indexing sets as I need apart from brute force: I could keep a
dictionary and hack _repr_ accordingly. Any better idea?
I guess as the author of InfinitePolynomial*, I should chime in.
Unfortunately I don't know the background of what you want to achieve.
In particular, I don't know what indexing set you need. Of course,
changing _repr_ in a sub-class is not a hack but common usage.
Perhaps I should try to explain the purpose of InfinitePolynomial: You
have a finite list of symbols and for each symbol you have a family of
generators indexed by natural numbers. Together, they generate a free
commutative K-algebra R (an "infinite polynomial ring"), where K is a field.
Then, the symmetric group S of the natural numbers acts on each family
of generators by permuting indices. Any ideal J in R that is (as a set)
invariant under the S-action is finitely generated in the sense that there
is a finite list of elements g1,...,gn of J such that the union of the
S-orbits of g1,...,gn generates J as an R-ideal. Moreover, ideal
containment can be effectively tested by some flavour of Gröbner basis
theory ("symmetric Gröbner bases").
The purpose of my implementation is to compute symmetric Gröbner bases
and test ideal containment.
Is any of that useful for your application? Or do you just need an
algebra with an indexed family of generators? Then, I suppose it is
possible to implement it using the stuff in sage.sets.family, together
with sage.combinat.free_module.CombinatorialFreeModule
Inspite of its name, CombinatorialFreeModule can be used to implement an
algebra. Beware, however, that it is all a very *general* implementation in
*Python* (not Cython) and (I think) quite convoluted and indirect [e.g.,
apparently one is supposed to implement multiplication of elements not
by providing _mul_ for the elements but by providing a method
product_on_basis for the ring, which is then used in a multiplication
method (again not of the elements but of the ring) that is provided by
the category of AlgebrasWithBasis that is then finally used in a
multiplication method for elements that (if I recall correctly) also is
implemented in Python and is inherited from the category framework].
So, my impression has been that CombinatorialFreeModule is by design not
to be competitive in terms of speed. But I am sure that other people will
disagree with me on that point.
I would recommend to find an appropriate Cython base class for your elements.
You'd sub-class it (in Cython, if you care for speed), by providing _mul_
and _lmul_ for the elements. The parent (i.e., ring) can very well be
implemented in Python, as typically speed matters less for the ring than
for its elements. I could actually imagine to use
CombinatorielFreeModule to implement the ring, but without relying on
product_on_basis, and use a Cython class for the elements.
And please do use the category and coercion framework! You may want to
read this thematic tutorial:
http://doc.sagemath.org/html/en/thematic_tutorials/coercion_and_categories.html
In a second moment I would like to be able to evaluate the element of this
ring at point on the group; is there a way to make them callable?
There is no default implementation for the __call__() method of ring
elements. So, I guess you can just provide it. It's the usual cython way
of making something callable.
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from
[sage-devel] Re: Implementing rings of coordinates
Dear S.,
On 2018-11-20, VulK wrote:
> I am trying to implement the ring of coordinates of a Lie group in the
> perspective of Peter-Weyl theorem.
>
> Concretely I would like to define a polynomial ring with infinitely many
> generators each depending on two points on a lattice. These generators
> satisfy many relations but, for the moment, I am happy to forget this fact.
> Is this possible in the current sage framework? Which are the classes I
> should inherit from?
>
> From a quick look at available classes it looks like InfinitePolynomialRing
> and InfinitePolynomial might be the one I am after but I do not see how to
> change the indexing sets as I need apart from brute force: I could keep a
> dictionary and hack _repr_ accordingly. Any better idea?
I guess as the author of InfinitePolynomial*, I should chime in.
Unfortunately I don't know the background of what you want to achieve.
In particular, I don't know what indexing set you need. Of course,
changing _repr_ in a sub-class is not a hack but common usage.
Perhaps I should try to explain the purpose of InfinitePolynomial: You
have a finite list of symbols and for each symbol you have a family of
generators indexed by natural numbers. Together, they generate a free
commutative K-algebra R (an "infinite polynomial ring"), where K is a field.
Then, the symmetric group S of the natural numbers acts on each family
of generators by permuting indices. Any ideal J in R that is (as a set)
invariant under the S-action is finitely generated in the sense that there
is a finite list of elements g1,...,gn of J such that the union of the
S-orbits of g1,...,gn generates J as an R-ideal. Moreover, ideal
containment can be effectively tested by some flavour of Gröbner basis
theory ("symmetric Gröbner bases").
The purpose of my implementation is to compute symmetric Gröbner bases
and test ideal containment.
Is any of that useful for your application? Or do you just need an
algebra with an indexed family of generators? Then, I suppose it is
possible to implement it using the stuff in sage.sets.family, together
with sage.combinat.free_module.CombinatorialFreeModule
Inspite of its name, CombinatorialFreeModule can be used to implement an
algebra. Beware, however, that it is all a very *general* implementation in
*Python* (not Cython) and (I think) quite convoluted and indirect [e.g.,
apparently one is supposed to implement multiplication of elements not
by providing _mul_ for the elements but by providing a method
product_on_basis for the ring, which is then used in a multiplication
method (again not of the elements but of the ring) that is provided by
the category of AlgebrasWithBasis that is then finally used in a
multiplication method for elements that (if I recall correctly) also is
implemented in Python and is inherited from the category framework].
So, my impression has been that CombinatorialFreeModule is by design not
to be competitive in terms of speed. But I am sure that other people will
disagree with me on that point.
I would recommend to find an appropriate Cython base class for your elements.
You'd sub-class it (in Cython, if you care for speed), by providing _mul_
and _lmul_ for the elements. The parent (i.e., ring) can very well be
implemented in Python, as typically speed matters less for the ring than
for its elements. I could actually imagine to use
CombinatorielFreeModule to implement the ring, but without relying on
product_on_basis, and use a Cython class for the elements.
And please do use the category and coercion framework! You may want to
read this thematic tutorial:
http://doc.sagemath.org/html/en/thematic_tutorials/coercion_and_categories.html
> In a second moment I would like to be able to evaluate the element of this
> ring at point on the group; is there a way to make them callable?
There is no default implementation for the __call__() method of ring
elements. So, I guess you can just provide it. It's the usual cython way
of making something callable.
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
