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

Synopsis

Usage:

solveDecomposableSystem F

solveDecomposableSystem (A,C)

solveDecomposableSystem (A,)
Inputs:
- F, a list, of (Laurent) polynomial equations.
- A, a list, of matrices whose column vectors are the support of a system of (Laurent) polynomial equations
- C, a list, whose i-th entry is the list of coefficients for the i-th polynomial equation.
Optional inputs:
- Verbose => an integer, default value 0, produces some level of printed output, where $0$ indicates no output and $3$ indicates the most output.
- Verify => an integer, default value 0, which when set to $1$ confirms at each step of the computation that the number of solutions computed is equal to the mixed volume of the polynomial system
- Software => a symbol, default value PHCPACK, describing which numerical solver to use to compute solutions to sparse polynomial systems which are not decomposable
- Tolerance => a real number, default value .00001, a tolerance governing whether a numerical solution belongs to the algebraic torus
- TriangularSystem => a Boolean value, default value true, describing if it is, a priori, possible that the input is triangular
- LacunarySystem => a Boolean value, default value true, describing if it is, a priori, possible that the input is lacunary
- Strategy => ..., default value {}, when set to FromGeneric, the software will solve a generic sparse system $G$, supported on $A$, and compute the solutions to $F$ via a parameter homotopy
Outputs:
- a list, of solutions to the polynomial equations in the algebraic torus

Description

This function 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 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.
Found:2 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions via monodromy
Found:3 solutions 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 :

solveDecomposableSystem(List)
solveDecomposableSystem(List,List)
solveDecomposableSystem(List,Nothing)

For the programmer

The object solveDecomposableSystem is a method function with options.