14h00: Jean-Charles Faugère, SALSA, INRIA Paris-Rocquencourt.
Solving Systems of Polynomial Equations with Symmetries Using SAGBI-Gröbner Bases.
In this talk we describe an efficient method to solve polynomial systems whose equations are left invariant by the action of a finite group $G$. The idea is to simultaneously compute a truncated SAGBI-Gröbner bases (a generalization of Gröbner bases to ideals of subalgebras of polynomial ring) and a Gröbner basis in the invariant ring $\mathbb{K}[\sigma_1,\ldots,\sigma_n]$ where $\sigma_i$ is the $i$-th elementary symmetric polynomial.
To this end, we provide two algorithms: first, from the $F_5$ algorithm we can derive an efficient algorithm for computing truncated SAGBI-Gröbner bases of the ideals in invariant rings. A first implementation of this algorithm in C enable us to estimate the practical efficiency: for instance, it takes only 10 seconds to compute a SAGBI basis of Cyclic 9 modulo a 15 bits prime. The second algorithm is inspired by the FGLM algorithm: from a truncated SAGBI-Gröbner basis of a zero-dimensional ideal we can compute efficiently a Gröbner basis in some invariant rings $\mathbb{K}[h_1,\ldots,h_n]$. Finally, we will show how this two algorithms can be combined to find a representation of the complex roots of such invariant polynomial systems.
Virginie Collette
Last modified: Mon Mar 30 14:53:58 CEST 2009