Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
From MaRDI portal
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.
Recommendations
- An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- On exact Polya and Putinar's representations
- On exact Reznick, Hilbert-Artin and Putinar's representations
- An algorithm for sums of squares of a class of positive semi-definite polynomials
Cites work
- A formal proof of the Kepler conjecture
- Accuracy and Stability of Numerical Algorithms
- Algorithms in real algebraic geometry
- Basic algebra. Along with a companion volume `Advanced algebra'
- Certificates of positivity in the Bernstein basis
- Computing rational points in convex semialgebraic sets and sum of squares decompositions
- Computing rational solutions of linear matrix inequalities
- Computing sum of squares decompositions with rational coefficients
- Efficient and accurate computation of upper bounds of approximation errors
- Exact algorithms for linear matrix inequalities
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Formal Proofs for Nonlinear Optimization
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 1601019 (Why is no real title available?)
- scientific article; zbMATH DE number 3785035 (Why is no real title available?)
- scientific article; zbMATH DE number 52177 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- kepler98
- mctoolbox
- Modern computer algebra
- On the combinatorial and algebraic complexity of quantifier elimination
- Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
- Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques
- Sylvester-Habicht sequences and fast Cauchy index computation
- Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
- Univariate real root isolation in an extension field
- Variant quantifier elimination
- Verifying Nonlinear Real Formulas Via Sums of Squares
Cited in
(14)- On sum of squares certificates of non-negativity on a strip
- An algorithm for decomposing a non-negative polynomial as a sum of squares of rational functions
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- univsos
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Convergence of a Constrained Vector Extrapolation Scheme
- A linear algebra method to decompose forms whose length is lower than the number of variables into weighted sum of squares
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size
- A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
- Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
- Univariate rational sums of squares
- Computer-assisted proofs for Lyapunov stability via sums of squares certificates and constructive analysis
- Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem
This page was built for publication: Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733314)
