Image Missing!
Software for Decomposable Sparse Polynomial Systems

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

Picture MissingDecomposable 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.


For a system of polynomial equations F=(F1,..,Fn), the support of F is the collection of n integer matrices whose columns are the exponent vectors appearing in each polynomial Fi. Let A1 = ( 0 1 2 0 1 0 0 0 1 1 ) , A2 = ( 1 0 1 2 1 0 1 1 1 2 ) , B1 = ( 0 2 0 2 0 0 1 3 ) , and B2 = ( 0 1 2 0 2 0 0 0 0 1 1 2 ). We consider the columns of these matrices as exponent vectors in this way and display their convex hulls below.

Missing Image
Missing Image
Missing Image
Missing Image

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

A (𝒾⁢,⁢𝒿) = ( 𝒾(A1), 𝒾(A2), 𝒿(B1), 𝒿(B2), C ).

Any sparse system with support A(𝒾⁢,⁢𝒿) 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.

Image Missing!