next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SOS :: SOSPoly

SOSPoly -- A type to store SOS decompositions of polynomials

Description

A polynomial f∈K[x] is a sum-of-squares (SOS) if it can be written as

f = ∑i di gi2,

where the gi are polynomials in K[x] and the di are positive weights in K. This data type stores SOS polynomials in terms of the summands. The type is a hash table consisting of the polynomials to be squared and summed (the ’generators’), corresponding coefficients, and the base ring. The most common way an SOSPoly comes to life is as the result of an SOS decomposition. 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;
Executing CSDP
Input file: /tmp/M2-4945-0/4.dat-s
Output file: /tmp/M2-4945-0/5
Status: SDP solved, primal-dual feasible
Start rational rounding
i4 : sosPoly sol

o4 = coeffs:
         43  231773
     {5, --, ------}
         20  344000
     gens:
         83 2    2  20 2         2
     {- ---x  + y , --x  + x*y, x }
        200         43

o4 : SOSPoly

Of course one can also construct SOSPolys by specifying all their ingredients.

i5 : R = QQ[x,y];
i6 : s = sosPoly(R, {x+1,y}, {2,3} )

o6 = coeffs:
     {2, 3}
     gens:
     {x + 1, y}

o6 : SOSPoly
i7 : peek s

o7 = SOSPoly{coefficients => {2, 3}  }
             generators => {x + 1, y}
             ring => R

The ingredients of a SOS 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 an SOS is the number of summands:

i11 : length s

o11 = 2

Sums of squares support many common operations with polynomials:

i12 : 2 * s

o12 = coeffs:
      {4, 6}
      gens:
      {x + 1, y}

o12 : SOSPoly
i13 : s + s

o13 = coeffs:
      {2, 3, 2, 3}
      gens:
      {x + 1, y, x + 1, y}

o13 : SOSPoly
i14 : s * s

o14 = coeffs:
      {4, 6, 6, 9}
      gens:
        2                              2
      {x  + 2x + 1, x*y + y, x*y + y, y }

o14 : SOSPoly
i15 : s == s

o15 = true

The actual polynomial can be recovered using sumSOS:

i16 : sumSOS s

        2     2
o16 = 2x  + 3y  + 4x + 2

o16 : R

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

i17 : S = QQ[x,y,z];
i18 : sub (s, S)

o18 = coeffs:
      {2, 3}
      gens:
      {x + 1, y}

o18 : 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.