Solving Polynomial Systems Globally Invariant Under an Action of the Symmetric Group and Application to the Equilibria of N vortices in the Plane

Jean-Charles Faugère (1) , Jules Svartz (1)

1 PolSys - Polynomial Systems

We propose an efficient algorithm to solve polynomial systems of which equations are globally invariant under an action of the symmetric group SN acting on the variable xi with s(xi) = xs(i) and the number of variables is a multiple of N. For instance, we can assume that swapping two variables (or two pairs of variables) in one equation gives rise to another equation of the system (perhaps changing the sign). The idea is to apply many times divided difference operators to the original system in order to obtain a new system of equations involving only the symmetric functions of a subset of the variables. The next step is to solve the system using Gröbner techniques; this is usually several order faster than computing the Gröbner basis of the original system since the number of solutions of the corresponding ideal, which is always finite has been divided by at least N!. To illustrate the algorithm and to demonstrate its efficiency, we apply the method to a well known physical problem called equilibria positions of vortices. This problem has been studied for almost 150 years and goes back to works by von Helmholtz and Lord Kelvin. Assuming that all vortices have same vorticity, the problem can be reformulated as a system of polynomial equations invariant under an action of SN. Using numerical methods, physicists have been able to compute solutions up to N 7 but it was an open challenge to check whether the set of solution is complete. Direct naive approach of Gröbner bases techniques give rise to hard-to-solve polynomial system: for instance, when N = 5, it takes several days to compute the Gröbner basis and the number of solutions is 2060. By contrast, applying the new algorithm to the same problem gives rise to a system of 17 solutions that can be solved in less than 0:1 sec. Moreover, we are able to compute all equilibria when N 7.

Domaines: Calcul formel [cs.SC]

Jean-Charles Faugère, Jules Svartz. Solving Polynomial Systems Globally Invariant Under an Action of the Symmetric Group and Application to the Equilibria of N vortices in the Plane. ISSAC '12 - International Symposium on Symbolic and Algebraic Computation, ACM, Jul 2012, Grenoble, France. pp.170-178, ⟨10.1145/2442829.2442856⟩. ⟨hal-00777791⟩