Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials

DOI10.1016/j.jsc.2018.06.005zbMath1420.13058arXiv1706.03941OpenAlexW2963106619MaRDI QIDQ1733314

Markus Schweighofer, Victor Magron, Mohab Safey El Din

Publication date: 21 March 2019

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.03941

zbMATH Keywords

real algebraic geometryroot isolationsum of squares decompositionNichtnegativstellensätzenon-negative univariate polynomials

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Semialgebraic sets and related spaces (14P10) Real algebra (13J30)

Related Items (9)

Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients ⋮ Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets ⋮ Convergence of a Constrained Vector Extrapolation Scheme ⋮ SONC optimization and exact nonnegativity certificates via second-order cone programming ⋮ 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 ⋮ On sum of squares certificates of non-negativity on a strip ⋮ univsos

Uses Software

• Coq
• PARI/GP
• RAGlib
• SDPA
• mctoolbox
• HOL Light
• SPECTRA
• kepler98

Cites Work

• mctoolbox
• kepler98
• Variant quantifier elimination
• Efficient and accurate computation of upper bounds of approximation errors
• Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
• Certificates of positivity in the Bernstein basis
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Computing sum of squares decompositions with rational coefficients
• Global Optimization with Polynomials and the Problem of Moments
• Exact Algorithms for Linear Matrix Inequalities
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Computing rational solutions of linear matrix inequalities
• Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
• Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
• Verifying Nonlinear Real Formulas Via Sums of Squares
• On the combinatorial and algebraic complexity of quantifier elimination
• Accuracy and Stability of Numerical Algorithms
• Formal Proofs for Nonlinear Optimization
• Univariate real root isolation in an extension field
• A FORMAL PROOF OF THE KEPLER CONJECTURE
• Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques
• Algorithms in real algebraic geometry
• Sylvester-Habicht sequences and fast Cauchy index computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials