KOPS - The Institutional Repository of the University of Konstanz
# Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials

Type of Publication: | Journal article |

Publication status: | Published |

Author: | Magron, Victor; El Din, Mohab Safey; Schweighofer, Markus |

Year of publication: | 2019 |

Published in: | Journal of Symbolic Computation ; 93 (2019). - pp. 200-220. - ISSN 0747-7171. - eISSN 1095-855X |

DOI (citable link): | https://dx.doi.org/10.1016/j.jsc.2018.06.005 |

Summary: |
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 (non-negatively) 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 particular, this allows for an effective treatment of polynomials with rational coefficients.
In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum 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 the runtime and the 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 was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the 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 and compare them in practice on several application benchmarks. 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. |

Subject (DDC): | 510 Mathematics |

Keywords: | Non-negative univariate polynomials, Nichtnegativstellensätze, Sum of squares, decomposition, Root isolation, Real algebraic geometry |

Bibliography of Konstanz: | Yes |

Refereed: | Unknown |

Files | Size | Format | View |
---|---|---|---|

There are no files associated with this item. |

MAGRON, Victor, Mohab Safey EL DIN, Markus SCHWEIGHOFER, 2019. Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials. In: Journal of Symbolic Computation. 93, pp. 200-220. ISSN 0747-7171. eISSN 1095-855X. Available under: doi: 10.1016/j.jsc.2018.06.005

@article{Magron2019-07Algor-44937, title={Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials}, year={2019}, doi={10.1016/j.jsc.2018.06.005}, volume={93}, issn={0747-7171}, journal={Journal of Symbolic Computation}, pages={200--220}, author={Magron, Victor and El Din, Mohab Safey and Schweighofer, Markus} }