-
Notifications
You must be signed in to change notification settings - Fork 0
GSoC 2012 Application Sergiu Ivanov: Generic Gröbner Walk
Name: Sergiu Ivanov
Enrollment: University of the Academy of Science of Moldova, http://www.edu.asm.md/en (partly in Romanian)
Melange link_id: unlimitedscolobb
Contacts: E-mail: unlimitedscolobb at gmail dot com or sivanov at math dot md, IRC: scolobb, GitHub username: scolobb.
My initial focus was on computer science; in the years 2004-2007, I have successfully taken part in a number of school Olympiads in programming and algorithms. At the university (2007-2011), I have studied formal languages, operating systems, networking, databases, object-oriented programming and Prolog. In my spare time I have got acquainted with a number of programming languages and frameworks, among which are C/C++, Java, Python, .NET/Mono, Smalltalk, Common Lisp, Haskell. At the university, I have also taken courses in calculus, probability, discrete mathematics, numerical methods, and optimisation.
In tried to be a part of GSoC 2008 with GNU/Hurd, with the project "Namespace-based Translator Selection". I was not accepted because of my low activity during the proposal ranking period; however, I worked on the idea voluntarily; one can find the short report of what has been done here. I was accepted to GSoC 2009 to the same organisation (GNU/Hurd), with the project "VFS-based Unionmount". The documentation of the tool I have developed (by extending another one) can be found here.
In my last year of bachelor studies I have implemented a remoting framework in Haskell. The code is here. My diploma project was a simulator of P systems written in Java, Jython, C, and Haskell. The code is here. In my diploma project I made use of OpenCL/CUDA.
I am currently pursuing MSc in "Mathematics and Informatics". I have had courses in parsing, theory of algorithms, measure theory. I have had (or am having) quite a bit of algebra-related courses: modules (and a bit of rings), lattices, quasigroups, Gröbner bases. I am doing part-time research in computability theory with focus on unconventional computing models. In my spare time I am learning category theory, functional programming, and lambda calculus.
I'm running the latest 64-bit Gentoo Linux. I have Python 2.7.2 installed. I prefer to code in Emacs.
I have been using Python every now and then for about 4 years now. I wrote simple to moderately complex university assignments in Python, including a wxPython-based application for creating and editing simple graphs and for running basic graph algorithms (minimal spanning trees and shortest paths mainly) with a custom widget for visually editing graphs. My knowledge of Python remains somewhat patchy, though.
Although I have had encounters with other version control systems, I am most comfortable with Git. I have been actively using Git since 2009, including for management of my university coding and documentation projects.
I have submitted a fix for for Issue 3106; the corresponding pull request has been merged into master.
I have also worked on Issue 2142; the corresponding pull request has not yet been merged, but will hopefully be soon.
SymPy currently supports computing Gröbner bases via improved Buchberger and F5B algorithms. However, the complexity of computing a Gröbner basis of a polynomial ideal depends considerably on the monomial ordering. It turns out that in certain situation less effort is required to compute the Gröbner basis of the polynomial ideal with respect to an "easier" ordering and then use a special algorithm, the Gröbner walk, to convert this basis to the Gröbner basis with respect to the desired monomial term ordering. I plan to implement the Gröbner walk in SymPy.
Gröbner bases are a concept which arise in the theory of multivariate
polynomial rings. Given a monomial ordering, a Gröbner basis of an
ideal I of a polynomial ring K[x_1, ..., x_n] over a field K is
a set of polynomials G = {f_i | i\in A} \subseteq I which have the
property that for any polynomial f \in R the remainder of the
multivariate division of f by the polynomials in G is the same in
whatever ordering one takes the polynomials in G. This uniqueness
property makes knowing a Gröbner basis of an ideal very useful, mainly
because it allows a much easier testing of whether a polynomial f
belongs to an ideal I for which the Gröbner basis is known.
A Gröbner basis of an ideal I is not unique. However, there exists a
special flavour called reduced Gröbner basis of an ideal I, which
is unique for a fixed monomial ordering. This allows testing for
equality of two ideals by comparing their reduced Gröbner bases.
While Gröbner bases are very useful, computing a Gröbner basis is, generally speaking, an NP-complete task [0]. In practise, however, it turns out that the complexity of computations depends considerably on the choice of a monomial ordering [1]. For example, it is generally easier to compute a Gröbner basis with respect to a total degree ordering than with respect to the lexicographic ordering. Because of this dependency, possibilities of converting between Gröbner bases of the same ideal with respect to different monomial orderings were considered. Among the first results in this direction is [2], which suggests a way to convert between two Gröbner bases of a zero-dimensional ideal [3] with respect to two different monomial orderings. A more general solution to convert between two Gröbner bases of a finite-dimensional ideal, the Gröbner walk, was presented in [4]. An improved version of this algorithm, called the generic Gröbner walk, is given in [5].
Currently, SymPy can compute Gröbner bases using the improved
Buchberger algorithm [6] and Faugére 5B algorithm [7]. Both methods
can be invoked via sdp_groebner() by specifying the corresponding
value as the keyword argument method. SymPy also contains the
function matrix_fglm() which implements the FGLM [2] conversion
between reduced Gröbner bases of a zero-dimensional ideal.
The goal of this Google Summer of Code 2012 project is to implement the generic Gröbner walk in SymPy.
In section 6.1 of [5] the authors have compared the times necessary to compute a large Gröbner basis directly and by walking from a smaller Gröbner basis with respect to a different monomial ordering. The algorithm which made use of the generic Gröbner walk has performed worse than direct computation in a rather small number of cases: 4 of 15. Yet, in some cases, it worked as much as 17 times faster than direct computation. This shows that using the Gröbner walk in computing Gröbner bases can sometimes be very advantageous.
In this section I will try to provide a short introduction to the material exposed in [5]. I do not claim to be extensive or detailed, though.
The principal idea behind the Gröbner walk is that a term ordering
(<) in a polynomial ring K[x_1, ..., x_n] can be "represented" by
an n-vector w = (w_1, ..., w_n)\in Q^n. In fact, (<) can be
"represented" by the topological closure C_< of the set of such
vectors [4], which is called the Gröbner cone of (<) in R^n. A
Gröbner cone C_< is actually a (convex polyhedral) cone in R^n; it
has faces of dimension less than n. There may exist another cone
C' in Q^n which has a common face with C_<.
Consider a finite dimensional polynomial ideal I\subseteq K[x_1, ..., x_n]. Given two terms orderings (<_1) and (<_2), consider the
corresponding two Gröbner cones C_{<_1} and C_{<_2} and the
(known) reduced Gröbner basis G_1 of I with respect to (<_1).
Consider two points w\in C_{<_1} and t\in C_{<_2} and the segment
starting from w and ending at t. We can "walk" along this
segment, from w to t. At a certain "moment", we will reach a face
of C_{<_1} and exit the cone. At the same "moment", we necessarily
enter a different cone C', which has a common face with C_{<_1}.
This cone C' "represents" a term ordering (<') and, therefore, one
can compute the reduced Gröbner basis G' of I with respect to
(<'). With the available information, this basis can be computed
easier that in the general case, when one only knows the ideal I and
the term ordering (<'). If (<') = (<_2), then we have arrived at
a reduced Gröbner basis of I with respect to the term ordering
(<_2). If, however, (<') =/= (<_2), then we should continue our
"walk" along the line into the next "neighbouring" cone. This
eventually brings us to the Gröbner basis of I with respect to
(<_2).
I see the implementation split into two mandatory major phases, the content of which will be exposed below.
This section is likely to be hard to comprehend without having looked at [5] beforehand.
In this phase I plan to implement the walk itself. To achieve this I
plan to extend MonomialOrdering with a utility class
GroupMonomialOrdering, which will represent a term ordering in a
K[x_1, ..., x_n]. This class will store n vectors with n
components each, which give a specific term ordering ([5], subsection
2.2). This class will be able to compare two monomials. (Note that
GroupMonomialOrdering will be exactly a monomial ordering; the
meaning of the verb "represent" in section Short Theoretical
Background is quite different from the meaning used in this
paragraph.) It will be possible to create an instance of
GroupMonomialOrdering from one of the standard monomial orderings
(LexOrder, GradedLexOrder, ReversedGradedLexOrder).
Another ordering utility class is the FacetPreorder, which will
store a reference to the corresponding GroupMonomialOrdering and
will compare two vectors in Q^n according to [5], section 4,
equation 3.
The Gröbner walk will be initiated by an invocation of the method
walk() which I plan to add to GroebnerBasis and which will accept
as an argument an instance of GroupMonomialOrdering representing the
target ordering and will return an instance of GroebnerBasis which will
contain the Gröbner basis of the same ideal with respect to the target
monomial ordering. The implementation will follow the algorithm
described [5] and shortly introduced in section Short Theoretical
Background.
I will now provide a more detailed overview of the planned implementation, which is strongly based on the algorithm shown in [5] on pages 11-12.
I will start by defining the function next_point() which corresponds
to Compute_last_w (this correspondence will be remarked in the
docstrings for ease of maintenance). I will construct all vectors in
V and choose the minimal one according to the FacetPreorder
generated from the target GroupMonomialOrdering.
I will then define the function lower_terms() which will return the
list S_g. Further, I will define the function autoreduce() which
will reduce the given list of polynomials with respect to each other.
This functionality is present in sympy/polys/groebnertools.py, in
the function buchberger(), but is not factored out into a separate
function. I plan to take the functionality from there.
The method walk() of GroebnerBasis will invoke next_point() and
then compute the generators of in_w(G), making use of
lower_terms(). It will then compute a new GroebnerBasis (by
creating a new instance of this class) of in_w(G) with respect to
the target monomial ordering. walk() will then construct H',
autoreduce it and restart from step (ii).
According to [5], section 6.1, Gröbner walk is quite efficient when
there are less than 10 Gröbner cones separating the initial and target
monomial orderings, which makes me believe that creating instances of
GroebnerBasis at every step of the walk will not introduce critical
slow-down. See next subsection for further considerations in this
regard.
The second phase of the implementation is the phase in which I will work on improving the existing code related to Gröbner bases, including the (already implemented) Gröbner walk. There is a number of important directions to work on, some of which are listed below, in the order of priority:
-
Profiling and optimisation. As I mentioned in the previous section, I do not expect the transition to a more object-oriented approach to cause significant slow-down. These expectations should be formally verified though. Similarly to [5], I will use the problems suggested in [8] to test the performance of my implementation generic Gröbner walk. I will then compare the timings to what is shown in [5], section 6.1. If the performance is going to be "significantly" worse, I will try to minimise the number of instances of classes my implementation of generic Gröbner walk is going to create.
-
Improve the documentation. The file
sympy/polys/groebnertools.pydoes include some documentation, but it is too scarce and is rather technical. I plan to write a less technical introduction to using this module (including a section about the Gröbner walk). -
Gröbner walk vs. direct computation. It would be very nice if the choice between first computing the Gröbner basis with respect to an "easier" term ordering and then walking to the desired ordering and directly computing the Gröbner basis with respect to the target term order could be done automatically. I expect that it is possible to start with the following simple heuristic: if the target term ordering is
lex, compute the Gröbner basis with respect togrlexand then walk tolex. To refine this heuristics, I will compare the performance of the two approaches on the problems in [8]. -
Extend the applications of Gröbner bases throughout SymPy. Gröbner bases have a considerable number of applications, not all of which are presently made use of in SymPy. As an example, I cannot see Gröbner bases used in ODE solvers, while, according to (at least) [9], there are some useful applications in this domains. I will collect the possibilities of making use of Gröbner bases in SymPy and will then implement them in the order of importance for SymPy.
The following list summarises the results I plan on obtaining by the end of the summer:
-
a working and tested Gröbner walk implementation,
-
"not so technical" documentation for
sympy/polys/groebnertools.py(including the Gröbner walk).
Gröbner bases-related problems have been a priority in the domain I am doing research in for quite some time, mainly because of the useful properties of these bases and, on the other hand, because they are so hard to compute. Therefore, working on a Gröbner bases-related problem will offer me invaluable information which I hope to further use in my research.
Another more personal reason for choosing this task was my preference for everything algebra-related.
I am currently taking a course on Gröbner bases and, according to my professor, the course is going to finalise with an overview of the applications of Gröbner bases. In the previous semester, I had a course on rings and modules. And, finally, I have thoroughly studied [5]. I believe that this provides me with sufficient background to properly understand and eventually implement the Gröbner walk algorithm, as well as work on further improving the Gröbner bases-related capabilities of SymPy.
Before the start of the coding period, I will have to spend quite a lot of time on university matters, which leaves about 2-3 hours per day for SymPy. In this time I plan to rebase https://github.com/sympy/sympy/pull/563 , as well as to work on http://code.google.com/p/sympy/issues/detail?id=2528 I will also have a much closer look at how polynomials are implemented in SymPy so that I will be able to write my own code better.
The schedule of the summer exam session has not yet been firmly established at my university; it is absolutely certain, however, that I will have finished all my exams by June 1st. While I expect to have finished earlier than that, I will plan my activities starting with this date.
During the period before mid-term evaluations, I plan to be fully dedicated to the project, which amounts to not less than 7 hours on average, every day (including the weekend). After the mid-term evaluations, closer to the end of July, I may leave for a week of vacation. Aside from that, I am going to spend the same amount of time (7 hours every day) working on the project.
The following is an approximate timeline of my activities at a week scale:
-
June 1 - June 3: start implementing
GroupMonomialOrderingandFacetPreorder; write the corresponding tests; -
June 4 - June 10: implement
GroupMonomialOrdering,FacetPreorder; start implementing the Gröbner walk; -
June 11 - June 17: implement the Gröbner walk;
-
June 18 - June 24: finish and test the Gröbner walk (add the corresponding unit tests);
-
June 25 - July 1: measure the performance of my implementation of the Gröbner walk; carry out the optimisations;
-
July 2 - July 8: produce the documentation;
-
July 9 - July 15: compare the times of directly computing a Gröbner basis with respect to the target monomial ordering and computing the Gröbner basis with respect to a different monomial ordering and then walking to the target monomial ordering; work on the heuristics of choosing between the two;
-
July 16 - July 22: decide on and implement the heuristics for choosing between directly computing a Gröbner base with respect to the target monomial ordering or computing the base with respect to an "easier" ordering and the walking to the target ordering;
-
July 23 - July 29: look for possibilities of extending the applications of Gröbner bases in SymPy;
-
July 30 - August 5: start using Gröbner bases in other parts of SymPy; finalise merging the changes pertaining to the Gröbner walk;
-
August 6 - August 12: extend the applications of Gröbner bases in SymPy;
-
August 13 - August 19: sort out the remaining issues; continue extending the applications of Gröbner bases in SymPy.
Note that, while I do not explicitly remark this in the timeline, I expect to be pushing the changes upstream as soon as I have bits of functionality which I am confident in. This will hopefully keep the burden of reviewing the changes low.
After the end of GSoC-2012, I plan to finalise those of the actions listed in the third phase of the implementations which will not fit into the GSoC timeframe. After this, I would do my best to maintain the Gröbner bases-related code; but I would be certainly interested in switching to a different (algebra-related) task.
[0] GSoC 2011 Application Jeremias Yehdegho: Implementing F5 - https://github.com/sympy/sympy/wiki/GSoC-2011-Application-Jeremias-Yehdegho%3A-Implementing-F5
[1] Weisstein, Eric W. "Gröbner Basis." From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/GroebnerBasis.html
[2] J. Faugére, P. Gianni, D. Lazard and T. Mora. Efficient computation of zero-dimensional ideal Gröbner bases by change of ordering. J. Symbolic Comp. 16 (1993), 329–344.
[3] Commutative Rings - Dimension - http://en.wikipedia.org/wiki/Commutative_ring#Dimension
[4] S. Collart, M. Kalkbrenner, and D. Mall. Converting bases with the Gröbner walk. J. Symbolic Comp. 6 (1997), 209–217.
[5] K. Fukuda, A. N. Jensen, N. Lauritzen, and R. Thomas. The generic Gröbner walk. http://arxiv.org/abs/math/0501345
[6] T. Becker, V. Weispfenning. Groebner Bases: A Computational
Approach to Commutative Algebra. Springer, 1993, page 232 (according
to sympy/polys/groebnertools.py)
[7] Yao Sun, Dingkang Wang. A New Proof for the Correctness of F5
(F5-Like) Algorithm. http://arxiv.org/abs/1004.0084 (specifically v4)
(according to sympy/polys/groebnertools.py)
[8] K. Aardal, A.K. Lenstra. Hard Equality Constrained Integer Knapsacks. Mathematics of Operations Research 29 (2004), pp. 724--738. ta.twi.tudelft.nl/wst/users/aardal/mor_corr.pdf
[9] G. Czichowski, M. Thiede. Gröbner Bases, Standard Forms of Differential Equations and Symmetry Computation, Seminar Sophus Lie Darmstadt-Erlangen-Greifswald-Leipzig, 1992. www.heldermann-verlag.de/jlt/jlt02/CZICHLAT_vol2.PDF
[10] 4ti2--A software package for algebraic, geometric and combinatorial problems on linear spaces. http://4ti2.de/
[11] Groebner Fans - Sage Reference Manual v4.8. http://www.sagemath.org/doc/reference/sage/rings/polynomial/groebner_fan.html