Solving systems of polynomial equations with symmetries using SAGBI-Grobner bases

摘要

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¨obner bases (a generalisation of Gr¨obner bases to ideals of subalgebras of polynomial ring) and a Gr¨obner basis in the invariant ring K[A1, . . . , An] where Ai 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¨obner 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¨obner basis of a zero-dimensional ideal we can compute efficiently a Gr¨obner 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.