next | previous | forward | backward | up | index | toc

# SOSPoly -- A type to store sums-of-squares polynomials

## Description

A polynomial $f\in K[x]$ is a sum of squares (SOS) if it can be written as $$f = \sum_i d_i g_i^2,$$ where the $g_i$ are polynomials in $K[x]$ and the $d_i$ are positive weights in $K$. This data type stores polynomials as sums of squares. The type is a hash table consisting of the polynomials to be squared and summed (the 'generators'), corresponding coefficients, and the base ring. We can construct an object of type SOSPoly from the result of sum-of-squares problem. See SDPResult for more on this.

 i1 : R = QQ[x,y]; i2 : f = 2*x^4+5*y^4-2*x^2*y^2+2*x^3*y; i3 : sol = solveSOS f; i4 : sosPoly sol 83 2 2 2 43 20 2 2 231773 2 2 o4 = (5)(- ---x + y ) + (--)(--x + x*y) + (------)(x ) 200 20 43 344000 o4 : SOSPoly

One can also construct an object of type SOSPolys by specifying all their ingredients.

 i5 : R = QQ[x,y]; i6 : s = sosPoly(R, {x+1,y}, {2,3} ) 2 2 o6 = 2*(x + 1) + 3*(y) o6 : SOSPoly i7 : peek s o7 = SOSPoly{coefficients => {2, 3} } generators => {x + 1, y} ring => R

The ingredients of a sum of squares can be recovered using the expected commands.

 i8 : gens s o8 = {x + 1, y} o8 : List i9 : ring s o9 = R o9 : PolynomialRing i10 : coefficients s o10 = {2, 3} o10 : List

The length of a sum-of-squares polynomial is the number of squares.

 i11 : length s o11 = 2

Sums of squares support many common operations with polynomials.

 i12 : 2 * s 2 2 o12 = 4*(x + 1) + 6*(y) o12 : SOSPoly i13 : s + s 2 2 2 2 o13 = 2*(x + 1) + 3*(y) + 2*(x + 1) + 3*(y) o13 : SOSPoly i14 : s * s 2 2 2 2 2 2 o14 = 4*(x + 2x + 1) + 6*(x*y + y) + 6*(x*y + y) + 9*(y ) o14 : SOSPoly i15 : s == s o15 = true

The actual polynomial can be recovered using value(SOSPoly).

 i16 : value s 2 2 o16 = 2x + 3y + 4x + 2 o16 : R

We can also produce a formal Expression.

 i17 : expression s 2 2 o17 = 2*(x + 1) + 3*(y) o17 : Expression of class Sum

Objects of type SOSPoly support the substitute command. This cannot be used to change the coefficient field, though. See coefficient field for some of the limitations.

 i18 : S = QQ[x,y,z]; i19 : sub (s, S) 2 2 o19 = 2*(x + 1) + 3*(y) o19 : SOSPoly

• sosPoly -- make an SOS polynomial

## Methods that use an object of class SOSPoly :

• clean(RR,SOSPoly) -- remove squares with very small coefficients from a sum of squares
• coefficients(SOSPoly)
• expression(SOSPoly)
• generators(SOSPoly)
• length(SOSPoly)
• Matrix == SOSPoly
• net(SOSPoly)
• Number * SOSPoly
• ring(SOSPoly)
• RingElement == SOSPoly
• SOSPoly * SOSPoly
• SOSPoly + SOSPoly
• SOSPoly == Matrix
• SOSPoly == RingElement
• SOSPoly == SOSPoly
• SOSPoly ^ ZZ
• substitute(SOSPoly,Ring)
• value(SOSPoly) -- expansion of a weighted SOS decomposition

## For the programmer

The object SOSPoly is a type, with ancestor classes HashTable < Thing.