Gsoc 2011 report jeremias yehdegho: implementing f5

About

I'm Jeremias Yehdegho, student of mathematics at the Graz University of Technology where I enjoy all lectures with "algebra(ic)" in their names. A good friend of mine, who was a mentor at this year's GSoC, suggested I should apply. SymPy seemed particularly well-suited for me.

Overview

My project consisted of implementing the F5B algorithm for computing Gröbner bases, which are generators of ideals in polynomial rings with desirable properties. I also implemented a simplification algorithm for rational functions "modulo a prime ideal". A very special case of this can be used for simplifying some trigonometric exrepssions and there's much room for improvement in this case, something I might get around to soon. In my proposal I had suggested doing a general algorithm for converting Gröbner bases but this didn't work out well, so I only implemented a conversion algorithm for a small class of ideals (which suffices for speeding up solving polynomial equations, though). My mentor was Mateusz.

Algorithms

F5B

As mentioned before, F5B is used to compute Gröbner bases of ideals. It looks quite similar to Buchberger's algorithm but it can avoid many useless reductions of critical pairs. There are a few gotchas, which often impose a certain computation path, which might not always be the fastest. I started by work for GSoC with F5B, which in the most basic form was done quite quickly. I did various optimizations over the next few weeks (selection strategies, imitating some aspects of GROEBNERNEW2 from the book by Becker & Weispfenning, ...).

FGLM

FGLM converts Gröbner bases of "zero-dimensional" ideals, which are ideals generated by a system of polynomials with finitely many solutions. I started FGLM quite early but didn't make any real progress for a while due to lack of understanding. I made good progress at the end of GSoC after giving up on the more general conversion algorithm. SymPy's implemention of FGLM avoids solving a linear equation in every iteration of the algorithm, something I haven't seen anywhere else (and only mentioned casually in the FGLM paper).

Rational simplification modulo prime ideal

This algorithm simplifies expressions f/g, where f and g are both polynomials "modulo" some prime ideal, which has to be given by a Gröbner basis. In other words, this finds a representation of f/g that minimizes the sum of the total degrees w.r.t. some relations (which are given by the ideal). Similarly to FGLM, this was done properly at the end of GSoC.

Looking back & looking forward

My peers have written suggestions for future students here, so I'll write down something I think I should have done: Be more communicative. Quite often I thought that I don't have anything worthwile to contribute (either because I would just be repeating something or because my knowledge on the subject was too meager) but Aaron, Ondrej and the others seem to welcome any contributions (be it code or in discussions). Thanks to Mateusz, especially for the IRC sessions, after which I was most productive.

After finishing my bachelor thesis, I intend to continue contributing to SymPy. There's the aforementioned simplification of (some) trigonometric expressions and linear algebra over more domains would have been useful quite often...