Title: Algorithms for Weighted Sums of Squares Decomposition of Non-negative Univariate Polynomials,
Abstract: It is well-known that every non-negative univariate real polynomial can be
written as the sum of two polynomial squares with real coefficients. When one
allows a weighted sum of finitely many squares instead of a sum of two squares,
then one can choose all coefficients in the representation to lie in the field
generated by the coefficients of the polynomial.
In this article, we describe, analyze and compare both from the theoretical
and practical points of view, two algorithms computing such a weighted sums of
squares decomposition for univariate polynomials with rational coefficients.
The first algorithm, due to the third author relies on real root isolation,
quadratic approximations of positive polynomials and square-free decomposition
but its complexity was not analyzed. We provide bit complexity estimates, both
on runtime and output size of this algorithm. They are exponential in the
degree of the input univariate polynomial and linear in the maximum bitsize of
its complexity. This analysis is obtained using quantifier elimination and root
isolation bounds.
The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies
on complex root isolation and square-free decomposition and has been introduced
for certifying positiveness of polynomials in the context of computer
arithmetics. Again, its complexity was not analyzed. We provide bit complexity
estimates, both on runtime and output size of this algorithm, which are
polynomial in the degree of the input polynomial and linear in the maximum
bitsize of its complexity. This analysis is obtained using Vieta's formula and
root isolation bounds.
Finally, we report on our implementations of both algorithms. While the
second algorithm is, as expected from the complexity result, more efficient on
most of examples, we exhibit families of non-negative polynomials for which the
first algorithm is better.