GSoC 2012: Groebner Bases
Sergiu Ivanov
I'd like to hear a definitive word on the status of Groebner bases in
SymPy. The ideas page says (just like it did a couple weeks ago) that
there was a project on this topic last year, and then it invites the
student to contact the developers, which I hereby do :-)
In the source tree, I can see the file sympy/polys/groebnertools.py,
which contains the implementation of Buchberger and F5B algorithms.
I've seen some suggestions for further improvement on the list (
https://groups.google.com/forum/?fromgroups#!topic/sympy/EI47kQM6S8c
), however neither of them has made it into the official ideas page.
I'd be interested in working on (improving) Groebner bases, so it
would be great to settle on a task which I could start preparing for.
I would also be very glad to hear from the people who are willing to
mentor such a task.
The ideas page says that Groebner bases in SymPy would benefit from
improvements to linear algebra. I absolutely don't mind (moreover,
I'd like it) to include a couple of such improvements into my eventual
proposal. Moreover, I could actually try to make a couple such
improvements right away, as a part of satisfying the patch
requirement.
A slight disclaimer is that I'm still not completely through my
Groebner bases course at the uni, so I'm by far not an expert in this
domain. I do believe though that my passion for and (something that I
consider to be) general knowledge of algebra, and, particularly of
modules and rings, will be sufficient to eventually grasp any
Groebner-bases-related idea.
Sergiu
Aaron Meurer
the codebase, with the exception of
https://github.com/sympy/sympy/pull/563. I've CC'd Jeremias (the
student who worked on it last year) and Mateusz (his mentor), to see
if they have any more comments. As far as I know, Mario's suggestion
is valid.
If Mateusz is free, he'll likely be the one to mentor such a project.
Otherwise, I don't know. Mario, would you be willing to help out with
such a project, if not directly mentor it. I think your knowledge of
Groebner bases is probably the strongest. We can help out where your
knowledge of the codebase is lacking.
Otherwise, I'll do it, though I'll have to update my own knowledge of
Groebner bases and these algorithms (which would not be a bad thing).
As for the linear algebra, I'm not sure it's something you could just
do really quickly, though feel free to look into it. What we need to
do is make things faster, and one way would be to restructure things
in Matrix so that they are similar to the way they are in Poly.
Otherwise, from my understanding, the algorithms that use linear
algebra are not really faster, as they kind of assume that the linear
algebra will be fast(er).
Aaron Meurer
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>
Sergiu Ivanov
> As far as I know, everything that has been implemented is already in
> the codebase, with the exception of
> https://github.com/sympy/sympy/pull/563. I've CC'd Jeremias (the
> student who worked on it last year) and Mateusz (his mentor), to see
> if they have any more comments. As far as I know, Mario's suggestion
> is valid.
Hm, I see. That pull request looks like it needs some love. I'll
throw a look at what is done there and what the problem with merge
conflicts is.
> If Mateusz is free, he'll likely be the one to mentor such a project.
> Otherwise, I don't know. Mario, would you be willing to help out with
> such a project, if not directly mentor it. I think your knowledge of
> Groebner bases is probably the strongest. We can help out where your
> knowledge of the codebase is lacking.
>
> Otherwise, I'll do it, though I'll have to update my own knowledge of
> Groebner bases and these algorithms (which would not be a bad thing).
Aha. Well, that's good news, I guess :-)
> As for the linear algebra, I'm not sure it's something you could just
> do really quickly, though feel free to look into it. What we need to
> do is make things faster, and one way would be to restructure things
> in Matrix so that they are similar to the way they are in Poly.
> Otherwise, from my understanding, the algorithms that use linear
> algebra are not really faster, as they kind of assume that the linear
> algebra will be fast(er).
Hm, I see. I think I'll at least look into those issues. Maybe there
are some simpler things I could fix and get the general idea.
Eventually, I don't mind working on linear algebra, so exploring this
module may result in me preparing another proposal.
Sergiu
mario
> Otherwise, I don't know. Mario, would you be willing to help out with
> such a project, if not directly mentor it. I think your knowledge of
> Groebner bases is probably the strongest. We can help out where your
> knowledge of the codebase is lacking.
on it. I suggested it because from what I read I got the impression that
it is doable in SymPy.
Sergiu Ivanov
I've had some tense days recently, with a couple test-papers at the
uni, so I hadn't had the time to work intensively, but I'm back now.
I have found two articles on Groebner walks (attached). The first one
(publication_637.pdf) seems to be *the* paper on the topic, so I'm now
reading it attentively. The second paper seems to suggest some
improvements, but I haven't yet read it.
Once I have read the first article, I will post my conclusions here
and will read the code in groebnertools.py once again, to get a better
understanding of how things work and how they depend on matrices.py.
I will then start writing my proposal on SymPy wiki, as I've seen that
this is the recommended way to do that.
Sergiu
P.S. I'm also working on improving the Wikipedia page, but it's
happenning rather slowly, because I'm doing that only when I'm not
good for anything more complicated.
Sergiu Ivanov
<unlimite...@gmail.com> wrote:
>
> I have found two articles on Groebner walks (attached). The first one
> (publication_637.pdf) seems to be *the* paper on the topic, so I'm now
> reading it attentively. The second paper seems to suggest some
> improvements, but I haven't yet read it.
It turned out that publication_637.pdf is too scarce as far as
introduction in the domain is concerned, so I recommend reading
0501345v3.pdf (reattached) to whoever would like to mentor the project
:-)
I have started drafting my proposal here [0], there's nothing on that
page yet, but I'll post an announcement once it's ready.
Sergiu
Sergiu Ivanov
<unlimite...@gmail.com> wrote:
>
> [0] https://github.com/sympy/sympy/wiki/GSoC-2012:-Application-by-Sergiu-Ivanov:-Implementing-Generic-Gr%C3%B6bner-Walk
Sorry, I failed to pay attention to the proper page naming convention :-(
https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Sergiu-Ivanov:-Generic-Gr%C3%B6bner-Walk
Sergiu
Sergiu Ivanov
This is the draft of my proposal about Groebner walk:
https://github.com/sympy/sympy/wiki/GSoC-2012-Application-Sergiu-Ivanov:-Generic-Gr%C3%B6bner-Walk
I'd be very happy to hear some feedback :-)
Sergiu
Ronan Lamy
job of summarising the feasibility of your project, its evaluation
criteria and the benefits it would bring. However, some points
(particularly the section "Infrastructure setup") could be made more
concrete if you wrote some doctest-ish pseudocode. Bonus points if the
code actually works.
I don't know much about the subject, so I only have a few specific
comments:
> As a way to better structure the code, I propose a (partial)
transition to object-oriented design.
Yay! +10.
> I suggest defining a very basic class Operation which will initially
contain one method with two arguments, which will perform the operation
itself.
I suspect that having to use the object in order to perform the
operation would be cumbersome, so it might be more fruitful to consider
Operation as a description of the operation, instead of as the operation
itself.
> I will start by defining the function nextPoint()
"nextPoint" isn't PEP8-compliant. It should be "next_point".
> July 9 - July 15: start merging the changes upstream; start working on
the documentation;
That's rather late. Any pull request with more than ~10 commits is
painful to review. A pull request at that stage is likely to contain a
few dozen commits, so you'd be lucky if it got merged before the end of
August. You should endeavour to send pull requests as soon as you have a
consistent and well-tested piece of functionality.
Sergiu Ivanov
>
> This looks like it'll be a solid proposal. In particular, you do a good
> job of summarising the feasibility of your project, its evaluation
> criteria and the benefits it would bring. However, some points
> (particularly the section "Infrastructure setup") could be made more
> concrete if you wrote some doctest-ish pseudocode. Bonus points if the
> code actually works.
Thank you for your feedback!
I will throw down some pseudo-code in a couple of days.
>> As a way to better structure the code, I propose a (partial)
> transition to object-oriented design.
>
> Yay! +10.
Cool :-)
>> I suggest defining a very basic class Operation which will initially
> contain one method with two arguments, which will perform the operation
> itself.
>
> I suspect that having to use the object in order to perform the
> operation would be cumbersome, so it might be more fruitful to consider
> Operation as a description of the operation, instead of as the operation
> itself.
This is exactly the point of Operation: it will eventually store the
information about the operation *and* will be able to actually perform
the operation on two elements. The problem is that implementing a
full fledged Operation is beyond the scope of my project, so I am only
going to set up a very basic form of it. Eventually, when someone
(maybe myself even, but later) gets to work on base classes for
abstract algebraic structures, it will be possible to easily migrate
the existing Groebner code base to the proper structures.
>> I will start by defining the function nextPoint()
>
> "nextPoint" isn't PEP8-compliant. It should be "next_point".
Oh, sorry, habits :-( Fixed.
>> July 9 - July 15: start merging the changes upstream; start working on
> the documentation;
>
> That's rather late. Any pull request with more than ~10 commits is
> painful to review. A pull request at that stage is likely to contain a
> few dozen commits, so you'd be lucky if it got merged before the end of
> August. You should endeavour to send pull requests as soon as you have a
> consistent and well-tested piece of functionality.
I actually had this thought while writing the proposal, but wasn't
sure about it. For me, pushing things upstream in small chunks feels
much more comfortable; it's good news that the developers are also
comfortable with strategy.
Fixed the proposal by removing explicit statements about merging in
the timeline and adding a proposition about pushing things in small
chunks after the timeline.
Sergiu
Aaron Meurer
I've written another mail to this list about this. We need to really
focus on merging things early and often this summer.
Aaron Meurer
Sergiu Ivanov
I will answer to a comment by Tom here, partly because it's more
comfortable for me to write E-mails. Should anyone feel this switch
is wrong, we can always turn back to discussing on Melange.
Tom Bachmann March 30, 2012, 9:37 a.m.
>Regarding Groebner Walk: Does it also work for modules? (I plan on submitting a pull request in a couple of days that implements some simple groebner basis algorithms for modules)
Googling for "groebner walk modules" does give some results, among
which the attached paper. (Sorry, I sometimes can't get the proper
URLs out of Google's search results). I haven't studied this article,
but my expectations are roughly the following: while adapting the
Groebner walk to modules is doable, I strongly doubt the possibility
of reusing the same code for doing walks both for ideals and
submodules.
This my personal opinion only, though.
>Regarding Object-Oriented redesign of polys code: please consider that Mateusz (the main author of everything in polys/) has put a lot of thought and work into the code. Note also that for many applications in mind, the performance of Groebner basis algorithms is highly sensitive. Thus at least the core functionality should be implemented in as raw a form as possible. This also facilitates later potential re-implementation in e.g. C. In any case, Mateusz is the most likely mentor for this project, so it's him you have to get on bord. Note also that in domains/, there are already classes for rings, polynomialrings etc (although they implement functionality somewhat different from what you envision).
Yes, I absolutely don't doubt that a lot of thought has been put into
the code I was looking at. However, the polys module is not
absolutely devoid of classes, therefore I think that my additions
aren't that unusual :-)
Nevertheless, the fact that I try to use the object-oriented approach
in my implementation in no way hinders the eventual exclusion of
classes. The classes I am suggesting are only going to include a
couple methods; it should be very easy to take these methods out and
turn them into simple functions, thus forgetting about classes.
>Regarding object-oriented structures for algebraic objects: please note that various people in various GSOC projects, and also without GSOC, seem to be thinking about implementing this sort of thing. In fact I myself have been toying with the idea of implementing a commutative algebra / algebraic geometry module that provides various of the classes. What I am trying to say is: implementation and optimization of the groebner-walk algorithm is most likely the most importand, and hardest, part of your project, and it would be a great addition to sympy. It seems less important, and more messy, to get the "meta-infrastructure" set up and past tons of discussion on the list (this is not to discourage you, just a heads up...).
Thank you for pointing out the classes in domains/ ! I haven't
managed to come over them. As you have noted, these classes indeed
focus on something different from what I envision to achieve with the
classes I suggest. I will make an explicit point (and I will also
modify the proposal accordingly) that I in no way plan to fully
implement rings and polynomial rings as algebraic structures. My goal
is making my code future-compatible with the eventual introduction of
these algebraic structures. Frankly speaking, I won't be surprised if
the classes which I will (maybe) implement will eventually be thrown
away and substituted with something else. However, migrating the
Groebner walk to this "something" else should be much easier because
of the foundations I am going to lay in this project.
On the other hand, as I say in the proposal, the classes Ring, Ideal,
etc. will only have the most basic of the functionality; I can't even
consider them to be skeletons of the corresponding algebraic
structures. This is why I don't expect much trouble with getting such
changes merged, especially if I have discussed the modifications
before.
>More technicalities: "high-level" classes should apparently go into "...tools.py" files in polys/. Look at e.g. polytools.py --- it has a GroebnerBasis class!
Oh, indeed! Thank you so much! I have seen it appear across the
code, but I couldn't trace the name to the origins and eventually
forgot about it :-(
I will modify my proposal accordingly.
>[If the above sounded rather critical: let me stress that you seem to have put a lot of work and thought into this, and the proposal is very solid. All of my comments should be considered as "minor".]
Thank you very much for your feedback! And thank you for worrying for
the possibility of interpreting your comments as critical :-)
Sergiu
Ronan Lamy
> Hello,
>
> I will answer to a comment by Tom here, partly because it's more
> comfortable for me to write E-mails. Should anyone feel this switch
> is wrong, we can always turn back to discussing on Melange.
>
> Tom Bachmann March 30, 2012, 9:37 a.m.
>
> >Regarding Object-Oriented redesign of polys code: please consider that
> Mateusz (the main author of everything in polys/) has put a lot of
> thought and work into the code. Note also that for many applications in
> mind, the performance of Groebner basis algorithms is highly sensitive.
> Thus at least the core functionality should be implemented in as raw a
> form as possible. This also facilitates later potential
> re-implementation in e.g. C. In any case, Mateusz is the most likely
> mentor for this project, so it's him you have to get on bord. Note also
> that in domains/, there are already classes for rings, polynomialrings
> etc (although they implement functionality somewhat different from what
> you envision).
Writing C in Python gives you the speed of Python and the
maintainability of C. If you want fast Pythonic code, you need to use
Cython or PyPy (well, ATM, PyPy is crap at dealing with big integers,
but hopefully, one day...). They both target idiomatic Python code, so
code using classes in a pythonic way, without over-engineering, is
actually likely to be faster than a mass of global functions with many
extraneous arguments.
>
> Yes, I absolutely don't doubt that a lot of thought has been put into
> the code I was looking at. However, the polys module is not
> absolutely devoid of classes, therefore I think that my additions
> aren't that unusual :-)
>
> Nevertheless, the fact that I try to use the object-oriented approach
> in my implementation in no way hinders the eventual exclusion of
> classes. The classes I am suggesting are only going to include a
> couple methods; it should be very easy to take these methods out and
> turn them into simple functions, thus forgetting about classes.
That's the job of a compiler. You shouldn't worry about it at all.
>
> >Regarding object-oriented structures for algebraic objects: please
> note that various people in various GSOC projects, and also without
> GSOC, seem to be thinking about implementing this sort of thing. In
> fact I myself have been toying with the idea of implementing a
> commutative algebra / algebraic geometry module that provides various
> of the classes. What I am trying to say is: implementation and
> optimization of the groebner-walk algorithm is most likely the most
> importand, and hardest, part of your project, and it would be a great
> addition to sympy. It seems less important, and more messy, to get the
> "meta-infrastructure" set up and past tons of discussion on the list
> (this is not to discourage you, just a heads up...).
>
> Thank you for pointing out the classes in domains/ ! I haven't
> managed to come over them. As you have noted, these classes indeed
> focus on something different from what I envision to achieve with the
> classes I suggest. I will make an explicit point (and I will also
> modify the proposal accordingly) that I in no way plan to fully
> implement rings and polynomial rings as algebraic structures. My goal
> is making my code future-compatible with the eventual introduction of
> these algebraic structures. Frankly speaking, I won't be surprised if
> the classes which I will (maybe) implement will eventually be thrown
> away and substituted with something else. However, migrating the
> Groebner walk to this "something" else should be much easier because
> of the foundations I am going to lay in this project.
As far as I can tell, "domains" don't represent algebraic structures but
are metadata for concrete types. So I agree with your assessment.
>
> On the other hand, as I say in the proposal, the classes Ring, Ideal,
> etc. will only have the most basic of the functionality; I can't even
> consider them to be skeletons of the corresponding algebraic
> structures. This is why I don't expect much trouble with getting such
> changes merged, especially if I have discussed the modifications
> before.
>
> >More technicalities: "high-level" classes should apparently go into
> "...tools.py" files in polys/. Look at e.g. polytools.py --- it has a
> GroebnerBasis class!
Well, that's an awkward and evidently confusing convention. Feel free to
reorganise the code more logically.
Aaron Meurer
From what I remember, there are logical base classes like Ring and
Field, of which the domains are subclasses.
>>
>> On the other hand, as I say in the proposal, the classes Ring, Ideal,
>> etc. will only have the most basic of the functionality; I can't even
>> consider them to be skeletons of the corresponding algebraic
>> structures. This is why I don't expect much trouble with getting such
>> changes merged, especially if I have discussed the modifications
>> before.
>>
>> >More technicalities: "high-level" classes should apparently go into
>> "...tools.py" files in polys/. Look at e.g. polytools.py --- it has a
>> GroebnerBasis class!
>
> Well, that's an awkward and evidently confusing convention. Feel free to
> reorganise the code more logically.
I agree. We should reorganize the polys so that the three layers are
clearer, probably by using three subdirectories.
Aaron Meurer
>>
>> Oh, indeed! Thank you so much! I have seen it appear across the
>> code, but I couldn't trace the name to the origins and eventually
>> forgot about it :-(
>>
>> I will modify my proposal accordingly.
>>
>> >[If the above sounded rather critical: let me stress that you seem to have put a lot of work and thought into this, and the proposal is very solid. All of my comments should be considered as "minor".]
>>
>> Thank you very much for your feedback! And thank you for worrying for
>> the possibility of interpreting your comments as critical :-)
>>
>> Sergiu
>>
>
>
Tom Bachmann
not coming to my rescue in defending his design). The following
statements are true:
- Had I written the polys module, there would be no C-like "functional"
interfaces. There would be very few global functions (all in objects),
and they surely wouldn't have awkward prefixes like sdp_...
- While I do know a lot about writing efficient C and C++ code, I know
basically nothing about what python code is efficient.
- In particular, for highly performance-sensitive code, this is why I
suggested sticking to whatever design there was, *made up by someone
who most likely knows better how to write highly-efficient python
code that I do*.
On 30.03.2012 21:51, Aaron Meurer wrote:
> On Fri, Mar 30, 2012 at 2:22 PM, Ronan Lamy<ronan...@gmail.com> wrote:
>> Le vendredi 30 mars 2012 � 22:15 +0300, Sergiu Ivanov a �crit :
Sergiu Ivanov
> I somehow feel like I have to explain myself (maybe because Mateusz is not
> coming to my rescue in defending his design). The following statements are
> true:
>
> - Had I written the polys module, there would be no C-like "functional"
> interfaces. There would be very few global functions (all in objects),
> and they surely wouldn't have awkward prefixes like sdp_...
Yes, I think I understand your position.
> - While I do know a lot about writing efficient C and C++ code, I know
> basically nothing about what python code is efficient.
I don't claim to have this knowledge either :-)
> - In particular, for highly performance-sensitive code, this is why I
> suggested sticking to whatever design there was, *made up by someone
> who most likely knows better how to write highly-efficient python
> code that I do*.
Yes, I do understand what you say, this is why I deliberately make my
statements sound more on the suggestive than strongly affirmative
side.
I do not of course hold authority in the questions of efficiency; I'm
just stating my opinion publicly, with the hope to collect sufficient
considerations in this regard.
Sergiu