-
Notifications
You must be signed in to change notification settings - Fork 0
GSoC 2011 Application Jeremias Yehdegho: Implementing F5
SymPy currently uses Gröbner bases for computations in polynomial rings (GCD, LCM), computing minimal polynomials of algebraic numbers and solving systems of polynomial equations. I plan to implement the F5B flavor of the F5 algorithm in order to improve performance with such computations and allow for new applications, such as simplification of rational functions modulo prime ideals.
A Gröbner basis is a special generating set of an ideal in a polynomial ring. Unlike polynomial rings with a single variable, it is not possible to perform division with remainder but it is possible to do something similar, namely division with remainder with respect to a set of polynomials. This may however yield different results for different orders of the polynomials, even worse: if a polynomial is an element of the ideal, its remainder need not be zero. Gröbner bases have the property that the remainder is always unique.
Computing the division with remainder and Gröbner bases depends on an order relation on the monomials, such as the lexicographic term order. This term order has a useful elimination property, which makes it possible to solve ("overdetermined") systems of polynomial equations (solvers/polysys.py and similarly polys/numberfields.py for minimal polynomials).
"Many problems" can be cleverly encoded in a problem of solving a system of polynomial equations, such as finding a 3-coloring of a graph. This implies that computing a Gröbner basis (with respect to the lexicographic term order) is an NP-hard problem.[3]
I want to implement the F5B algorithm by Yao Sun and Dingkang Wang [1], which is a variation of Jean-Charles Faugère's F5 algorithm. The currently used Buchberger algorithm computes a Gröbner basis by repeatedly constructing a special polynomial from two polynomials in the generating set, computing its remainder with respect to the generating set and adding the remainder to the generating set if it is not zero. As it turns out, these remainders are often zero which gives no new information. In order to improve speed, Faugère's algorithm provides two criteria when a special polynomial will have remainder 0 and need not be further considered.
Why F5B and not some other variant? F5B looks quite similar to Buchberger's algorithm, so I expect "Buchberger - many useless reductions to zero" to perform better than the current algorithm. Furthermore F5B allows any selection strategy [1] for the special polynomial, so I would at least try and benchmark the "sugar method" selection strategy.
Additionally, I want to implement the second algorithm from [2] to compute a simplification of a rational function modulo a prime ideal. (This would also work with the current algorithm.)
If I have enough time left, I would like to take a look at the Gröbner Walk algorithm, which converts a Gröbner basis with respect to one term order to a Gröbner basis with respect to another term order. I find the theory behind it quite interesting but I don't know much about it yet, so consider this optional.
Lastly, this project overlaps with my prospective bachelor thesis, which among other things also includes implementing F5(B). This has been discussed with and agreed on by my thesis advisor.
My name is Jeremias Yehdegho, I'm 22 years old and a fourth year student of mathematics ("Mathematical computer science") at the Graz University of Technology. A few relevant (and perhaps not so relevant) courses I've taken include:
- Introductory course in algebra
- Courses on field theory (one on finite fields and coding theory, one on Galois theory)
- "Symbolic computation" (Mostly factorization of polynomials and Gröbner bases, used SAGE for the exercises)
- Master level courses on algebra, algebraic curves and algebraic number theory (currently). I haven't done the exams yet, though.
- Introductory courses on C and C++
- "Computer Mathematics" (Mathematica, Maple, Matlab/Octave, LaTeX)
My favorite programming language is C, which I believe I know reasonably well. I know a bit of Python (through (very) small scripts, Project Euler and exercises using SAGE). Some other languages I know a bit include: C++, Mathematica and Go.
If it matters, I've been using Linux for about three years exclusively (first Xubuntu, now ArchLinux). I have not contributed to an open source project before, however I wrote the first version of the "Jumanji" web browser (can be found here). The current author rewrote it from scratch, however.
The prescribed dates don't align well with my courses, so I will postpone them to next year. This is fine except for an algebraic number theory class, which might not be offered by the same professor (whose lectures I very much enjoy) next year. The lecture and exercises are on Wednesday 8-10 and 12-14 and Thursay 8-10. To compensate I would start early in my easter break (April 16th to May 7th).
- Write the datastructures (signature, labeled polynomial)
-
- Write F5B
-
- f5_reduction
- is_rewritable
- is_compareable
- ...
-
- Benchmark, improve, benchmark, improve, benchmark, improve, ...
-
- incremental algorithm (with and without interreduction)
- TOP/POT order for signatures (See "A natural Variation" in [1])
- sugar method selection strategy
- Implement the second algorithm from [2]
Since time is running out and I'm quite bad at estimating how long I will need for these tasks (sorry for not reaching out more concerning the schedule), I'll leave it at that and make changes to the schedule either tomorrow or later via the comments.
You can reach me via
- Email at j.[last name]@gmail.com,
- IRC on Freenode as "f1728"
- or
-
- Jabber at [first name].[last name]@edu.uni-graz.at.
[1] A New Proof for the Correctness of F5 (F5-Like) Algorithm, Yao Sun, Dingkang Wang, http://arxiv.org/abs/1004.0084v4
[2] Rational Simplification Modulo a Polynomial Ideal, Michael Monagan, Roman Pearce, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.4135&rep=rep1&type=pdf
[3] Design and implementation issues of a~computer algebra system in an interpreted, dynamically typed programming language, Mateusz Paprocki, http://mattpap.github.com/masters-thesis/html/src/groebner.html#applications-of-groebner-bases