Software for Decomposable Sparse Polynomial Systems

Solving Decomposable Sparse Systems, Numerical Algorithms 88, 453-474 (2021)

Decomposable Sparse Polynomial Systems, Journal of Software for Algebra and Geometry Vol. 11 (2021), 53-59

DecomposableSparseSystems.m2 Macaulay2 Page

A sparse polynomial system is decomposable if its associated branched covers factors as a composition of nontrivial branched covers on an open set. Solutions to such systems can be computed by iteratively factoring these branched covers and computing their fibres. These fibres can be computed as solutions to simpler sparse polynomial systems.

We describe this technique of solving sparse polynomial systems explicitly in our paper Solving Decomposable Sparse Systems. We have implemented this method in the Macaulay2 package "DecomposableSparseSystems.m2", which is included in current distributions of Macaulay2.

Example

For a system of polynomial equations $F=\left(F$1,..,Fn), the support of $F$ is the collection of $n$ integer matrices whose columns are the exponent vectors appearing in each polynomial $F$i. Let $\mathrm{A1}=\left(\begin{array}{ccccc}0& 1& 2& 0& 1\\ 0& 0& 0& 1& 1\end{array}\right)$, $\mathrm{A2}=\left(\begin{array}{ccccc}1& 0& 1& 2& 1\\ 0& 1& 1& 1& 2\end{array}\right)$, $\mathrm{B1}=\left(\begin{array}{cccc}0& 2& 0& 2\\ 0& 0& 1& 3\end{array}\right)$, and $\mathrm{B2}=\left(\begin{array}{cccccc}0& 1& 2& 0& 2& 0\\ 0& 0& 0& 1& 1& 2\end{array}\right).$ We consider the columns of these matrices as exponent vectors in this way and display their convex hulls below.

Let $C=\left\{0,1\right\}5$ be the vertices of the five-dimensional cube. We construct sparse decomposable systems from $\mathrm{A•}=\left(\mathrm{A1},\mathrm{A2}\right)$ , $\mathrm{B•}=\left(\mathrm{B1},\mathrm{B2}\right)$, and $C$ as follows. Choose two embeddings $𝒾:\mathrm{ℤ2}\to \mathrm{ℤ5}$ and $𝒿:\mathrm{ℤ2}\to \mathrm{ℤ5}$ such that $𝒾\left(\mathrm{ℤ2}\right) \bigcap 𝒿\left(\mathrm{ℤ2}\right)=\left\{0\right\}.$ For example, choose four linearly independent vectors $\mathrm{i1},\mathrm{i2},\mathrm{j1},\mathrm{j2}$ and define $𝒾\left(a,b\right)=a\mathrm{i1}+b\mathrm{i2}$ and the same for $𝒿.$ These embeddings correspond to monomial maps. For example, the embedding corresonponding to the vectors $\mathrm{i1}=\left(1,2\right)T$ and $\mathrm{i2}=\left(0,3\right)T$ corresponds to the monomial map on $\left(ℂ×\right)2$ sending $\mathrm{x1}\to \mathrm{x1}\mathrm{x22}$ and $\mathrm{x2}\to \mathrm{x23}.$ For any matrix $A,$ the image $𝒾\left(A$1) is the set of exponent vectors that appear by precomposing a polynomial supported on $A$ with the monomial map associated to $𝒾.$ Set

$A\left(𝒾,𝒿\right)=\left(\mathrm{𝒾\left(\mathrm{A1}\right)},\mathrm{𝒾\left(\mathrm{A2}\right)},\mathrm{𝒿\left(\mathrm{B1}\right)},\mathrm{𝒿\left(\mathrm{B2}\right)},C\right).$

Any sparse system with support $A\left(𝒾,𝒿\right)$ is decomposable and can be efficiently solved with the Macaulay2 software above via the command solveDecomposableSystem. If the equations are in a list F, the command solveDecomposableSystem(F) will compute a list of solutions to F.

Timing

The example above was used to compare timings of our software against the polyhedral homotopy software PHC. Solutions to 10962 instances of such sparse systems for various choices of $𝒾$ and $𝒿$ were computed with both softwares and timings were recorded against the total number of solutions to each instance. A comparison of the timings are reported in the figure to the right.