Macaulay2 » Documentation
Packages » SumsOfSquares :: SOSPoly
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

See also

Methods that use an object of class SOSPoly:

For the programmer

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