Computing Implicitizations of Multi-Graded Polynomial Maps
Abstract: In this paper, we focus on computing the kernel of a map of polynomial rings \(\varphi\). This core problem in symbolic computation is known as implicitization. While there are extremely effective Gröbner basis methods used to solve this problem, these methods can become infeasible as the number of variables increases. In the case when the map \(\varphi\) is multigraded, we consider an alternative approach. We demonstrate how to quickly compute a matrix of maximal rank for which \(\varphi\) has a positive multigrading. Then in each graded component we compute the minimal generators of the kernel in that multidegree with linear algebra. We have implemented our techniques in Macaulay2 and show that our implementation can compute many generators of low degree in examples where Gröbner techniques have failed. This includes several examples coming from phylogenetics where even a complete list of quadrics and cubics were unknown. When the multigrading refines total degree, our algorithm is embarassingly parallel and a fully parallelized version of our algorithm will be forthcoming in OSCAR.
This page contains our \(\verb|Macaulay2|\) package \(\verb|MultigradedImplicitization.m2|\) which can be downloaded here
as well as supplementary material for the computations performed in the article. To use the package simply start Macaulay2 in a directory containing the package and load it as demonstrated below.
needsPackage "MultigradedImplicitization"
A = matrix {{1,1,1,0,0,0,0,0,0}, {0,0,0,1,1,1,0,0,0}, {0,0,0,0,0,0,1,1,1}, {1,0,0,1,0,0,1,0,0}, {0,1,0,0,1,0,0,1,0}};
R = QQ[x_1..x_(numcols A)];
S = QQ[t_1..t_(numrows A)];
F = map(S, R, apply(numcols(A), i -> S_(flatten entries A_i)));
dom = newRing(R, Degrees => A);
G = componentsOfKernel(2,F);
The package is completely documented with several examples on how to use it included within. To view the documentation simply type \(\verb|viewHelp MultigradedImplicitization|\) after loading the package.
Supplementary Material
In the last section of our paper we apply our main algorithm to several difficult implicitization problems which come from phylogenetics. For most examples, it has thus far been impossible to even compute all quadratic or cubic generators with standard Gröbner basis algorithms. In the \(\verb|Macaulay2|\) files which can be found below, there is a straightforward implementation for each of the phylogenetic models discussed in our paper. We then simply ran our main algorithm on them to find generators of the kernel.
The General Markov Model
One well known implicitization problem is the Salmon Problem which was formulated by Elizabeth Allman and received significant follow up work. This problem is to find a generating set for the ideal of phylogenetic invariants for the 4-state general Markov model on a 3 leaf tree. Equivalently, it is to find a generating set for the vanishing ideal of \(\mathrm{Sec}^4(\mathbb{P}^3 \times \mathbb{P}^3 \times \mathbb{P}^3)\). A conjectural set of generators is known which has been shown to cut out the ideal set theoretically. In this problem, the ring map which parameterizes the model maps from a ring with 64 variables into a ring with 52 variables though this can be reduced slightly. While our current \(\verb|Macaulay2|\) implementation is unable to solve this problem currently, we are able to solve the equivalent problem for the general Markov model with 3 states which corresponds to the vanishing ideal of \(\mathrm{Sec}^3(\mathbb{P}^2 \times \mathbb{P}^2 \times \mathbb{P}^2)\)
The K3P Model on a Phylogenetic Network
Our second interesting example is the Kimura 3-Parameter model on a phylogenetic network. Previous attempts to compute the invariants of a 4 leaf network with Gröbner bases have had limited success. In particular, they were unable to compute the cubic invariants even after 100 days. The parameterization \(\varphi_n\) for an \(n\) leaf sunlet network has \(4^{n-1}\) variables in the domain and \(6n+1\) variables in the codomain. In the file below we provide a simple function which creates the parameterization of the model. We then run our algorithm on the parameterization. The file below takes approximately 8 minutes to compute all invariants of total degree at most 3. One may also change the number of leaves \(n\) or the total degree \(d\) in the file below to compute invariants for networks with more leaves or higher total degree though this of course takes longer.
The TN93 Model on a 4-Leaf Tree
Our third example is the Timura-Nei model on a 4 leaf tree. This model is no longer group-based, but it is time-reversible. For a tree \(T\) with \(n\) leaves, the vanishing ideal under the TN93 model is as of yet unknown; however, it has been shown for a 4 leaf tree that on an open subset of a statistical significance, the ideal is a complete intersection of dimension 16 generated by polynomials of degree at most 4. The file below finishes in approximately 30 seconds and computes all 375 minimal quadrics in the ideal. In particular, the full ideal is not a complete intersection. One could also try to find the minimal cubics and quartics; however, the computation is significantly slowed down since we are working over the fraction field \(\mathbb{C}(\pi_1,\pi_2,\pi_3,\pi_4)\). The code below can be used to compute these invariants. The first file was produced by Marta Casanellas, Roser Homs Pons, Angélica Torres and is input which is used to construct the model in the second file.
Additionally, all of the above code can be found in the following zip file.