Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
Jean‐Charles Faugère, Sajjad Rahmany · 2009
In this paper, we propose 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 generalisation of Gröbner bases to ideals of subalgebras of polynomial ring) and a Gröbner basis in the invariant ring K[σ1,..., σn] where σi is the i-th elementary symmetric polynomial. To this end, we provide two algorithms: first, from the F5 algorithm we can derive an efficient and easy to implement 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 92s to compute a SAGBI basis of Cyclic 9 modulo a small 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 K[h1,..., hn]. Finally, we will show how this two algorithms can be combined to find the complex roots of such invariant polynomial systems.