next | previous | forward | backward | up | top | index | toc | Macaulay2 website
DecomposableSparseSystems :: solveDecomposableSystem

solveDecomposableSystem -- recursively solves a sparse (Laurent) polynomial system through a decomposition

Synopsis

Description

This implements Algorithm 9 in (T.Brysiewicz, J.I.Rodriguez, F.Sottile, and T.Yahl, Solving Decomposable Sparse Systems, arXiv:2001.04228, 2019). It recursively checks whether or not the input sparse polynomial system is decomposable, computes the decomposition, and then calls itself on each portion of the decomposition. When the input is not decomposable it solves multivariate polynomial systems with the numerical solver given by the option Software and it solves univariate polynomial systems using companion matrices.

This function accepts a sparse polynomial system in the form of exponents and coefficients.

i1 : A = {matrix{{0,2,4},{0,2,4}},matrix{{0,0,2,2},{0,2,0,2}}};
i2 : C = {{1,3,7},{1,17,-3,23*ii}};
i3 : solveDecomposableSystem(A,C)

o3 = {{.702415-1.63878*ii, .217314-.267712*ii}, {.702415-1.63878*ii,
     ------------------------------------------------------------------------
     -.217314+.267712*ii}, {-.702415+1.63878*ii, .217314-.267712*ii},
     ------------------------------------------------------------------------
     {-.702415+1.63878*ii, -.217314+.267712*ii}, {.637282+.51731*ii,
     ------------------------------------------------------------------------
     .688424+.295073*ii}, {.637282+.51731*ii, -.688424-.295073*ii},
     ------------------------------------------------------------------------
     {-.637282-.51731*ii, .688424+.295073*ii}, {-.637282-.51731*ii,
     ------------------------------------------------------------------------
     -.688424-.295073*ii}, {1.77892-.630257*ii, .239172-.221165*ii},
     ------------------------------------------------------------------------
     {1.77892-.630257*ii, -.239172+.221165*ii}, {-1.77892+.630257*ii,
     ------------------------------------------------------------------------
     .239172-.221165*ii}, {-1.77892+.630257*ii, -.239172+.221165*ii},
     ------------------------------------------------------------------------
     {.526478+.569343*ii, .264761+.747295*ii}, {.526478+.569343*ii,
     ------------------------------------------------------------------------
     -.264761-.747295*ii}, {-.526478-.569343*ii, .264761+.747295*ii},
     ------------------------------------------------------------------------
     {-.526478-.569343*ii, -.264761-.747295*ii}}

o3 : List

It also accepts the sparse polynomial itself

i4 : R=CC[x,y];
i5 : F = {x^4+3*y^6-1,17*x^2-2*y^2+2};
i6 : solveDecomposableSystem F

o6 = {{.0857238+.407474*ii, .412225+.720254*ii}, {.0857238+.407474*ii,
     ------------------------------------------------------------------------
     -.412225-.720254*ii}, {-.0857238-.407474*ii, .412225+.720254*ii},
     ------------------------------------------------------------------------
     {-.0857238-.407474*ii, -.412225-.720254*ii}, {.0857238-.407474*ii,
     ------------------------------------------------------------------------
     .412225-.720254*ii}, {.0857238-.407474*ii, -.412225+.720254*ii},
     ------------------------------------------------------------------------
     {-.0857238+.407474*ii, .412225-.720254*ii}, {-.0857238+.407474*ii,
     ------------------------------------------------------------------------
     -.412225+.720254*ii}, {.190028*ii, .832502}, {.190028*ii, -.832502},
     ------------------------------------------------------------------------
     {-.190028*ii, .832502}, {-.190028*ii, -.832502}}

o6 : List

When $C$ is not entered, the method will choose random coefficients for $C$ and solve that sparse polynomial system. The output is then the pair $(F,S)$ where $F$ is the random sparse polynomial system chosen and $S$ are the solutions to that system in the algebraic torus.

i7 : A = {matrix{{0,2,4},{0,2,4}},matrix{{0,0,2,2},{0,2,0,2}}};
i8 : (F,S)=solveDecomposableSystem(A,)

                                4 4                            2 2          
o8 = ({(- .288652 + .102598*ii)x x  + (- .447102 + .460291*ii)x x  - .866002
                                1 2                            1 2          
     ------------------------------------------------------------------------
                                          2 2                             2  
     + .483774*ii, (.414854 + .444789*ii)x x  + (- .0428314 + .122642*ii)x  +
                                          1 2                             1  
     ------------------------------------------------------------------------
                            2
     (.102663 + .409083*ii)x  - .613611 + .146095*ii}, {{2.26363-.972212*ii,
                            2
     ------------------------------------------------------------------------
     .368462-.309321*ii}, {2.26363-.972212*ii, -.368462+.309321*ii},
     ------------------------------------------------------------------------
     {-2.26363+.972212*ii, .368462-.309321*ii}, {-2.26363+.972212*ii,
     ------------------------------------------------------------------------
     -.368462+.309321*ii}, {.47614-.724379*ii, 1.35825-.156519*ii},
     ------------------------------------------------------------------------
     {.47614-.724379*ii, -1.35825+.156519*ii}, {-.47614+.724379*ii,
     ------------------------------------------------------------------------
     1.35825-.156519*ii}, {-.47614+.724379*ii, -1.35825+.156519*ii},
     ------------------------------------------------------------------------
     {1.84186-3.43817*ii, .1962-.336199*ii}, {1.84186-3.43817*ii,
     ------------------------------------------------------------------------
     -.1962+.336199*ii}, {-1.84186+3.43817*ii, .1962-.336199*ii},
     ------------------------------------------------------------------------
     {-1.84186+3.43817*ii, -.1962+.336199*ii}, {.164898-.681737*ii,
     ------------------------------------------------------------------------
     1.52658-1.53471*ii}, {.164898-.681737*ii, -1.52658+1.53471*ii},
     ------------------------------------------------------------------------
     {-.164898+.681737*ii, 1.52658-1.53471*ii}, {-.164898+.681737*ii,
     ------------------------------------------------------------------------
     -1.52658+1.53471*ii}})

o8 : Sequence

Setting Verify greater than zero will run mixedVolume five times and return the minimum to determine the mixed volume of any non-decomposable system being solved by Software. If the number of solutions found does not equal this computation, the software will run ten monodromy loops to attempt to populate the missing solutions. As the mixed volume computation is accurate up to some probability, we do not use this as a stopping criterion for the monodromy computation.

i9 : R=CC[x,y];
i10 : F = {x^4+3*y^6-1,17*x^2-2*y^2+2};
i11 : solveDecomposableSystem (F,Verify=>1,Tolerance=>0.1,Verbose=>3)
The mixed volume of 
{3*x_2^3+x_1^2-1, 17*x_1-2*x_2+2}
 is 3
 yet we found 2 points
Attempting to find all 3 points via monodromy.
Monodromy recovery was successful
basicSolver: Computed 3 solutions

o11 = {{.0857238+.407474*ii, .412225+.720254*ii}, {.0857238+.407474*ii,
      -----------------------------------------------------------------------
      -.412225-.720254*ii}, {-.0857238-.407474*ii, .412225+.720254*ii},
      -----------------------------------------------------------------------
      {-.0857238-.407474*ii, -.412225-.720254*ii}, {.0857238-.407474*ii,
      -----------------------------------------------------------------------
      .412225-.720254*ii}, {.0857238-.407474*ii, -.412225+.720254*ii},
      -----------------------------------------------------------------------
      {-.0857238+.407474*ii, .412225-.720254*ii}, {-.0857238+.407474*ii,
      -----------------------------------------------------------------------
      -.412225+.720254*ii}, {.190028*ii, .832502}, {.190028*ii, -.832502},
      -----------------------------------------------------------------------
      {-.190028*ii, .832502}, {-.190028*ii, -.832502}}

o11 : List

Ways to use solveDecomposableSystem :

For the programmer

The object solveDecomposableSystem is a method function with options.