Sparse polynomial systems solved to find real solutions efficiently
The Moment Method for Computing Real Points of Sparse Polynomial Systems
Symbolic Computation
Summary
Finding real solutions to polynomial equations is important but can be very complex. Lasserre, Laurent, and Rostalski developed a method using moment matrices and semidefinite programming to find these solutions. The authors of this work improved that method to take advantage of the sparsity, or few nonzero terms, in many polynomial equations. This helps find real solutions more efficiently, especially for systems related to shapes called affine toric varieties. They also showed how part of the problem can be simplified to a shape called a polytope and designed a way to find just one real solution when needed.
What this means in practice
- •For mathematics software developers: Implement more efficient algorithms to compute real solutions of sparse polynomial systems in computer algebra software.
- •For optimization engineers: Use the sparsity-exploiting moment method to solve problems modeled by polynomial equations with fewer computational resources.
Authors
Tom Baumbach, Matías Bender
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.