Self Introductory and Gröebner Bases

[Atahan Haznedar]

Hello everyone, I am Atahan Haznedar from Turkey. Even though Turkish is my native language, I am fluent with English. I am a third year Mathematics undergraduate in Bogazici University in Istanbul. I have been using Linux for 2 years to understand what really open source is, and I have always wanted to be a part of a group to help develop an open source software. I am hoping that GSoC will help me achieve to be part of a group to develop open source project. I started coding with Python 3 years ago, and I have been using it since then for academic purposes and I feel confident about it. I have basic coding experience with C++ (Mostly scripting and optimization purposes) and Octave (Machine Learning course on Coursera by Andrew NG) as well, however I am more familiar with Python. I am studying with 2 different professors at the same time. With one of them we started to learn Gröebner Bases with the book "Ideals, Varieties, and Algorithms by Cox". With the other professor we have read some chapters on "Undergraduate Convexity by Niel Lauritzen" and "Lectures in Geometric Combinatorics By Rekha R. Thomas". At the moment we are implementing an algorithm that uses cones and linear programming optimization for a linearly constrained linear extension problem. I have taken 2 semester Abstract Algebra course that includes Groups, Rings, Fields, and Galois Theory from the book "A First Course in Abstract Algebra by Fraleigh". My main expertise and area of interest is actually Mathematical Logic and Geometry. At the moment I am willing to help contributing to Gröebner Bases algorithm however if someone thinks that my help will be better on different topic its not a problem for me. As for the Gröebner Bases algorithm I can see that the documentation in the sympy is not that heavy at the moment so I can easily start. I am open to any recommendation of books or lectures to this topic since I am flexible as a student.

1. Should I check the book "Groebner Bases: A Computational Approach to Commutative Algebra" before starting?
2. Apart from the articles that are referenced do you recommend anything else to start with?
2. Apart from the articles that are referenced do you recommend anything else to start with?
3. Couldn't find the link for old GSoC22' to see what has been done in the last year for the gröebner bases. Can you link me to it if there is a summary for it?

Thanks in advance.

[Oscar Benjamin]

Hi Atahan,

I don't think that there has been any work on Groebner bases in SymPy
in the last year.

I just looked at the Groebner bases project idea. I guess you mean this one:
https://github.com/sympy/sympy/wiki/GSoC-Ideas#efficient-groebner-bases-and-their-applications

I would say that there are several things that would improve the
performance of SymPy's Groebner basis calculations in this respect:

1. Make use of python_flint to speed up polynomial arithmetic.
2. Improve linear algebra for FGLM and F4 algorithms (the idea
suggests this is needed first for F4).
3. Improve polynomial gcd:
https://github.com/sympy/sympy/wiki/GSoC-Ideas#polynomial-gcd

On the linear algebra side see (plenty of work can be done to improve this):
https://docs.sympy.org/latest/modules/polys/domainmatrix.html
https://docs.sympy.org/latest/modules/polys/domainsintro.html

Also we have the f5b algorithm but it is not used by default even
though it seems to be always faster than buchberger as far as I can
tell. Likewise for zero-dimensional bases it is usually faster to
compute a grevlex basis and convert to lex with fglm. The nonlinsolve
code does this but solve does not. Ideally that would be a simple
option with the groebner function.

Another thing that could be worked on is supporting different
orderings such as elimination ordering. The current code is sort of
there to handle this but doesn't fully work and could certainly be
made easier. With an elimination ordering we could using some
combination of that and resultants as a way to implement an eliminate
function which would be useful:
https://reference.wolfram.com/language/ref/Eliminate.html

The other aspect though is making better use of Groebner bases within
SymPy. Both solve and nonlinsolve use Groebner bases but the code
using them can be improved to give better representations of
positive-dimensional solutions to polynomial systems of equations. I'm
not sure that either makes proper use of factorisation of the
polynomials in the basis to bring everything down to reduced bases for
example.

It would be useful to have a convenient way to compute a factorisation
of a Greobner basis into bases for irreducible components.

Another useful thing would be a way to generate a rational univariate
representation along with some way to represent that for the benefit
of users who are trying to solve systems polynomial equations.

--
Oscar

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5462c493-2044-4928-8c5c-2566b9f7e255n%40googlegroups.com.

[Atahan Haznedar]

Hello Oscar,

Sorry for the late reply, after seeing the post you have made, I can pretty much can say that I am really excited! There are lots of things on the polynomial side to be done as far as I can see. I am not that familiar with Sympy at the moment so probably I am just going to tinker and try to get used to using Sympy in my leisure time by implementing some examples and algorithms that I have studied so far. So probably I am not going to be able to make a contribution soon. Is this a problem for my submission on GSoC?

By the way although I have been studying Combinatorial Geometry for a year now this is my first time learning Gröbner Bases this semester. As I said before, we are studying from the book "Ideals Varieties and Algorithms" [1] and we are in chapter 2 at the moment. My plan until the end of semester is after learning the main concept of Gröbner Bases, I will read and understand the "Additional Gröbner Basis Algorithms" chapter which also includes the Faugère’s F_5 algorithm. After learning it I think it will be easier to understand and implement Tran (2000) and Fukuda et al. (2005). By the way if you recommend me using "Gröbner Bases A Computational Approach to Commutative Algebra" [2] compared to "Ideals Varieties and Algorithms" [1] we can easily change the textbook since we are studying with the professor on 1-1.

I am looking forward to hear from you,

Thanks in advance,

Atahan

---

[1] https://link.springer.com/book/10.1007/978-3-319-16721-3

[2] https://link.springer.com/book/10.1007/978-1-4612-0913-3

[Aaron Meurer]

On Sun, Mar 12, 2023 at 3:04 PM Atahan Haznedar
<atahana...@gmail.com> wrote:
>
> Hello Oscar,
>
> Sorry for the late reply, after seeing the post you have made, I can pretty much can say that I am really excited! There are lots of things on the polynomial side to be done as far as I can see. I am not that familiar with Sympy at the moment so probably I am just going to tinker and try to get used to using Sympy in my leisure time by implementing some examples and algorithms that I have studied so far. So probably I am not going to be able to make a contribution soon. Is this a problem for my submission on GSoC?

Most polynomial algorithms are already implemented in SymPy, but if
you find something that's missing that would definitely be a good
submission. Otherwise, I would recommend finding some bugs to fix
(e.g. from the sympy issue tracker). That's generally the best way to
learn about the codebase in my experience.

>
> By the way although I have been studying Combinatorial Geometry for a year now this is my first time learning Gröbner Bases this semester. As I said before, we are studying from the book "Ideals Varieties and Algorithms" [1] and we are in chapter 2 at the moment. My plan until the end of semester is after learning the main concept of Gröbner Bases, I will read and understand the "Additional Gröbner Basis Algorithms" chapter which also includes the Faugère’s F_5 algorithm. After learning it I think it will be easier to understand and implement Tran (2000) and Fukuda et al. (2005). By the way if you recommend me using "Gröbner Bases A Computational Approach to Commutative Algebra" [2] compared to "Ideals Varieties and Algorithms" [1] we can easily change the textbook since we are studying with the professor on 1-1.

I'm not familiar enough with the literature here to make a specific
recommendation, but I would say generally that texts that have a focus
on practical implementations tend to be more useful. If one of the
books uses pseudocode, for example, that generally makes it easier to
implement the algorithms from.

At the end of the day, you will probably end up making use of multiple
reference texts and papers. You'll need to understand both the theory
and implementation details for a project like this to succeed, so
you'll want to get a good grasp of both perspectives.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/58c8ca18-7918-41d5-b3f7-ce801ee98d56n%40googlegroups.com.

[Oscar Benjamin]

On Fri, 17 Mar 2023 at 20:39, Aaron Meurer <asme...@gmail.com> wrote:
>
> On Sun, Mar 12, 2023 at 3:04 PM Atahan Haznedar
> <atahana...@gmail.com> wrote:
> >
> > Hello Oscar,
> >
> > Sorry for the late reply, after seeing the post you have made, I can pretty much can say that I am really excited! There are lots of things on the polynomial side to be done as far as I can see. I am not that familiar with Sympy at the moment so probably I am just going to tinker and try to get used to using Sympy in my leisure time by implementing some examples and algorithms that I have studied so far. So probably I am not going to be able to make a contribution soon. Is this a problem for my submission on GSoC?
>
> Most polynomial algorithms are already implemented in SymPy, but if
> you find something that's missing that would definitely be a good
> submission. Otherwise, I would recommend finding some bugs to fix
> (e.g. from the sympy issue tracker). That's generally the best way to
> learn about the codebase in my experience.

While many of the most needed algorithms are implemented there is
plenty of scope to improve those implementations or to implement
better algorithms. More commonly though the problem is that the
algorithms are not being used very well by the rest of SymPy. Groebner
bases are a good example here because the algorithms are there and
they work but:

1. By default Groebner uses the slower buchberger algorithm even
though f5b is implemented and similarly many places want a zero
dimensional basis but don't make use of the existing fglm algorithm.
2. The code that consumes the output of Groebner can be massively
improved. The code to solve systems of polynomial equations in solve
and nonlinsolve uses Groebner but really does not do a good job of
processing the output of groebner:
https://github.com/sympy/sympy/issues/24868

The number one priority around Groebner bases is not implementing new
algorithms to compute them but rather improving the way that the
existing algorithms are used in the codebase.

--
Oscar

[Chris Smith]

There was some promising work (as I recall) that stalled at https://github.com/sympy/sympy/pull/609. See discussion there for idea to get that work from level 0 representation of Poly to level 1.

/c

[Chris Smith]

update: When reviewing this it is not clear to me how much of this already made it in in some form or another. Look for PRs be author:pernici that were committed. Search also for lpoly.

/c

[Chris Smith]

There is some preliminary work at https://github.com/sympy/sympy/issues/23665 that aims to improve exponentiation of certain types of polynomials. It might be a good GSOC task.

/c

[thomas...@gmail.com]

Here’s just a little note on the German name Gröbner. The letters ä, ö, and ü can be substituted by ae, oe, and ue and, in fact, the form oe is older than ö. However, some proper names, such as Goethe, always use oe and not ö. The Gröbner basis was named after the mathematician Wolfgang Gröbner, so we see that the proper name in this case is Gröbner. If the substitution is applied, the result is Groebner. In other languages, such a Finnish, the rules are different.

 

Tom

(Dr. Thomas S. Ligon)

thomas...@gmail.com

Frohnloher Str. 6a
81475 Muenchen
Germany
Tel. +49(89)74575075

--

You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3b6ac8d8-caed-4f24-a74f-fb9afca48daen%40googlegroups.com.

[Atahan Haznedar]

Oh apperarantly, I mixed both of them and come up with totally different thing “Gröebner”. Thanks for pointing that out! My mistake there.

Atahan

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/001401d95a55%24049a2070%240dce6150%24%40gmail.com.

[Atahan Haznedar]

Unfortunately I couldn't make any progress fixing an issue for the Sympy repository these couple days. This is the first time for me trying to make a contribution to an open source community. Is it normal that I get overwhelmed and can't make any progress? I really would like to contribute to Sympy with GSoC, however due to my lack of knowledge I feel like i'm not going to be able to make any contribution before submission date. I read and played with github workflow and experimented with sympy for a couple days however it seems that my lack of knowledge for OOP is lacking. What would be the recommendation for me to start developing and doing a proposal for GSoC? I checked the github issues that are related to my area of interest in which you guys recommended me, however they seem like undoable at the moment.

Atahan 

[Oscar Benjamin]

On Wed, 22 Mar 2023 at 21:34, Atahan Haznedar <atahana...@gmail.com> wrote:
>
> Unfortunately I couldn't make any progress fixing an issue for the Sympy repository these couple days. This is the first time for me trying to make a contribution to an open source community. Is it normal that I get overwhelmed and can't make any progress? I really would like to contribute to Sympy with GSoC, however due to my lack of knowledge I feel like i'm not going to be able to make any contribution before submission date. I read and played with github workflow and experimented with sympy for a couple days however it seems that my lack of knowledge for OOP is lacking. What would be the recommendation for me to start developing and doing a proposal for GSoC? I checked the github issues that are related to my area of interest in which you guys recommended me, however they seem like undoable at the moment.

Take a look at the issues with the polys tag:
https://github.com/sympy/sympy/issues?q=is%3Aissue+is%3Aopen+label%3Apolys

This issue for example needs someone to understand the possibilities
and improve the documentation:
https://github.com/sympy/sympy/issues/24394

--
Oscar

[Aaron Meurer]

The oe spelling is common for Gröbner because in many code contexts,
the ö Unicode character is either not allowed or avoided. For
instance, in Python, even though we can use ö in variable names, such
usage is generally avoided to make things easier for people to type,
which is why the SymPy function is called groebner(). In SymPy
documentation either spelling can be used. An advantage of using
Groebner even in contexts where Gröbner would be fine is that it more
closely matches the name used in the Python API, and many readers may
not know that "ö" corresponds to "oe".

By the way, I find it interesting that almost no one maintains the ß
character in German words or names in Romanized transliterations (like
Gauß), but letters with accents are often maintained. I don't know if
there are grammatical or historical reasons for this, or if it's just
because English speakers are more accepting of Latin letters with
accents than with completely non-Latin letters.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/001401d95a55%24049a2070%240dce6150%24%40gmail.com.

[Alan Bromborsky]

Back in the 60's when I was taking German in high school the books still
used the Eszett symbol.  Also remember Stan Freberg's skit on the
Delcaration of Independence and the purfuit of happiness (Jefferson's
fancy spelling using an Eszett letter).