SOS.m2
A sum of squares package for Macaulay 2
Description
SOS
is a Macaulay2 package for computing sum of squares
(SOS) decompositions of polynomials with rational coefficients. The
algorithm uses an interior point method to solve the underlying
semidefinite program and tries to compute an exact decomposition from
the numerical solution. Presentation
Note: since an efficient SDP solver is an art in itself and beyond the scope of this project, the package
simpleSDP
just implements a very simple method which is
not expected to work well on big problems.
Packages

SOS
, computation of rational sum of squares decompositions; depends on the following three packages: 
simpleSDP
, a simple interior point solver 
LDL
, LDL' factorization for rational matrices 
BlkDiag
, for creating blockdiagonal matrices
Installation
To
use the SOS package you need a working installation of
Macaulay 2 with version number at least 0.9.94.
Steps to install:
Steps to install:
 Download the packages
SOS
,simpleSDP
,LDL
, andBlkDiag
to your working directory  Unzip the SOS package
 Do one of the following:
 Launch Macaulay2 in your download directory and use the
installPackage
command to install the packages, e.g.,i1 : installPackage "LDL" installing package LDL in ../.Macaulay2/encap/LDL1.5/ ...
SinceSOS
is depending on the packagessimpleSDP
,LDL
, andBlkDiag
, it should be installed at last.  If you do not want to install the packages permanently, include the download directory to
Macaulay 2's
path
list.
 Launch Macaulay2 in your download directory and use the
Examples
 Computing a SOS decomposition
The following example demonstrates how to use the functiongetSOS
of theSOS
package to compute a SOS decomposition of a polynomial.i1 : loadPackage"SOS"; i2 : S = QQ[x,y]; i3 : f = 2*x^4+5*y^42*x^2*y^2+2*x^3*y; i4 : (g,d) = getSOS f . . . 2 2 2 1 2 2 7 o4 = (( *x + y , *x + x*y, x ), (5, 2, )) 5 2 10
We can check with thesumSOS
command whether the found decomposition matches the original polynomiali5 : sumSOS(g,d) 4 3 2 2 4 o5 = 2x + 2x y  2x y + 5y o5 : QQ [x, y]
 SOS with parameters
If the coefficients of the polynomial are linearly parameterized, we can also search for parameters which render a polynomial to be a SOS. In the following example, the variablea
will be treated as a free parameter.i6 : S = QQ[x,a]; i7 : f = (a1)*x^4+1/2*a*x+1; i8 : (g,d,aval) = getSOS (f,{a}) . . . 2 2 1 2 5 21 211 o9 = ({ *x + *x + 1, x + *x, x}, {1, , },  2 ) 5 2 21 25 420 o9 : Sequence
The last output argument contains the vector of parameters, i.e,a=2
.  SOS with parameter optimization
Semidefinite programming also allows to optimize a linear functional of the decision variables. As an example we compute a lower bound of a polynomial by minimizing its constant term. Since there is a tradeoff between rounding and optimality, we specify the required rounding precision as an optional input argument.i10 : S = QQ[x,t] o10 = S o10 : PolynomialRing i11 : f = x^4  2*x + t; i12 : (g,d,tVal) = getSOS (f,{t},t,rndTol=>3) . . . 1 2 4 10 2 2 5 9 19 o12 = ({ *x  *x + 1,  *x + x, x }, {, , },  5/4 ) 2 5 9 4 20 144