The Moment Method for Computing Real Points of Sparse Polynomial Systems

Source abstract

One of the most important problems in computational algebra is the computation of real solutions of a polynomial system. Lasserre, Laurent, and Rostalski introduced a numerical method to compute the real radical of an ideal defining a finite set of real points. Their method is based on moment matrices and reduces the problem to solving a semidefinite program. In this work, we build on this method and on the work of Laurent and Mourrain to exploit the sparsity of the input polynomials. For this purpose, we extend the theory of moment matrices to the setting of affine toric varieties. We prove that, for sparse polynomial systems, this approach allows us to recover real points on affine toric varieties. Moreover, we show that a projection of the spectrahedron associated with the semidefinite program is, in fact, a polytope, and we propose a variation of the method to compute only one real solution of the system.