This is DecomposableSparseSystems.info, produced by Macaulay2, version 1.20

DecomposableSparseSystems -- Solving decomposable sparse polynomial systems
***************************************************************************

Description
===========

There are two natural ways a sparse polynomial system can be decomposed in the
sense of (T. Brysiewicz, J. I. Rodriguez, F. Sottile, and T. Yahl, Solving
Decomposable Sparse Systems, arXiv:2001.04228, 2019). These methods detect and
compute these decompositions and use them to compute solutions.

Authors
=======

  * Taylor Brysiewicz (see https://sites.google.com/view/taylorbrysiewicz )
    <taylorbrysiewicz@gmail.com>
  * Jose Israel Rodriguez (see https://www.math.wisc.edu/~jose/ )
    <Jose@math.wisc.edu>
  * Frank Sottile (see https://www.math.tamu.edu/~sottile )
    <sottile@math.tamu.edu>
  * Thomas Yahl (see https://math.tamu.edu/~thomasjyahl )
    <thomasjyahl@tamu.edu>

Certification a gold star
=========================

Version 1.0.1 of this package was accepted for publication in volume 11 (see
https://msp.org/jsag/2021/11-1/ ) of The Journal of Software for Algebra and
Geometry (see http://j-sag.org/ ) on 25 March 2021, in the article Decomposable
sparse polynomial systems (see https://msp.org/jsag/2021/11-1/p06.xhtml ). That
version can be obtained from the journal (see
https://msp.org/jsag/2021/11-1/jsag-v11-n1-x06-DecomposableSparseSystems.zip )
or from the Macaulay2 source code repository (see
http://github.com/Macaulay2/M2/blob/c07e21e64bfa7f37ce7969b2a1bad99666d0fb17/M2
/Macaulay2/packages/DecomposableSparseSystems.m2 ).

Version
=======

This documentation describes version 1.0.1 of DecomposableSparseSystems.

Source code
===========

The source code from which this documentation is derived is in the file
DecomposableSparseSystems.m2 (see
common/share/Macaulay2/DecomposableSparseSystems.m2 ). The auxiliary files
accompanying it are in the directory DecomposableSparseSystems/ (see
common/share/Macaulay2/DecomposableSparseSystems/ ).

Exports
=======

  * Functions and commands
      * isDecomposable -- Decides whether a polynomial
        system is decomposable
      * isLacunary -- Decides whether a polynomial system is
        lacunary
      * isTriangular -- Decides whether a polynomial
        system is triangular
      * solveDecomposableSystem -- recursively
        solves a sparse (Laurent) polynomial system through a decomposition
  * Methods
      * "isDecomposable(List)" -- see isDecomposable, --
        Decides whether a polynomial system is decomposable
      * "isLacunary(List)" -- see isLacunary, -- Decides
        whether a polynomial system is lacunary
      * "isTriangular(List)" -- see isTriangular, --
        Decides whether a polynomial system is triangular
      * "solveDecomposableSystem(List)" -- see solveDecomposableSystem,
        -- recursively solves a sparse (Laurent)
        polynomial system through a decomposition
      * "solveDecomposableSystem(List,List)" -- see
        solveDecomposableSystem, -- recursively solves
        a sparse (Laurent) polynomial system through a decomposition
      * "solveDecomposableSystem(List,Nothing)" -- see
        solveDecomposableSystem, -- recursively solves
        a sparse (Laurent) polynomial system through a decomposition
  * Symbols
      * "FromGeneric" -- see solveDecomposableSystem,
        -- recursively solves a sparse (Laurent)
        polynomial system through a decomposition
      * "FromVertexGeneric" -- see solveDecomposableSystem,
        -- recursively solves a sparse (Laurent)
        polynomial system through a decomposition
      * "LacunarySystem" -- see solveDecomposableSystem,
        -- recursively solves a sparse (Laurent)
        polynomial system through a decomposition
      * "TriangularSystem" -- see solveDecomposableSystem,
        -- recursively solves a sparse (Laurent)
        polynomial system through a decomposition

For the programmer
==================

The object DecomposableSparseSystems, is a package (Macaulay2Doc).

isDecomposable -- Decides whether a polynomial system is decomposable
*********************************************************************

Synopsis
========

  * Usage:
        isDecomposable F
        isDecomposable A
  * Inputs:
      * F, a list (Macaulay2Doc), of (Laurent) polynomial
        equations.
      * A, a list (Macaulay2Doc), of matrices whose column vectors
        are the support of a system of (Laurent) polynomial equations
  * Outputs:
      * a Boolean value (Macaulay2Doc), a boolean asserting
        whether the polynomial system (or set of supports) is decomposable

Description
===========

A polynomial system is decomposable if it is either lacunary or triangular.
This function checks whether a polynomial system is decomposable.

The function isDecomposable accepts a list of polynomials forming a system.

+---------------------------------------------------------+
|i1 : R=QQ[x,y];                                          |
+---------------------------------------------------------+
|i2 : F={3+x^2*y^2-(17/3)*x^4*y^4,2-x^2+5*y^2-13*x^2*y^2};|
+---------------------------------------------------------+
|i3 : isDecomposable F                                    |
|                                                         |
|o3 = true                                                |
+---------------------------------------------------------+

The function isDecomposable also accepts a list of supports encoded as
matrices.

+---------------------------------------------------------------+
|i4 : A = {matrix{{0,2,4},{0,2,4}},matrix{{0,0,2,2},{0,2,0,2}}};|
+---------------------------------------------------------------+
|i5 : isDecomposable A                                          |
|                                                               |
|o5 = true                                                      |
+---------------------------------------------------------------+
|i6 : B = {matrix{{0,2,4},{0,2,3}},matrix{{0,1,0},{0,0,1}}};    |
+---------------------------------------------------------------+
|i7 : isDecomposable B                                          |
|                                                               |
|o7 = false                                                     |
+---------------------------------------------------------------+

See also
========

  * isLacunary -- Decides whether a polynomial system is
    lacunary
  * isTriangular -- Decides whether a polynomial system is
    triangular

Ways to use isDecomposable :
============================

  * "isDecomposable(List)"

For the programmer
==================

The object isDecomposable, is a method function (Macaulay2Doc).

isLacunary -- Decides whether a polynomial system is lacunary
*************************************************************

Synopsis
========

  * Usage:
        isLacunary F
        isLacunary A
  * Inputs:
      * F, a list (Macaulay2Doc), of (Laurent) polynomial
        equations.
      * A, a list (Macaulay2Doc), of matrices whose column vectors
        are the support of a system of (Laurent) polynomial equations
  * Outputs:
      * a Boolean value (Macaulay2Doc), a boolean asserting
        whether the polynomial system (or set of supports) is lacunary

Description
===========

A polynomial system is lacunary when its support spans a proper sublattice of
full rank of the integer lattice. This function checks whether a polynomial
system is lacunary.

The function isLacunary accepts a  list of polynomials forming a system.

+---------------------------------------------------------+
|i1 : R=QQ[x,y];                                          |
+---------------------------------------------------------+
|i2 : F={3+x^2*y^2-(17/3)*x^4*y^4,2-x^2+5*y^2-13*x^2*y^2};|
+---------------------------------------------------------+
|i3 : isLacunary F                                        |
|                                                         |
|o3 = true                                                |
+---------------------------------------------------------+

The function isLacunary also accepts a list of supports encoded as matrices.

+---------------------------------------------------------------+
|i4 : A = {matrix{{0,2,4},{0,2,4}},matrix{{0,0,2,2},{0,2,0,2}}};|
+---------------------------------------------------------------+
|i5 : isLacunary A                                              |
|                                                               |
|o5 = true                                                      |
+---------------------------------------------------------------+
|i6 : B = {matrix{{0,2,4},{0,2,4}},matrix{{0,1,0},{0,0,1}}};    |
+---------------------------------------------------------------+
|i7 : isLacunary B                                              |
|                                                               |
|o7 = false                                                     |
+---------------------------------------------------------------+

See also
========

  * isTriangular -- Decides whether a polynomial system is
    triangular
  * isDecomposable -- Decides whether a polynomial
    system is decomposable

Ways to use isLacunary :
========================

  * "isLacunary(List)"

For the programmer
==================

The object isLacunary, is a method function (Macaulay2Doc).

isTriangular -- Decides whether a polynomial system is triangular
*****************************************************************

Synopsis
========

  * Usage:
        isTriangular F
        isTriangular A
  * Inputs:
      * F, a list (Macaulay2Doc), of (Laurent) polynomial
        equations.
      * A, a list (Macaulay2Doc), of matrices whose column vectors
        are the support of a system of (Laurent) polynomial equations
  * Outputs:
      * a Boolean value (Macaulay2Doc), a boolean asserting
        whether the polynomial system (or set of supports) is triangular

Description
===========

A polynomial system is triangular if, after a monomial change of coordinates,
there is a proper subset of $k$ equations which involve only the first $k$
variables. This function checks whether a polynomial system (or set of
supports) is triangular.

The function isTriangular accepts a list of polynomials forming a system.

+---------------------------------------------------------+
|i1 : R=QQ[x,y];                                          |
+---------------------------------------------------------+
|i2 : F={3+x^2*y^2-(17/3)*x^4*y^4,2-x^2+5*y^2-13*x^2*y^2};|
+---------------------------------------------------------+
|i3 : isTriangular F                                      |
|                                                         |
|o3 = true                                                |
+---------------------------------------------------------+

The function isTriangular also accepts  a list of supports encoded as matrices.

+---------------------------------------------------------------+
|i4 : A = {matrix{{0,2,4},{0,2,4}},matrix{{0,0,2,2},{0,2,0,2}}};|
+---------------------------------------------------------------+
|i5 : isTriangular A                                            |
|                                                               |
|o5 = true                                                      |
+---------------------------------------------------------------+
|i6 : B = {matrix{{0,2,4},{0,2,3}},matrix{{0,1,0},{0,0,1}}};    |
+---------------------------------------------------------------+
|i7 : isTriangular B                                            |
|                                                               |
|o7 = false                                                     |
+---------------------------------------------------------------+

See also
========

  * isLacunary -- Decides whether a polynomial system is
    lacunary
  * isDecomposable -- Decides whether a polynomial
    system is decomposable

Ways to use isTriangular :
==========================

  * "isTriangular(List)"

For the programmer
==================

The object isTriangular, is a method function (Macaulay2Doc).

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

Synopsis
========

  * Usage:
        solveDecomposableSystem F
        solveDecomposableSystem (A,C)
        solveDecomposableSystem (A,)
  * Inputs:
      * F, a list (Macaulay2Doc), of (Laurent) polynomial
        equations.
      * A, a list (Macaulay2Doc), of matrices whose column vectors
        are the support of a system of (Laurent) polynomial equations
      * C, a list (Macaulay2Doc), whose i-th entry is the list of
        coefficients for the i-th polynomial equation.
  * Optional inputs (Macaulay2Doc),:
      * Verbose => an integer (Macaulay2Doc), default value 0,
        produces some level of printed output, where $0$ indicates no output
        and $3$ indicates the most output.
      * Verify => an integer (Macaulay2Doc), 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 (Macaulay2Doc), default value
        PHCPACK, describing which numerical solver to use to compute solutions
        to sparse polynomial systems which are not decomposable
      * Tolerance => a real number (Macaulay2Doc), default value
        .00001, a tolerance governing whether a numerical solution belongs to
        the algebraic torus
      * TriangularSystem => a Boolean value (Macaulay2Doc),
        default value true, describing if it is, a priori, possible that the
        input is triangular
      * LacunarySystem => a Boolean value (Macaulay2Doc),
        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 (Macaulay2Doc), 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 (Polyhedra),
five times and return the minimum to determine the
mixed volume of any non-decomposable system being solved by Software (NumericalAlgebraicGeometry).
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 :
=====================================

  * "solveDecomposableSystem(List)"
  * "solveDecomposableSystem(List,List)"
  * "solveDecomposableSystem(List,Nothing)"

For the programmer
==================

The object solveDecomposableSystem, is a
method function with options (Macaulay2Doc).