COCOA VICOmputational COmmutative Algebra
Villa Gualino, Torino, Italy |

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).