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.
For a system of polynomial equations the support of is the collection of integer matrices whose columns are the exponent vectors appearing in each polynomial Let , , , and We consider the columns of these matrices as exponent vectors in this way and display their convex hulls below.
Let be the vertices of the five-dimensional cube. We construct sparse decomposable systems from , , and as follows. Choose two embeddings and such that For example, choose four linearly independent vectors and define and the same for These embeddings correspond to monomial maps. For example, the embedding corresonponding to the vectors and corresponds to the monomial map on sending and For any matrix the image is the set of exponent vectors that appear by precomposing a polynomial supported on with the monomial map associated to Set
Any sparse system with support 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.
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.