An algorithm for sums of squares of real polynomials

DOI10.1016/S0022-4049(97)83827-3zbMath0936.11023MaRDI QIDQ1295495

Thorsten Wörmann, Victoria Powers

Publication date: 24 May 2000

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

zbMATH Keywords

algorithmreal polynomialexplicit representationsum of squares

Mathematics Subject Classification ID

Sums of squares and representations by other particular quadratic forms (11E25) Number-theoretic algorithms; complexity (11Y16)

Related Items (52)

Further results on sum-of-squares tensors ⋮ Symmetry groups, semidefinite programs, and sums of squares ⋮ Computing sum of squares decompositions with rational coefficients ⋮ Semidefinite programming and sums of Hermitian squares of noncommutative polynomials ⋮ Nonlinear state feedback control for a class of polynomial nonlinear discrete-time systems with norm-bounded uncertainties: an integrator approach ⋮ Semidefinite representations for finite varieties ⋮ Computation of the maximal invariant set of discrete-time linear systems subject to a class of non-convex constraints ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ The Pythagoras number of real sum of squares polynomials and sum of square magnitudes of polynomials ⋮ A facial reduction algorithm for finding sparse SOS representations ⋮ On real one-sided ideals in a free algebra ⋮ Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools ⋮ Nonlinear \(H_\infty\) feedback control with integrator for polynomial discrete-time systems ⋮ Reflection groups and cones of sums of squares ⋮ Robust and optimal registration of image sets and structured scenes via sum-of-squares polynomials ⋮ Sublinear circuits and the constrained signomial nonnegativity problem ⋮ A connected component labeling algorithm for implicitly defined domains ⋮ Computation of Sum of Squares Polynomials from Data Points ⋮ Tunable halfband-pair wavelet filter banks and application to multifocus image fusion ⋮ Tight wavelet frames via semi-definite programming ⋮ Noncommutative plurisubharmonic polynomials. I: Global assumptions ⋮ Hilbert's 17th problem and best dual bounds in quadratic minimization ⋮ Positive semidefinite diagonal minus tail forms are sums of squares ⋮ Design of Lyapunov functions for a class of homogeneous systems: Generalized forms approach ⋮ Algorithms for multidimensional spectral factorization and sum of squares ⋮ Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system ⋮ Algorithms for quadratic forms ⋮ The length of \(x_1^4+x_2^4+x_3^4+x_4^4\) as a sum of squares ⋮ Localization of periodic orbits of polynomial vector fields of even degree by linear functions ⋮ Pythagoras numbers of real irreducible algebroid curves and Gram matrices ⋮ Higher-order discrete maximum principle for 1D diffusion-reaction problems ⋮ A novel approach to stability analysis for switched positive linear systems ⋮ Sparsity in sums of squares of polynomials ⋮ A PTAS for the minimization of polynomials of fixed degree over the simplex ⋮ Robust static output feedback design for polynomial nonlinear systems ⋮ Guaranteed error bounds for structured complexity reduction of biochemical networks ⋮ Sums of squares and moment problems in equivariant situations ⋮ Semidefinite programming relaxations and algebraic optimization in control ⋮ Sums of squares over totally real fields are rational sums of squares ⋮ Smaller SDP for SOS decomposition ⋮ Synchronization of the bidirectionally coupled unified chaotic system via sum of squares method ⋮ NCSOStools: a computer algebra system for symbolic and numerical computation with noncommutative polynomials ⋮ Numerical approaches for collaborative data processing ⋮ An algorithm for the global optimization of a class of continuous minimax problems ⋮ Exact Algorithms for Linear Matrix Inequalities ⋮ A linear algebra method to decompose forms whose length is lower than the number of variables into weighted sum of squares ⋮ Noncoercive sums of squares in \(\mathbb R[x_1,\ldots ,x_n\)] ⋮ Positive Gorenstein ideals ⋮ Equivalence of sum of squares convex relaxations for quadratic distance problems ⋮ Non-existence of degree bounds for weighted sums of squares representations ⋮ Computing the Length of Sum of Squares and Pythagoras Element in a Global Field ⋮ Heat transport bounds for a truncated model of Rayleigh-Bénard convection via polynomial optimization

Cites Work

• Solving systems of polynomial inequalities in subexponential time
• Improved Algorithms for Sign Determination and Existential Quantifier Elimination
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An algorithm for sums of squares of real polynomials