Efficient polynomial systems solving: algorithms & software

Jean-Charles Faugere, CNRS-Universite Paris VI

In this talk we describe briefly different way of solving polynomial systems (Gröbner basis, Triangular systems, Primary decompositions, Decomposition into primes) and review their respective benefits (Radical, Uniqueness, ...). This talk presents in particular a efficient algorithm for computing Gröbner bases: F4. To avoid as much as possible intermediate computation, the F4 algorithm computes successive truncated Gröbner bases and replaces the classical polynomial reduction found in the Buchberger algorithm by the simultaneous reduction of several polynomials. This powerful reduction mechanism is achieved by means of a symbolic precomputation and by extensive use of sparse linear algebra methods. We present also work in progress: a second algorithm, called F5, eliminates the Buchberger criteria so that there is no reduction to zero during the computation when the input system is complete intersection. For solving polynomial systems the F7 algorithm computes a minimal set of associated primes. The F7 algorithm uses all the previous algorithms but also efficient algorithm for change of ordering and fast polynomial factorization package (NTL - V. Shoup). The F7 algorithm can decompose difficult problems such as Cyclic 9 (of dimension 2 with approximately 6500 isolated points). In a second part of the talk we review different applications solved by these algorithms/programs (in cooperation with F. Rouillier: Robotic, Signal Theory, N body problem,...). We describe several interfaces of Gb/FGb with other Computer Algebra Systems (RealSolving/RS, MPSolve, Mupad, ...) and also an easy to use Web interface. We illustrate the various aspects of polynomial solving in a live demo (if a video projector is available).