Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
针对有理系数多项式，提出精确计算其模梯度理想的平方和分解的算法，从而获得精确的非负性证明，并分析了算法的比特复杂度与证书的比特大小界限。
Assessing non-negativity of multivariate polynomials over the reals, through\nthe computation of {\\em certificates of non-negativity}, is a topical issue in\npolynomial optimization. This is usually tackled through the computation of\n{\\em sums-of-squares decompositions} which rely on efficient numerical solvers\nfor semi-definite programming. This method faces two difficulties. The first\none is that the certificates obtained this way are {\\em approximate} and then\nnon-exact. The second one is due to the fact that not all non-negative\npolynomials are sums-of-squares. In this paper, we build on previous works by\nParrilo, Nie, Demmel and Sturmfels who introduced certificates of\nnon-negativity modulo {\\em gradient ideals}. We prove that, actually, such\ncertificates can be obtained {\\em exactly}, over the rationals if the\npolynomial under consideration has rational coefficients and we provide {\\em\nexact} algorithms to compute them. We analyze the bit complexity of these\nalgorithms and deduce bit size bounds of such certificates.\n