# Solving sparse polynomial systems using Gröbner bases and resultants

Matías R. Bender  Technische Universität BerlinBerlinGermany<EMAIL_ADDRESS>berlin.de 0000-0001-9341-287X

(2022)

###### Abstract.

Solving systems of polynomial equations is a central problem in nonlinear and
computational algebra. Since Buchberger’s algorithm for computing Gröbner
bases in the 60s, there has been a lot of progress in this domain. Moreover,
these equations have been employed to model and solve problems from diverse
disciplines such as biology, cryptography, and robotics. Currently, we have a
good understanding of how to solve generic systems from a theoretical and
algorithmic point of view. However, polynomial equations encountered in
practice are usually structured, and so many properties and results about
generic systems do not apply to them. For this reason, a common trend in the
last decades has been to develop mathematical and algorithmic frameworks to
exploit specific structures of systems of polynomials.

Arguably, the most common structure is sparsity; that is, the polynomials of
the systems only involve a few monomials. Since Bernstein, Khovanskii, and
Kushnirenko’s work on the expected number of solutions of sparse systems,
toric geometry has been the default mathematical framework to employ sparsity.
In particular, it is the crux of the matter behind the extension of classical
tools to systems, such as resultant computations, homotopy continuation
methods, and most recently, Gröbner bases. In this work, we will review these
classical tools, their extensions, and recent progress in exploiting sparsity
for solving polynomial systems.

This manuscript complements its homonymous tutorial presented at the
conference ISSAC 2022.

Sparse polynomials, Gröbner bases, resultants, solving polynomial systems

††journalyear: 2022††copyright: acmlicensed††conference: Proceedings of the
2022 International Symposium on Symbolic and Algebraic Computation; July 4–7,
2022; Villeneuve-d’Ascq, France††booktitle: Proceedings of the 2022
International Symposium on Symbolic and Algebraic Computation (ISSAC ’22),
July 4–7, 2022, Villeneuve-d’Ascq, France††price: 15.00††doi:
10.1145/3476446.3535498††isbn: 978-1-4503-8688-3/22/07††ccs: Computing
methodologies Symbolic and algebraic algorithms††ccs: Computing methodologies
Hybrid symbolic-numeric methods††ccs: Computing methodologies Symbolic
calculus algorithms††ccs: Computing methodologies Equation and inequality
solving algorithms

_Dedicated to the memory of Agnes Szanto_

##  1\. Introduction

Systems of polynomial equations give us one of the simplest and general ways
of dealing with non-linear objects. They are expressive enough to encode
algebraic varieties and effective enough to allow us to compute with them.
They generalize two ubiquitous kinds of equations appearing in Mathematics,
linear equations and univariate polynomials. Solving polynomial equations,
that is, to find exact or approximate solutions for the equations of the
systems, is one of the central problems in this setting and their applications
span several domains in science and engineering (Cox et al., 2020; Breiding et
al., 2021).

There are several tools to solve polynomial systems, e.g., geometric
resolutions (Heintz et al., 2000; Giusti et al., 2001; Herrero et al., 2013),
Gröbner bases (Faugère et al., 1993; Faugére, 1999)(Kreuzer and Robbiano,
2000, Chp. 2), homotopy continuation (Morgan and Sommese, 1987; Huber and
Sturmfels, 1995; Bürgisser and Cucker, 2013), normal form algorithms (Lazard,
1981; Auzinger and Stetter, 1988; Mourrain, 1999; Telen, 2020b), resultants
(Canny, 1990; Emiris and Rege, 1994)(Cox et al., 2005, Chp. 3), subdivisions
(Cucker et al., 2008; Mourrain and Pavone, 2009; Tonelli-Cueto, 2019),
subresultants (González-Vega, 1991; Szanto, 2008; Diochnos et al., 2009) and
triangular decompositions (Chen and Maza, 2012; Wang et al., 2020). The
aforementioned is a non-exhaustive list of methods and references; the
interested reader can find the latest developments on many of these methods in
the proceedings of the previous editions of ISSAC. Some nice introductions to
the theory of solving systems of polynomial equations can be found in (Kreuzer
and Robbiano, 2000; Cox et al., 2005; Dickenstein and Emiris, 2005). In this
manuscript, and in its associated tutorial, we focus on Gröbner bases,
resultants, and normal forms algorithms.

In practice, the polynomial systems that we encounter are structured, e.g.,
sparse polynomials in biology (Gatermann and Huber, 2002) and statistics
(Drton et al., 2009), symmetric in cryptography (Faugère et al., 201), and
determinantal in optimization (Huber and Verschelde, 2000). However, the
general-purpose strategies to solve polynomial systems does not exploit this
structure. For this reason, in the last years, an important trend in
polynomial system solving is to improve these techniques for specific
structures. In this text, we will focus on the sparsity of the inputs. Besides
sparsity, other kinds of structures include, e.g., symmetry (Faugère and
Svartz, 2013; Bazan and Hubert, 2020), determinantal (Faugère et al., 201;
Labahn et al., 2021), black box evaluations (Bürgisser et al., 2020), and
degenerations (Burr et al., 2022).

###  1.1. Sparsity

Sparsity is arguably the most common structure appearing in practice. Before
giving the definition of sparsity, let us introduce some notation.

##### Notation

Given $\alpha\in\mathbb{Z}^{n}$, we define
$\bm{x}^{\alpha}:=\prod_{i=1}^{n}x_{i}^{\alpha_{i}}$. The monomials
$\\{\bm{x}^{\alpha}:\alpha\in\mathbb{Z}^{n}\\}$ generate the
$\mathbb{C}$-algebra of _Laurent polynomials_
$\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}]$. We will write our polynomials in
$\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}]$ as a sum of terms, i.e.,
$\sum_{\alpha\in\mathbb{N}^{n}}c_{\alpha}x^{\alpha}$, where
$c_{\alpha}\in\mathbb{C}$ is the coefficient of the monomial $\bm{x}^{\alpha}$
and there are finite $\alpha\in\mathbb{Z}^{n}$ such that $c_{\alpha}\neq 0$.
The _support_ of a given polynomial $f$ is the finite set of exponents with
non-zero coefficients, i.e.,

$\mathtt{Supp}\left(\sum_{\alpha\in\mathbb{N}^{n}}c_{\alpha}\bm{x}^{\alpha}\right):=\\{\alpha\in\mathbb{Z}^{n}:c_{\alpha}\neq
0\\}.$

We abuse notation and we also identify $\mathtt{Supp}(f)$ with a set of the
monomials with exponents in $\mathtt{Supp}(f)$. In this text, we will only
work with rational polytopes, i.e., its vertices are integer points. Given two
polytopes $P_{1}$ and $P_{2}$, we define its Minkowski sum $P_{1}+P_{2}$ as
their point-wise addition, i.e., $P_{1}+P_{2}:=\\{\alpha+\beta:\alpha\in
P_{1},\beta\in P_{2}\\}$. For each $i\in\mathbb{N}$, let $i\,P:=P+(i-1)\,P$,
and $0\,P=\\{0\\}$. We denote by $\Delta_{n}$ the $n$-dimensional standard
simplex, i.e., the convex hull of
$\\{0,e_{1},\dots,e_{n}\\}\\!\subset\\!\mathbb{R}^{n}$, where
$\\{e_{1},\dots,e_{n}\\}$ is the canonical basis of $\mathbb{R}^{n}$.

Intuitively, a polynomial $f\in\mathbb{C}[x_{1},\dots,x_{n}]$ is sparse when
$\mathtt{Supp}(f)$ is _small_ , e.g., $\mathtt{Supp}(f)$ has less elements
than $\mathtt{Supp}(g)$, where $g\in\mathbb{C}[x_{1},\dots,x_{n}]$ is a
generic polynomial of the same degree as $f$. However, in this text we will
use a related, but different, notion of sparsity given by the _Newton
polytope_ of the polynomial.

###### Definition 1.1 (Newton polytope).

Given a polynomial $f$, its _Newton polytope_
$\mathtt{NP}(f)\subset\mathbb{R}^{n}$ is the convex hull of $\mathtt{Supp}(f)$
over $\mathbb{R}^{n}$.

Observe that the Newton polytope of a generic polynomial in
$\mathbb{C}[x_{1},\dots,x_{n}]$ of degree $d$ is $d\,\Delta_{n}$, i.e., the
$d$-dilation of the $n$-dimensional standard simplex.

###### Example 1.2 (Generalized eigenvalue problem).

For most generalized eigenvalue problems in $\mathbb{C}^{2\times 2}$, we can
represent them as a system of polynomial equations in two variables
$\lambda,w$, where $(1,\lambda)$ denotes the generalized eigenvalue and
$v:=(1,w)$, the eigenvector. For example, for the pencil $(A,B)$,
$A:=\big{(}\begin{smallmatrix}1&2\\\ 3&4\end{smallmatrix}\big{)}$,
$B:=\big{(}\begin{smallmatrix}3&4\\\ -2&-4\end{smallmatrix}\big{)}$, we obtain
the polynomial system $f_{1}=f_{2}=0$,

$\displaystyle(A+\lambda\,B)\,v=0\iff\left\\{\begin{array}[]{c}f_{1}:=1+3\,\lambda+2\,w+4\,\lambda\,w=0\\\
f_{2}:=3-2\,\lambda+4\,w-4\,\lambda\,w=0\end{array}\right..$

The polynomials have degree 2 and their support are
$\mathtt{Supp}(f_{1})=\mathtt{Supp}(f_{2})=\\{1,\lambda,w,\lambda\,w\\}$. The
polynomials are sparse; written in terms of monomials of degree at most 2, we
have that

$f_{1}=\bm{1}+\bm{3}\,\lambda+\bm{0}\,\lambda^{2}+\bm{2}\,w+\bm{0}\,w^{2}+\bm{4}\,\lambda\,w.$

The gray square in the following picture is their Newton polytope.

$w^{2}$$w$$1$$\lambda\,w$$\lambda$$\lambda^{2}$

When we talk about sparsity, we look at Newton polytopes and not at the
supports because of the next theorem, attributed to Bernstein (Bernshtein,
1975), Khovanskii (Khovanskii, 1978), and Kushnirenko (Kushnirenko, 1976).

###### Theorem 1.3 (BBK bound).

Fix a polynomial system $(f_{1},\dots,f_{n})$ with a finite number of
solutions over $(\mathbb{C}^{*})^{n}$, where
$\mathbb{C}^{*}:=\mathbb{C}\setminus\\{0\\}$. Then, this number of solutions
is upper bounded by the _mixed volume_ of
$\mathtt{NP}(f_{1}),\dots,\mathtt{NP}(f_{n})$, i.e.,
$\mathtt{MV}(\mathtt{NP}(f_{1}),\dots,\mathtt{NP}(f_{n}))$, where

$\mathtt{MV}(P_{1},\dots,P_{n}):=(-1)^{n}+\sum_{k=1}^{n}(-1)^{n-k}\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}I\subset\\{1,\dots,n\\}\\\
\\#I=k\end{subarray}}\\!\\!\\!\\!\\!\\!\\#\left((P_{I_{1}}+\dots+P_{I_{k}})\cap\mathbb{Z}^{n}\right)$

Moreover, consider finite subsets $A_{1},\dots,A_{n}\subset\mathbb{Z}^{n}$ and
a system of generic polynomials $(f_{1},\dots,f_{n})$ supported on
$A_{1},\dots,A_{n}$, i.e., each $f_{i}=\sum_{\alpha\in
A_{i}}c_{i,\alpha}\bm{x}^{\alpha}$, where
$(c_{i,\alpha})_{i\in\\{1,\dots,n\\},\alpha\in A_{i}}$ is a generic vector.
Then, the aforementioned bound for this generic system is an equality.

For a proof and extensions of this theorem, see (Mondal, 2021). The generic
conditions of the previous theorem can be relaxed (Canny and Rojas, 1991;
Chen, 2019; Bihan and Soprunov, 2019).

###### Example 1.4 (Cont. Ex. 1.2).

Without considering the sparsity of the input, Bézout’s theorem tells us that
the system should have (at most) $2^{2}$ solutions. However, it has only two,
each corresponding to a different eigenspace. This number agrees with the
mixed volume of the Newton polytopes defining the equations.

When working with sparse polynomials, we usually consider two class of
systems. We say that a sparse polynomial system $(f_{1},\dots,f_{r})$ is
_unmixed_ when there is an integer polytope $P\subset\mathbb{R}^{n}$ and
integers $d_{1},\dots,d_{r}$ such that $\mathtt{NP}(f_{i})=d_{i}\,P$, i.e.,
each Newton polytope is a dilation of a common integer polytope. Otherwise,
the system is _mixed_.

In this manuscript, we will discuss Gröbner bases and resultants in the
context of sparse polynomials. We will employ the Newton polytopes of the
input polynomials to speed up the computations and derive complexity bounds
for our algorithms depending on the sparsity pattern of the inputs. These
techniques rely on _toric geometry_. Toric geometry was also employed to solve
sparse polynomial systems using other techniques such as homotopy continuation
(Huber and Sturmfels, 1995; Malajovich, 2019; Ergür and de Wolff, 2021) or
geometric resolutions (Herrero et al., 2013).

###### Remark 1.5 (Other notions of sparsity).

As the BKK bound shows, from a complex point of view, the solutions of the
sparse systems are “determined” by the Newton polytopes of the input
polynomials and not by their supports. However, from a real point of view, the
support matters. In real algebraic geometry, a polynomial whose support is
small is called a _fewnomial_. Khovanskii showed that the number of positive
real solutions of a fewnomial system is upper bounded by a quantity singly
exponential in the size of the supports of the fewnomials (Khovanskii, 1991).
Determining the number of real solutions of a fewnomial system is an active
area of research. For example, the bounds were improved for general (Bihan and
Sottile, 2007) and particular systems (Bihan and Dickenstein, 2017). Moreover,
probabilistically, stronger bounds hold (Bürgisser et al., 2019; Jindal et
al., 2020).

A different kind of sparsity that has been studied is the _chordal structure_.
This structure only cares about the variables appearing in each polynomial,
regardless of the specific monomials. There are dedicated algorithms to
compute Gröbner bases (Cifuentes and Parrilo, 2016) and triangular sets (Mou
et al., 2021) that exploit this notion.

###  1.2. Multiplication maps

An intermediate tool used to solve polynomial systems using the Gröbner bases
and resultants is multiplication maps. To define them, let
$\bm{f}:=\\{f_{1},\dots,f_{r}\\}\subset\mathbb{C}[x_{1},\dots,x_{n}]$ be an
affine polynomial system with a finite number of solutions $\delta$ over
$\mathbb{C}^{n}$, counting multiplicities. The quotient ring
$\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$ is a finite dimensional
$\mathbb{C}$-vector space whose dimension is $\delta$ (Cox et al., 2005, Chp.
4.2), so we will fix a basis $b_{1},\dots,b_{\delta}$ to identify
$\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$ with
$\mathbb{C}^{\delta}$. Given
$g\in\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$, the _multiplication
map_ of $g$ is the morphism

$\displaystyle M_{g}:\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$
$\displaystyle\rightarrow\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$
$\displaystyle h$ $\displaystyle\mapsto M_{g}(h):=g\,h.$

Using the basis $\\{b_{1},\dots,b_{\delta}\\}$, we think about $M_{g}$ as a
matrix, which we call the _multiplication matrix_. Multiplication matrices are
ubiquitous in algorithms for solving polynomial systems:

  * •

On one hand, we can approximate the solutions by computing the eigenvalues of
these maps. More precisely, the _eigenvalue theorem_ (Lazard, 1981) states
that the eigenvalues of $M_{g}$ correspond to the evaluations111The evaluation
of $g\in\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$ at a point
$p\in\mathbb{C}^{n}$ corresponds to $\bar{g}(p)$, where
$\bar{g}\in\mathbb{C}[x_{1},\dots,x_{n}]$ is such that $\bar{g}$ belongs to
the class of $g$ in $\mathbb{C}[x_{1},\dots,x_{n}]/\langle\bm{f}\rangle$. of
$g$ at the $\delta$ solutions of the system $(f_{1},\dots,f_{r})$. See (Cox,
2021) for more details on this theorem and its history. Moreover, for each
solution $p$ of $\bm{f}$, the vector given by the evaluations
$(b_{i}(p))_{i\leq\delta}$ belongs to the eigenspace of $M_{g}$ of eigenvalue
$g(p)$ (Auzinger and Stetter, 1988).

  * •

On the other hand, multiplication maps are a standard tool to compute Gröbner
bases for zero-dimension ideals. The algorithm FGLM (Faugère et al., 1993;
Faugère and Mou, 2017) allows us to derive, from the multiplication matrices,
Gröbner bases of $\langle\bm{f}\rangle$ with respect to any monomial order,
e.g., lexicographical, or to find a rational univariate representation of the
solutions (Rouillier, 1999).

To compute multiplication matrices, we use a _normal form_ , which is, roughly
speaking, a homomorphism
$\mathbb{C}[x_{1},\dots,x_{n}]\rightarrow\mathbb{C}^{\delta}$ whose kernel is
$\langle\bm{f}\rangle$. We can obtain such normal forms using, for example,
Gröbner bases (Kreuzer and Robbiano, 2000, Chp. 2), border bases (Mourrain,
1999)(Dickenstein and Emiris, 2005, Chp. 4), or Sylvester formulas for the
resultant (Auzinger and Stetter, 1988; Telen et al., 2018; Telen, 2020b). We
can compute these matrices by performing $d^{O(n)}$ arithmetic operations,
where $d$ is the maximal among the degrees of the polynomials in $\bm{f}$
(Lakshman and Lazard, 1991).

The aforementioned strategies do not employ the sparsity of the inputs to
speed up the computations (at least directly222Heuristically, implementations
of the F4 algorithm to compute Gröbner bases (Faugére, 1999) can benefit
partially from the sparsity of the inputs; see, e.g., (Monagan and Pearce,
2017; Berthomieu et al., 2021).). Moreover, their complexity bounds are
independent of this structure and to achieve them, we must destroy the
sparsity of the inputs, i.e., to perform random linear change of coordinates
or to consider random combinations of the input polynomials. In the following
sections, we discuss alternative approaches to avoid these issues.

##  2\. The sparse resultant

In this section, we will assume that the reader is familiar with the classical
(projective) resultant. We refer to (Cox et al., 2005, Chp. 3) and (Busé,
2006) for an introduction.

The sparse resultant is a generalization of the classical resultant that allow
us to decide if a sparse affine polynomial system in $n$ variables given by
$n+1$ polynomials has a common solution in $(\mathbb{C}^{*})^{n}$. It is one
of the first available tools to solve sparse polynomial systems and a subject
of study since the 90’s.

Given finite sets $A_{0},\dots,A_{n}\subset\mathbb{Z}^{n}$, we can
parameterize each different polynomial system supported in
$\bm{A}:=(A_{0},\dots,A_{n})$ with points333We identify the systems using the
multi-projective space because multiplying the polynomials by non-zero
constants does not change their solution set. in
$\mathbb{P}^{\bm{A}}:=\mathbb{P}^{\\#A_{0}-1}\times\dots\times\mathbb{P}^{\\#A_{n}-1}$,

$(\bm{c_{0}},\dots,\bm{c_{n}})\in\mathbb{P}^{A_{0}}\times\dots\times\mathbb{P}^{A_{n}}\mapsto\left(\sum_{\alpha\in
A_{0}}c_{0,\alpha}x^{\alpha},\dots,\sum_{\alpha\in
A_{n}}c_{n,\alpha}x^{\alpha}\right).$

We use the _incidence variety_ $\Omega$ to characterize all the sparse systems
of polynomials supported on $A_{0},\dots,A_{n}$ with solutions in
$(\mathbb{C}^{*})^{n}$.

$\Omega:=\\{(p,(F_{0},\dots,F_{n}))\in(\mathbb{C}^{*})^{n}\times\mathbb{P}^{\bm{A}}:(\forall
i)\,F_{i}(p)=0\\},$

If we consider the projection map
$\pi:(\mathbb{C}^{*})^{n}\times\mathbb{P}^{\bm{A}}\rightarrow\mathbb{P}^{\bm{A}}$,
$\pi(\Omega)\subset\mathbb{P}^{\bm{A}}$ determines the systems with solutions
at $(\mathbb{C}^{*})^{n}$. However, as $\pi(\Omega)$ is not an algebraic
variety, we consider its algebraic closure $\overline{\pi(\Omega)}$ in
$\mathbb{P}^{\bm{A}}$. Under combinatorial assumptions on $\bm{A}$ (Sturmfels,
1994, Cor. 1.1), $\overline{\pi(\Omega)}$ has co-dimension $1$ on
$\mathbb{P}^{\bm{A}}$ and it is an irreducible hypersurface defined by a
multihomogeneous polynomial $\mathtt{Res}_{\bm{A}}$ called the _sparse
resultant_ of $\bm{A}$444We follow Esterov’s (Esterov, 2010) and D’Andrea &
Sombra’s (D’Andrea and Sombra, 2015) definition of the sparse resultant. That
is, the polynomial $\mathtt{Res}_{\bm{A}}$ might not be irreducible, but it is
the $d$-power of an irreducible polynomial, the _eliminant_ , where $d$ is the
degree of $\pi$ restricted to $\Omega$; see (D’Andrea and Sombra, 2015, Sec.
2). Classically (Gelfand et al., 2008; Sturmfels, 1994), the sparse resultant
was defined as the eliminant. . For each $i$, the sparse resultant
$\mathtt{Res}_{\bm{A}}$ is homogeneous with respect to the coefficients of the
polynomial $F_{i}$ supported in $A_{i}$ and its degree is
$\mathtt{MV}(P_{0},\dots,P_{i-1},P_{i+1},\dots,P_{n})$, where $P_{i}$ is the
convex hull of $A_{i}$. The sparse resultant is a generalization of the
classical (projective) resultant. More precisely, if we have that
$A_{i}=d_{i}\Delta_{n}\cap\mathbb{Z}^{n}$, for some $d_{i}\in\mathbb{N}$, for
each $i$, the sparse and classical resultant agree. The interested reader can
find more properties of the sparse resultant in, e.g., (Cox et al., 2005, Chp.
7),(Gelfand et al., 2008, Chp. 8), (Sturmfels, 1994; D’Andrea and Sombra,
2015).

###  2.1. Vanishing of the sparse resultant

As the classical resultant is a special case of the sparse resultant, it is
easy to verify that having solutions on the torus $(\mathbb{C}^{*})^{n}$ is a
necessary but not sufficient condition for the vanishing of the sparse
resultant. To understand when this vanishes, let us recall when the classical
(projective) resultant vanishes. Given an affine polynomial
$f\in\mathbb{C}[x_{1},\dots,x_{n}]$, we define its classical _homogenization_
, $f^{h}\in\mathbb{C}[x_{0},x_{1},\dots,x_{n}]$, as the polynomial
$f^{h}=x_{0}^{\mathtt{deg}(f)}\,f\left(\frac{x_{1}}{x_{0}},\dots,\frac{x_{n}}{x_{0}}\right)$.
Given an affine polynomial system
$f_{0},\dots,f_{n}\in\mathbb{C}[x_{1},\dots,x_{n}]$, the classical resultant
of $(f_{0},\dots,f_{n})$ will vanish if and only if the _homogenization_ of
the system, i.e.
$f_{0}^{h},\dots,f_{n}^{h}\in\mathbb{C}[x_{0},x_{1},\dots,x_{n}]$, has a
common solution on $\mathbb{P}^{n}$. The homogenization does not change the
solutions of the original system on $\mathbb{C}^{n}$, i.e., for
$p\in\mathbb{C}^{n}$, if $f(p_{1},\dots,p_{n})=0$, then
$f^{h}(1,p_{1},\dots,p_{n})=0$. However, it might introduce new solutions _at
infinity_ , i.e.,
$\mathbb{P}^{n}\setminus\mathbb{C}^{n}:=\\{[p_{0}:\dots:p_{n}]\in\mathbb{P}^{n}:p_{0}=0\\}$.
In an analogous way, the sparse resultant $\mathtt{Res}_{\bm{A}}$ of a sparse
system will vanish if and only if a homogenization of the system vanishes over
a normal projective toric variety ${X}$. This toric variety is a compact
variety containing $(\mathbb{C}^{*})^{n}$ which is constructed from the
Minkowski sum $P:=\sum_{i}P_{i}$; see, e.g., (Cox et al., 2011, Chp. 2.3) for
more details on this construction. As in the classical setting, the
homogenization of the system has the same solutions as the original system
over $(\mathbb{C}^{*})^{n}$, but might have extra zeros on
$X\setminus(\mathbb{C}^{*})^{n}$, which we will call _zeros at infinity_. More
precisely, for each $P_{i}$, we can find a torus-invariant nef Cartier divisor
$D_{i}$ such that the global sections of its associated line bundle, denoted
by $O_{X}(D_{i})$, can be identified with the sparse polynomials whose Newton
polytope is equal to (or contained in) $P_{i}$ (Cox et al., 2011, Chp. 6),
that is,

(1) $\displaystyle
H^{0}(X_{P},O_{X}(D_{i}))=\\{g\in\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}]:\mathtt{NP}(g)\subseteq
P_{i}\\}.$

This identification corresponds to the homogenization. Somehow, if we have a
global section $s\in H^{0}(X_{P},O_{X}(D))$ identified with
$g:=\sum_{\alpha\in Q}c_{\alpha}x^{\alpha}$, then for every
$p\in(\mathbb{C}^{*})^{n}$, $s(p)=0$ if and only if $g(p)=0$. Using this
intuition, we consider the incidence variety

$\Omega^{h}:=\\{(p,(F_{0},\dots,F_{n}))\in
X_{\bm{P}}\times\mathbb{P}^{\bm{A}}:(\forall i)\,\mathtt{hom}(F_{i})(p)=0\\},$

where $\mathtt{hom}(F_{i})$ denotes the global section of $O_{X}(D)$
identified with $F_{i}$. If $\pi$ now denotes the projection onto
$\mathbb{P}^{\bm{A}}$, $\pi(\Omega^{h})$ is an algebraic variety (because $X$
is projective) which we can prove agrees with $\overline{\pi(\Omega)}$. We
refer the interested reader to (Cox et al., 2005, Chp. 7.3) for a more
detailed explanation in the case of unmixed systems555Beware that the toric
variety constructed in (Cox et al., 2005, Chp. 7.3) and $X$ might not agree
($X$ is its normalization; see (Cox et al., 2011, Chp. 3.A)), but the argument
extends to $X$..

###### Remark 2.1.

To define a homogenization in terms of coordinates, as we did over
$\mathbb{P}^{n}$, we need to introduce a coordinate ring for $X$. However,
such a ring depends on the way (embedding) that we use to think about $X$. For
example, we can think about $X$ as an _almost geometric quotient_ and use its
associated ring, the Cox ring (Cox, 1995), to homogenize the polynomials; see
(Cox et al., 2011, Chp. 5). Alternatively, we can use the so-called Cayley
trick (Gelfand et al., 2008, Chp. 8), where we choose nef line bundles on $X$
associated to each $P_{i}$ and consider the embedding of $X$ on the (weighted)
multi-projective space defined by them. We will use the latter approach in
Sec. 3.

###  2.2. Computing the sparse resultant

####  2.2.1. The determinant of a matrix

A classical way of computing the resultant is a factor of the determinant of a
matrix. Sylvester (Sylvester, 1840) showed that we can compute the resultant
of two univariate polynomials $f_{0},f_{1}\in\mathbb{C}[x_{0},x_{1}]$ by
considering the determinant of the Sylvester matrix, which linearizes the
(Sylvester) map $(g_{0},g_{1})\mapsto g_{0}\,f_{0}+g_{1}\,f_{1}$, where
$g_{0}$ is a polynomial of degree at most $\deg(f_{1})-1$ and $g_{1}$ a
polynomial of degree at most $\deg(f_{0})-1$. This construction was later
generalized by Macaulay (Macaulay, 1916), who showed how to compute the
classical (projective) resultant of $n+1$ polynomials
$f_{0},\dots,f_{n}\in\mathbb{C}[x_{1},\dots,x_{n}]$ of degree
$d_{0},\dots,d_{n}$. He also showed that there is a way of constructing
monomial sets $B_{0},\dots,B_{n}$ such that each $x^{\beta}\in B_{i}$ has
degree at most $\sum_{j\neq i}d_{j}-n$ and $\sum_{i}\\#B_{i}$ agrees with the
number of monomials of degree at most $\sum_{j}d_{j}-n$ in
$\mathbb{C}[x_{1},\dots,x_{n}]$. With these considerations, we can construct
the _Macaulay matrix_ $M$, whose columns we index with monomials in
$\mathbb{C}[x_{0},\dots,x_{n}]$ of degree at most $\sum_{j}d_{j}-n$ and the
rows with pairs $\\{(i,x^{\beta}):i\in\\{0,\dots,n\\},x^{\beta}\in B_{i}\\}$.
The element in $M$ associated with the column indexed by $x^{\alpha}$ and row
indexed by $(i,x^{\beta})$ corresponds to the coefficient of the monomial
$x^{\alpha}$ in $x^{\beta}\,f_{i}$. Macaulay proved that the resultant of
$(f_{0},\dots,f_{n})$ is a factor of the determinant of $M$, i.e.,
$\det(M)=\mathtt{Res}(f_{0},\dots,f_{n})\cdot E$. Moreover, he showed that the
polynomial $E$, usually called the _extra factor_ , is a specific minor of
$M$. Observe that the matrix $M$ is the transpose of a matrix representing the
Sylvester map $(g_{0},\dots,g_{n})\mapsto\sum_{i}f_{i}\,g_{i}$, where the
support of each $g_{i}$ is contained in $B_{i}$. For this reason, we say that
his construction is a _Sylvester formula_ for the resultant. Besides Sylvester
formulas, we observe that other maps can be used to compute resultants. We
refer the reader to (Emiris and Mourrain, 1999) and references therein.

Canny and Emiris (Canny and Emiris, 1993) generalized Macaulay’s construction
to the sparse case. They presented a Sylvester formula for the resultant
constructed out of mixed subdivisions of the Newton polytopes of the input
polynomials. The interested reader can find more details and references in
(Cox et al., 2005, Chp. 7.6). However, Canny and Emiris did not characterize
the extra factor appearing in their constructions. Different authors studied
this question, e.g., (D’Andrea, 2002; Groh, 2020; D’Andrea et al., 2022), and
very recently D’Andrea, Jeronimo, and Sombra (D’Andrea et al., 2022) presented
a complete characterization of the extra factor which allowed them to recover
Macaulay’s original results.

####  2.2.2. The determinant of a complex

A more general and elaborated way of computing the resultant is as the
determinant of a complex of vector spaces. This approach is attributed to
Cayley and was extended to study general kinds of resultants, such as the
sparse one; the interested reader can find more details in (Gelfand et al.,
2008, Chp. 3.4). It turns out that the aforementioned Sylvester maps are just
the last maps appearing in certain Koszul complexes that we can use to compute
resultants; see, e.g., (Gelfand et al., 2008, Chp. 13). Moreover, we can use
other kinds of complexes to construct smaller matrices from which to compute
the resultant. In the best case scenario, the complex will involve only two
non-zero modules and so its determinant will agree with the determinant of the
maps between these modules. In this case, we will be able to construct
_determinantal formulas_ , that is, maps whose determinant is exactly the
resultant, i.e., the extra factor $E$ is a non-zero constant independent of
the specific system.

Following (Gelfand et al., 2008), to construct the resultant as the
determinant of a complex, we use sheaf cohomology. Let $X$ be the normal
projective toric variety constructed from the polytope $P$ detailed before and
consider the nef line bundles $O_{X}(D_{0}),\dots,O_{X}(D_{n})$. Consider
global sections $\tilde{f}_{0},\dots,\tilde{f}_{n}$ such that
$\tilde{f}_{i}\in H^{0}(X,O_{X}(D_{i}))$. If
$(\tilde{f}_{0},\dots,\tilde{f}_{n})$ has no common zeros on $X$, the Koszul
complex of sheaves $\mathcal{K}_{\bullet}$ associated with the Sylvester map,
defined locally at $U\subset X$ as
$\mathtt{Sylv}(g_{0},\dots,g_{n})\mapsto\sum_{i}g_{i}\,\tilde{f}_{i}\\!\mid_{U}$,
is exact;

(2) $\mathcal{K_{\bullet}}:0\rightarrow
O_{X}(-\sum_{i}D_{i})\rightarrow\bigoplus_{i}O_{X}(-\sum_{j\neq
i}D_{j})\rightarrow\dots{\\\ }\dots\rightarrow\bigoplus_{j\neq
i}O_{X}(-D_{i}-D_{j})\rightarrow\bigoplus_{j}O_{X}(-D_{j})\xrightarrow{\mathtt{Sylv}}O_{X}\rightarrow
0,$

where $O_{X}(D-B)=O_{X}(D)\otimes O_{X}(B)^{-1}$, for any two Cartier divisors
$D$ and $B$. We will transform this complex of sheaves into a complex of
vector spaces by considering its sheaf cohomology. Sheaf cohomology of line
bundles on the toric variety $X$ is a well-understood subject; for more
details, see (Cox et al., 2011, Chp. 9) and (Altmann and Ploog, 2020).

Observe that, for any Cartier divisor $D$, the twisted complex
$\mathcal{K}_{\bullet}\otimes O_{X}(D)$ is exact, because $O_{X}(D)$ is
locally invertible. Hence, we consider the exact complex
$\mathcal{K}_{\bullet}\otimes O_{X}(\sum_{i}D_{i})$. Every module in the
twisted complex is a direct sum of sheaves of the form $O_{X}(\sum_{i\in
I}D_{i})$, for some $I\subset\\{0,\dots,n\\}$, so they are all nef. Hence, all
the higher sheaf cohomologies of the modules in $\mathcal{K}_{\bullet}\otimes
O_{X}(\sum_{i}D_{i})$ vanish (Cox et al., 2011, Thm. 9.2.3) and so, the
associated complex of global sections is exact (Gelfand et al., 2008, Lem.
2.2.4),

(3) $H^{0}(X,\mathcal{K_{\bullet}}\otimes O_{X}(\sum_{i}D_{i})):0\rightarrow
H^{0}(X,O_{X})\rightarrow\dots{\\\
}\dots\rightarrow\bigoplus_{j}H^{0}(X,O_{X}(\sum_{i\neq
j}D_{i}))\xrightarrow{\mathtt{Sylv}}H^{0}(X,O_{X}(\sum_{i}D_{i}))\rightarrow
0.$

The global sections of the line bundle $O_{X}(\sum_{i\in I}D_{i})$, for
$I\\!\subset\\!\\{0,\dots,n\\}$, correspond to the sparse polynomials with
Newton polytope equal to (or contained in) $\sum_{i\in I}P_{i}$. Hence, the
last map of the exact complex of global sections is the Sylvester map
$(g_{0},\dots,g_{n})\mapsto\sum_{i}g_{i}\,\tilde{f}_{i}$, where $g_{i}$ is a
sparse polynomial such that $\mathtt{NP}(g_{i})\subset\sum_{j\neq i}P_{j}$.
Canny and Emiris’ matrix is a square submatrix of the matrix associated with
this Sylvester map666However, it is not a submatrix of maximal size; see
(Massri, 2016) for more details.. Using this construction, we can also recover
a matrix related to Macaulay’s construction. In this case, we consider
$X=\mathbb{P}^{n}$ and so, its Picard group is $\mathbb{Z}$. We identify
$D_{i}$ with the degree of $\tilde{f}_{i}$ and consider the complex
$\mathcal{K_{\bullet}}\otimes O_{X}(\sum_{i}d_{i}-n)$. By Serre’s vanishing
theorem, the invertible sheaves appearing in this complex have no higher sheaf
cohomologies and so, we can consider the exact complex of vector spaces
$H^{0}(X,\mathcal{K_{\bullet}}\otimes O_{X}(\sum_{i}d_{i}-n))$. The last map
of this complex is the Sylvester map
$(g_{0},\dots,g_{n})\mapsto\sum_{i}g_{i}\,f_{i}$, where $g_{i}$ has degree
$\sum_{j\neq i}\deg(f_{j})$. Macaulay’s matrix is a maximal square submatrix
of this map.

We can also use this construction to understand why the Sylvester matrix gives
us a determinantal formula. In this case, we have that $n=1$ and
$X=\mathbb{P}^{1}$. The aforementioned complex reduces to

$0\rightarrow\mathbb{C}[x_{0},x_{1}]_{d_{1}-1}\oplus\mathbb{C}[x_{0},x_{1}]_{d_{0}-1}\xrightarrow{\mathtt{Sylv}}\mathbb{C}[x_{0},x_{1}]_{d_{0}+d_{1}-1}\rightarrow
0,$

where $d_{i}=\deg(f_{i})$. The exactness of the Sylvester map determines the
exactness of the full complex and agrees with Sylvester’s construction. Hence,
there is no extra-factor in his construction. 777Beware that the arguments at
our exposition are not formal. To prove that the determinant of the complex is
the resultant we need to consider the Koszul (or, more generally, the Weyman)
complex not over $X$, but over $X\times\mathbb{P}^{\bm{A}}$, i.e., the
construction has to be done using systems with generic (symbolic)
coefficients; see (Gelfand et al., 2008).

In the general case, Weyman proposed an approach to derive from
$\mathcal{K}_{\bullet}$ an exact complex whose modules are direct sums of
sheaves cohomologies of the form $H^{i}(X,O_{X}(B))$ and such that the maps
only depend on the coefficients of $(\tilde{f}_{0},\dots,\tilde{f}_{n})$
(Weyman, 2003). By twisting Weyman’s complex by certain line bundles and
studying the vanishing of the sheaf cohomologies appearing in it, several
authors constructed smaller formulas for computing the sparse resultant, e.g.
(Weyman and Zelevinsky, 1994; D’Andrea and Khetan, 2005; Dickenstein and
Emiris, 2003). Moreover, by studying the case when the Weyman complex only
involves two non-zero modules, this construction was used to derive
determinantal formulas for the resultant of multihomogeneous systems, e.g.,
(Weyman and Zelevinsky, 1994; Emiris and Mantzaflaris, 2012; Bender et al.,
2018b; Busé et al., 2020; Emiris et al., 2021; Bender et al., 2021). In what
follows, we present an example taken from (Emiris and Mantzaflaris, 2012, Ex.
5.3) of a determinantal formula obtained from Weyman’s complex which is not a
Sylvester formula.

###### Example 2.2 (Koszul-type formula).

We consider bilinear forms
$f_{0},f_{1},f_{2}\in\mathbb{C}[x_{0},x_{1}]_{1}\otimes\mathbb{C}[y_{0},y_{1}]_{1}$.
Their resultant vanishes if and only if they have a common solution on
$\mathbb{P}^{1}\times\mathbb{P}^{1}$;

(4)
$\displaystyle\begin{cases}f_{0}=(a_{0,0}\,x_{0}+a_{1,0}\,x_{1})\,y_{0}+(a_{0,1}\,x_{0}+a_{1,1}\,x_{1})\,y_{1}\\\
f_{1}=(b_{0,0}\,x_{0}+b_{1,0}\,x_{1})\,y_{0}+(b_{0,1}\,x_{0}+b_{1,1}\,x_{1})\,y_{1}\\\
f_{2}=(c_{0,0}\,x_{0}+c_{1,0}\,x_{1})\,y_{0}+(c_{0,1}\,x_{0}+c_{1,1}\,x_{1})\,y_{1}.\end{cases}$

To construct a determinantal formula, we consider the bilinear map

$\displaystyle\star:\mathbb{C}[y_{0},y_{1}]_{1}\times(\mathbb{C}[x_{0},x_{1}]_{1}\otimes\mathbb{C}[y_{0},y_{1}]_{1})\rightarrow\mathbb{C}[x_{0},x_{1}]_{1}$
$\displaystyle y_{i}\star(x_{k}\,y_{j}):=\left\\{\begin{array}[]{c
c}x_{j}&\text{if }i=j,\\\ 0&\text{otherwise}.\end{array}\right.$

The determinant of
$\phi:(\mathbb{C}[y_{0},y_{1}]_{1})^{3}\rightarrow(\mathbb{C}[x_{0},x_{1}]_{1})^{3}$
is the resultant of the system;

$y_{i}\,\bm{e}_{j}\mapsto\phi(y_{i}\,\bm{e}_{j}):=(y_{i}\star
f_{J_{2}})\,\bm{e}_{J_{1}}-(y_{i}\star
f_{J_{1}})\,\bm{e}_{J_{2}},\quad(J=\\{0,1,2\\}\setminus\\{j\\})$

This formula is not a Sylvester formula, but a Koszul one.

(12) $\displaystyle\begin{array}[]{c || c c c c | c c}&x_{0}\,e_{0}&x_{1}\,e_{0}&x_{1}\,e_{2}&x_{1}\,e_{1}&x_{0}\,\,e_{2}&x_{0}\,e_{1}\\\ \hline\cr\hline\cr y_{0}\,e_{0}&0&0&b_{1,0}&-c_{1,0}&b_{0,0}&-c_{0,0}\\\ y_{1}\,e_{0}&0&0&b_{1,1}&-c_{1,1}&b_{0,1}&-c_{0,1}\\\ y_{1}\,e_{1}&-c_{0,1}&-c_{1,1}&a_{1,1}&0&a_{0,1}&0\\\ y_{1}\,e_{2}&-b_{0,1}&-b_{1,1}&0&a_{1,1}&0&a_{0,1}\\\ \hline\cr y_{0}\,e_{1}&-c_{0,0}&-c_{1,0}&a_{1,0}&0&a_{0,0}&0\\\ y_{0}\,e_{2}&-b_{0,0}&-b_{1,0}&0&a_{1,0}&0&a_{0,0}\end{array}$

###  2.3. Solving sparse systems

In an analogous way to what we can do with the classical (projective)
resultant, we can use the sparse resultant to compute all the solutions of a
sparse square system. In this section, we will discuss eigenvalue methods to
solve polynomial systems. Other solving strategies as the hidden-variable
approach or U-resultants (Cox et al., 2005, Chp. 3.5) can be also extended;
see, e.g., (D’Andrea and Sombra, 2015).

The following method was proposed by Emiris and Rege to recover multiplication
maps using the sparse resultant (Emiris and Rege, 1994). Their approach
generalizes ideas by Auzinger and Stetter for solving classical homogeneous
systems (Auzinger and Stetter, 1988). Consider a sparse polynomial system
$f_{1},\dots,f_{n}$ such that their number of solutions on
$(\mathbb{C}^{*})^{n}$ is the mixed volume of
$\mathtt{NP}(f_{1}),\dots,\mathtt{NP}(f_{n})$ and this volume is not zero. Let
$f_{0}$ be a linear form in the variables $x_{1},\dots,x_{n}$ with Newton
polytope $\Delta_{n}$. We consider the matrix constructed by Canny and Emiris’
algorithm for the sparse resultant of $(f_{0},\dots,f_{n})$ (Canny and Emiris,
1993). This construction will generate monomial sets $B_{0},\dots,B_{n},A$
such that $\sum\\#B_{i}=\\#A$, for any $i$ and $x^{\beta}\in B_{i}$, for which
$\mathtt{Supp}(x^{\beta}\,f_{i})\in A$,
$\\#B_{0}=\mathtt{MV}(P_{1},\dots,P_{n})$ and $B_{0}\subset A$. From these
sets, we consider the Macaulay matrix $M$ whose rows are indexed by monomials
in $A$ and its columns by pairs $(i,x^{\beta})$ where $x^{\beta}\in B_{i}$,
and where in the position corresponding to the row $x^{\alpha}$ and column
$(i,x^{\beta})$, the element is the coefficient of the monomial $x^{\alpha}$
in $x^{\beta}\,f_{i}$. We reorder $M$ such that the bottom rows correspond to
the pairs $(0,x^{\beta})$ and the left-more columns corresponds to the
monomials in $B_{0}$, and we split the matrix accordingly:

(27) $\displaystyle\begin{tabular}[]{r}$\\{x^{\beta}\,f_{i}:i>0,x^{\beta}\in
B_{i}\\}\left\\{\hbox
to0.0pt{$\displaystyle\phantom{\begin{array}[]{c}\\\\[10.0pt]
M_{1,1}\\\\[15.0pt] \hline\cr\end{array}}$\hss}\right.$\\\
$\\{x^{\beta}\,f_{0}:x^{\alpha}\in B_{0}\\}\left\\{\hbox
to0.0pt{$\displaystyle\phantom{\begin{array}[]{c}\\\\[0.0pt]
M_{1,1}\\\\[5.0pt]
\hline\cr\end{array}}$\hss}\right.$\end{tabular}\left[\phantom{\begin{matrix}a_{0}\\\
\ddots\\\ a_{0}\\\ b_{0}\\\ \ddots\\\
b_{0}\end{matrix}}\right.\overbrace{\begin{array}[]{c |}\\\\[10.0pt] \hskip
18.0ptM_{1,1}\\\\[15.0pt] \hline\cr\hline\cr\\\\[0.0pt] M_{2,1}\\\\[5.0pt]
\end{array}}^{\text{\huge$A\setminus B_{0}$}}\overbrace{\begin{array}[]{|
c}\\\\[10.0pt] \hskip 2.0ptM_{1,2}\\\\[15.0pt] \hline\cr\hline\cr\\\\[0.0pt]
M_{2,2}\\\\[5.0pt]
\end{array}}^{\text{\huge$B_{0}$}}\left.\phantom{\begin{matrix}a_{0}\\\
\ddots\\\ a_{0}\\\ b_{0}\\\ \ddots\\\ b_{0}\end{matrix}}\right]$

Emiris and Rege showed that if the system $(f_{1},\dots,f_{n})$ is generic-
enough then the matrix $M_{1,1}$ is invertible and so the Schur complement of
$M_{2,2}$, i.e. the matrix $M_{2,2}-M_{1,2}\,M_{1,1}^{-1}\,M_{2,1}$, is the
multiplication matrix of $f_{0}$ in
$\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}]/\langle f_{1},\dots,f_{n}\rangle$.
The latter holds because this matrix allows us to rewrite elements of the form
$f_{0}\,(\sum_{\beta\in B_{0}}c_{\beta}\,x^{\beta})$ as $\sum_{\beta\in
B_{0}}\bar{c}_{\beta}\,x^{\beta}+g$, where $g\in\langle
f_{1},\dots,f_{n}\rangle$. If the resultant of $(f_{0},\dots,f_{n})$ does not
vanish, then the map is invertible, and so $B_{0}$ is a monomial basis of
$\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}]/\langle f_{1},\dots,f_{n}\rangle$
as its cardinal $\mathtt{MV}(P_{1},\dots,P_{n})$ agrees with the dimension of
the quotient ring (Pedersen and Sturmfels, 1996). The generic assumptions of
the aforementioned construction can be relaxed (Rojas, 1999; Telen, 2020a;
Bender and Telen, 2022) and the construction can be extended to solve
overdetermined sparse systems (Massri, 2016; Bender and Telen, 2021).
Recently, special attention has been given to the numerical aspects of this
approach (Telen, 2020a; Bender and Telen, 2022, 2021). In general, we can use
determinantal formulas to compute matrices which are similar to multiplication
matrices, i.e., they share the same eigenvalues (Bender et al., 2018b). In
contrast to the Sylvester formulas, the eigenvectors of the determinantal
formulas are not well-understood, with the exception of the Koszul formulas
(Bender et al., 2018b).

###### Example 2.3 (Solving using determinantal formulas).

Following our Example 2.2, we fix
$f_{0},f_{1},f_{2}\in\mathbb{C}[x_{0},x_{1}]_{1}\otimes\mathbb{C}[y_{0},y_{1}]_{1}$
as in (4) and partition the determinantal formula as in (12),

$\left[\begin{array}[]{c | c}M_{1,1}&M_{1,2}\\\ \hline\cr M_{2,1}&M_{2,2}\end{array}\right]$

We will show that, if the coordinates $x_{0}$ and $y_{0}$ of every solution of
$(f_{1},f_{2})$ are different to zero, then we can solve $(f_{1},f_{2})$ by
computing the eigenvalues of the Schur complement of $M_{2,2}$.

By assumption, the system $(x_{0}\,y_{0},f_{1},f_{2})$ has no solution and so
the matrix $M_{1,1}$ is invertible as the resultant of
$(x_{0}\,y_{0},f_{1},f_{2})$ is $\det(M_{1,1})\neq 0$. We introduce a new
variable $\lambda$ and consider the resultant of the system
$(f_{0}-\lambda\,x_{0},\,y_{0},f_{1},f_{2})$. By the Poisson formula (D’Andrea
and Sombra, 2015), the resultant is a polynomial in $\lambda$ whose roots are
of the form $\frac{f_{0}}{x_{0}\,y_{0}}$ evaluated at the solutions of
$(f_{1},f_{2})$. Hence, the determinantal formula for
$(f_{0}-\lambda\,x_{0}\,y_{0},f_{1},f_{2})$ given in (12), can be written as

$\left[\begin{array}[]{c|c}M_{1,1}&M_{1,2}\\\ \hline\cr
M_{2,1}&M_{2,2}-\lambda\,I\end{array}\right]$

where $I$ is the $2\times 2$ identity matrix. Hence, the resultant of
$(f_{0}-\lambda\,x_{0}\,y_{0},f_{1},f_{2})$ agrees with the determinant of the
Schur complement of $M_{2,2}-\lambda\,I$. Equivalently, the eigenvalues of the
Schur complement of $M_{2,2}$ are the evaluations of
$\frac{f_{0}}{x_{0}\,y_{0}}$ at the solutions of $(f_{1},f_{2})$.

##  3\. Gröbner bases

The objective of this section is to compute Gröbner bases for sparse
polynomial systems. Gröbner bases algorithms usually can incorporate a priori
information of the system to speed up computations, e.g., syzygy module
(Faugère, 2002; Eder and Faugère, 2017) or Hilbert series (Traverso, 1996).
The main issue when we compute with sparse polynomials is that they behave
differently from dense systems, and we do not have much prior information on
them. We will explain how toric geometry can help us understand the systems
better and so, speed up computations.

###  3.1. Embedding of a toric variety

In this section, we will fix polytopes $P_{1},\dots,P_{m}$ and consider the
projective normal toric variety $X$ associated with $P:=P_{1}+\dots+P_{m}$
detailed in the previous section. We assume $P$ is full-dimensional. Given an
integer polytope $Q$, we say it is a _$\mathbb{N}$ -Minkowski summand_ of $P$
if there is $k\in\mathbb{N}$ and an integer polytope $S$ such that $Q+S=k\,P$.
To each $\mathbb{N}$-Minkowski summand $Q$ of $P$ there is a nef Cartier
divisor $D_{Q}$ such that we can identify the global sections of the nef line
bundle $O_{X}(D_{Q})$ with the polynomials whose Newton polytope is equal to
(or contained in) $Q$, as in (1) (Cox et al., 2011, Chp. 6). Moreover, we have
that for two $\mathbb{N}$-Minkowski summands $Q,S$, the global sections of
$O_{X}(D_{Q}+D_{S})$ correspond to the polynomials with Newton polytope $Q+S$.
Given $f_{i}$ with Newton polytope contained in $P_{i}$, we will _homogenize_
$f_{i}$ and write it as $\tilde{f}_{i}\in H^{0}(X,O_{X}(D_{P_{i}}))$. The
common zeros of $\tilde{f}_{1},\dots,\tilde{f}_{m}$ will determine a subscheme
of $X$, that we denote by $Y$. The subscheme $Y\cap(\mathbb{C}^{*})^{n}$
agrees with the subscheme defined by the original $f_{1},\dots,f_{m}$ on
$(\mathbb{C}^{*})^{n}$. Particularly, when $Y\subset(\mathbb{C}^{*})^{n}$, $Y$
is zero-dimensional and we can study the solutions of $f_{1},\dots,f_{m}$ on
$(\mathbb{C}^{*})^{n}$ by studying $Y$.

###### Example 3.1 (Intersection theory for toric varieties).

If $m=n$ and $Y$ is zero-dimensional, the mixed volume
$\mathtt{MV}(P_{1},\dots,P_{n})$ is actually the intersection number of
$D_{P_{1}},\dots,D_{P_{n}}$; see (Fulton, 1993, Chp. 5). Hence, the number of
solutions of $f_{1},\dots,f_{n}$ is bounded by the degree of $Y$, and so by
this mixed volume. Moreover, generically, the system
$(\tilde{f}_{1},\dots,\tilde{f}_{n})$ has no solutions on
$X\setminus(\mathbb{C}^{*})^{n}$ and so the BKK bound is tight. In general,
the BKK bound is tight when we count the _solutions at infinity_.

In what follows, we assume that there are _$\mathbb{N}$ -Minkowski summands_
$Q_{1},\dots,Q_{r}$ of $P$ and vectors $d_{1},\dots,d_{m}\in\mathbb{Z}^{r}$
such that $P_{i}=\sum_{k}d_{i,k}\,Q_{k}$. We consider the
$\mathbb{N}^{r}$-graded algebra given by

$R^{h}:=\bigoplus_{b\in\mathbb{N}^{r}}H^{0}\left(X,O_{X}\left(\sum_{k}b_{k}D_{Q_{k}}\right)\right)=\bigoplus_{b\in\mathbb{N}^{r}}\\!\\!\\!\\!\\!\\!\\!\\!\bigoplus_{\begin{subarray}{c}\phantom{A}\\\
\alpha\in(\sum_{k}b_{k}\,Q_{k})\cap\mathbb{Z}^{n}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{C}\,x^{(\alpha,b)}.$

The Multi-Proj of $R^{h}$ is the embedding of $X$ in a (weighted) multi-
projective space.

Hence, given polynomials $f_{1},\dots,f_{m}$ with Newton polytopes
$P_{1},\dots,P_{m}$, we can homogenize them as
$(\tilde{f}_{1},\dots,\tilde{f}_{m})$ such that, for each $i$,
$\tilde{f}_{i}\in S^{h}_{d_{i}}$. If the polynomials $f_{1},\dots,f_{m}$ are
generic enough, we can predict the properties of
$(\tilde{f}_{1},\dots,\tilde{f}_{m})$ on $R^{h}$. For this reason, we will
compute Gröbner bases over $R^{h}$ and use them to compute Gröbner bases over
other rings. To formalize this, we introduce the notion of Gröbner bases over
pointed affine semigroup algebras.

###  3.2. Gröbner bases for semigroup algebras

In this section, we will only consider affine semigroups with identity, that
is, a semigroup $(S,+)$ with identity $0$, isomorphic to a finitely-generated
submonoid of $\mathbb{Z}^{k}$. We say that $(S,+)$ is pointed if $\alpha\in
S\setminus\\{0\\}$, $-\alpha\not\in S$, where $-\alpha$ is defined in the
smallest group containing $S$. Given a semigroup, we define the semigroup
algebra $\mathbb{C}[S]$ as the monomial $\mathbb{C}$-algebra generated by the
monomials $\\{x^{\alpha}:\alpha\in S\\}$.

If $(S,+)$ is a pointed semigroup, it is possible to define a monomial
ordering $<$ for $\mathbb{C}[S]$; see (Faugère et al., 2014, Def. 3.1). For
example, if $S\subset\mathbb{N}^{s}$, for some $s\in\mathbb{N}$, then any
monomial ordering for the standard algebra $\mathbb{C}[x_{1},\dots,x_{s}]$
induces a monomial ordering on $\mathbb{C}[S]$. Hence, we can define Gröbner
bases for ideals in $\mathbb{C}[S]$ using the standard definition, i.e.,
$G\subset\mathbb{C}[S]$ is a Gröbner basis for an ideal
$I\subset\mathbb{C}[S]$ with respect to a monomial ordering $<$ if $G\subset
I$ and, for every $f\in I$, there is $g\in G$ and $x^{\alpha}\in\mathbb{C}[S]$
such that $x^{\alpha}\,\mathtt{LM}_{<}(g)=\mathtt{LM}_{<}(f)$, where
$LM_{<}(\cdot)$ is the leading monomial in $\mathbb{C}[S]$ with respect to
$<$.

Given $\alpha\in\mathbb{R}^{n}\times\mathbb{R}^{r}$, let $\pi_{1},\pi_{2}$ be
its projections onto $\mathbb{R}^{n}$ and $\mathbb{R}^{r}$, respectively.
Clearly, as $S$ is a semigroup, $\pi_{1}(S)$ and $\pi_{2}(S)$ are also
semigroups. In what follows, we assume that, for the affine pointed semigroup
$S$, it holds that $\pi_{1}(S)$ and $\pi_{2}(S)$ are also an affine pointed
semigroups and the preimage of each $\gamma\in\pi_{2}(S)$ is finite. Somehow,
we will think about $\pi_{2}(S)$ as a grading of $S$. In this case, we say
that a monomial ordering $<$ for $S$ is _graded_ if there is another monomial
ordering $<_{1}$ for $\pi_{1}(S)$ and $<_{2}$ for $\pi_{2}(S)$ such that

$x^{\alpha}<x^{\beta}\iff\left\\{\begin{array}[]{l}x^{\pi_{2}(\alpha)}<_{2}x^{\pi_{2}(\beta)}\text{
or }\\\ x^{\pi_{2}(\alpha)}=x^{\pi_{2}(\beta)}\text{ and
}x^{\pi_{1}(\alpha)}<_{1}x^{\pi_{1}(\beta)}\end{array}\right.$

The algebra $R^{h}$ defined in Subsection 3.1 corresponds to the semigroup
algebra associated with the semigroup

$S^{h}:=\left\\{(\alpha,b)\in\mathbb{Z}^{n}\times\mathbb{Z}^{r}:\alpha\in\left(\sum_{i}b_{i}Q_{i}\right)\cap\mathbb{Z}^{n}\right\\}.$

If $0$ is a vertex of each $Q_{i}$ and of $\sum_{i}Q_{i}$, we can see that
$S^{h}$ satisfies the assumptions on the projections $\pi_{1}$ and $\pi_{2}$
detailed above. As the solution set of $(f_{1},\dots,f_{m})$ over
$(\mathbb{C}^{*})^{n}$ does not change if we multiply the polynomials by
monomials, equivalently, if we translate their Newton polytopes, we will
assume with no loss of generality than $0$ is a vertex of the aforementioned
polytopes. Therefore, we consider the semigroup algebra

$R:=\mathbb{C}[\pi_{1}(S^{h})]\subset\mathbb{C}[x_{1}^{\pm},\dots,x_{n}^{\pm}].$

We define $\pi$ as the homomorphism between $R^{h}$ and $R$ taking
$x^{\alpha}\mapsto\pi(x^{\alpha}):=x^{\pi_{1}(\alpha)}$. This morphism acts as
a _dehomogenization_ and it relates to graded orders as follow. Given a
Gröbner basis $G$ of an ideal of $I\subset R^{h}$ with respect to a graded
order $<$, the set $\pi(G)$ is a Gröbner basis for $\pi(I)\subset R$ with
respect to $<_{1}$ (Faugère et al., 2014, Prop. 3.5).

###  3.3. Computing Gröbner bases

In this section we discuss an algorithm to compute Gröbner bases for an ideal
$\langle f_{1},\dots,f_{r}\rangle\subset R$ with respect to a monomial
ordering $<_{1}$. For this, we will compute Gröbner bases for
$\langle\tilde{f}_{1},\dots,\tilde{f}_{r}\rangle\subset R^{h}$ with respect to
a graded monomial ordering $<$ associated with $<_{1}$. In what follows, we
ignore the subindex from the ordering $<_{1}$.

For each multidegree $b\in\mathbb{N}^{r}$, we will construct a Macaulay matrix
$M_{b}$ where the columns are indexed by the monomials of degree $b$ in
$R^{h}$, the rows by the pairs $(i,x^{\beta})$, where $x^{\beta}$ is a
monomial of degree $b-d_{i}$. The rows are sorted in decreasing order with
respect to $<$ and the columns are sorted in decreasing order in the following
way: if $i>j$, or $i=j$ and $x^{\alpha}>x^{\beta}$, then
$(i,x^{\alpha})<(j,x^{\beta})$. The element of the matrix $M_{b}$ of column
index $x^{\alpha}$, and row $(i,x^{\beta})$ is the coefficient of the monomial
$x^{\alpha}$ in $x^{\beta}\tilde{f}_{i}$ . As Lazard realized (Lazard, 1983),
if we perform Gaussian elimination with no pivoting, we obtain new rows
representing elements in the Gröbner basis of
$\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle$ of degree $b$. As the
Gröbner basis is finite, if we perform this computation for sufficiently many
different degrees, we recover the complete Gröbner basis.

A classical bottleneck of Gröbner bases computations are reductions to zero.
In the sketched algorithm, these reductions to zero correspond to the rows
reducing to zero after performing Gaussian elimination. An established way of
speeding up computations is to avoid these reductions using the F5 criterion
(Faugère, 2002; Eder and Faugère, 2017). In this context, the F5 criterion is
called Matrix-F5 (Eder and Faugère, 2017, Sec. 3) and translates into skipping
some rows from the construction of the matrix. The F5 criterion tells us that
the row indexed by $(i,x^{\beta})$ will reduce to zero after performing
Gaussian elimination if and only if $x^{\beta}$ is the leading monomial of a
polynomial of degree ${b-d_{i}}$ in the colon ideal
$(\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle:f_{i})$, i.e.,
$x^{\beta}\in
LM((\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle:f_{i}))_{b-d_{i}}$. We
can organize our computation in such a way that we can recover from it
$LM(\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle)_{b-d_{i}}$ (Eder and
Faugère, 2017, Sec. 3). Hence, when these two sets agree, we can skip every
reduction to zero, that is, the F5 criterion is _optimal_. A classical setting
where this happens is when $f_{i}$ is not a zero divisor in
$R^{h}/\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle$. Hence, when
$(\tilde{f}_{1},\dots,\tilde{f}_{m})$ is a regular sequence, i.e., when the
previous condition holds for every $i$, then we can avoid every reduction to
zero. In the unmixed case, we have that $r=1$ and the ring $R^{h}$ is
$\mathbb{N}$-graded. It can be shown that this is a Cohen-Macaulay ring and
that, if $m\leq n$, a generic unmixed sparse system
$(\tilde{f}_{1},\dots,\tilde{f}_{m})$ forms a regular sequence on $R^{h}$
(Hochster, 1972). This last fact was exploited by Faugère, Spaenlehauer, and
Svartz (Faugère et al., 2014) to compute Gröbner bases for unmixed systems.
However, in the mixed case, this is not true anymore, that is, our system
$(\tilde{f}_{1},\dots,\tilde{f}_{m})$ usually does not form a regular sequence
on $R^{h}$. To solve this problem, together with Faugère and Tsigaridas
(Bender et al., 2018a, 2019), we observed that the F5 criterion is optimal at
_certain degree_ $b$ whenever
$(\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle:f_{i})_{b-d_{i}}=\langle\tilde{f}_{1},\dots,\tilde{f}_{i-1}\rangle_{b-d_{i}}$,
for each $i$. This condition can be enforced by the vanishing of the first
homology of the Koszul complex of $(\tilde{f}_{1},\dots,\tilde{f}_{i})$ at
degree $b$, for each $i$. We can prove that, if the subscheme defined by
$(\tilde{f}_{1},\dots,\tilde{f}_{i})$ on $X$ is a complete intersection, then
the first homology of the Koszul complex of
$(\tilde{f}_{1},\dots,\tilde{f}_{i})$ vanishes at any degree $b\geq\sum_{j\leq
i}d_{i}$. Moreover, this bound can be improved for special systems. For
example, for multihomogeneous systems over
$\mathbb{P}^{n_{1}}\times\dots\times\mathbb{P}^{n_{r}}$, we have that
$b\geq\sum_{j\leq i}d_{i}-(n_{1},\dots,n_{r})$ suffices (Bender et al., 2018a)
888A spectre is haunting this argument - a spectral sequence associated to the
Koszul complex of sheaves mentioned in the previous section. Normal projective
toric varieties are Cohen-Macaulay, so if
$(\tilde{f}_{1},\dots,\tilde{f}_{i})$ defines a complete intersection $Y$ on
$X$, the Koszul complex gives a resolution for the structure sheaf $O_{Y}$. In
this case, we can transform this complex into a resolution of $R^{h}/\langle
f_{1},\dots,f_{i-1}\rangle$ at degree $b\in\mathbb{N}^{r}$, if for each
$I\subseteq\\{1,\dots,i\\}$, $H^{t}(X,O_{X}(\sum_{j}(b_{j}-\sum_{k\in
I}d_{j,k})D_{Q_{j}}))=0$, for $t>0$. It is easy to construct a priori bounds
for $b$ as $\sum_{j}d_{i}$ using vanishing theorems for the sheaf cohomology
of line bundles over toric varieties; see, e.g., (Bender and Telen, 2022, Sec.
4). In our papers (Bender et al., 2018a, 2019), we skipped this discussion by
defining the concept of _Koszul regular systems_ as the systems such that, for
every subsystem, the first homology of its associated Koszul complex vanishes
at certain degrees, which we can predict from the previous analysis. . Hence,
we can predict all the reductions to zero appearing at “big-enough” degree.
Moreover, if our objective is to only compute Gröbner bases over $R$, we will
just avoid the degrees at which we cannot predict every reduction.

###### Remark 3.2.

This strategy generalizes partially previous work on computing Gröbner bases
for special sparse systems such as bilinear (Faugère et al., 2011) and
weighted homogeneous systems (Faugère et al., 2016).

To derive complexity bounds, we need to construct a bound of the maximal
degree of an element in a Gröbner bases of
$\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle$. However, the monomial
orderings defined over semigroup algebras, in general, does not have the
dehomogenization property of GRevLex (Bender, 2019, Ex. 7.2.1). Moreover, we
cannot talk about generic coordinates for the solutions, as random change of
coordinates destroys the sparsity. Hence, we cannot use strategies as (Bayer
and Stillman, 1987) to construct bounds for the maximal degrees of the
elements in the Gröbner bases. As we will show in the next section, we can
work around this problem in the zero-dimensional case, i.e., when the
subscheme associated to $\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle$ has
dimension zero.

###  3.4. Zero-dimensional systems

In this section, we will construct bounds for computing Gröbner bases of zero-
dimensional ideals. Classically, to compute Gröbner bases for zero-dimensional
systems, we first calculate a Gröbner basis with respect to GRevLex and then
we use FGLM to recover the Gröbner basis with respect to the ordering we want.
We do so because, with respect to GRevLex, the Gröbner basis involves elements
of smaller degrees, for which we may find upper bounds. Generally, the maximal
degree of an element in a Gröbner basis of a zero-dimensional ideal is given
by the _Castelnuovo-Mumford regularity_ of its homogenization (Chardin, 2003,
Cor. 3). In the semigroup setting, where there usually does not exist a
GRevLex ordering, the maximal degree of an element in the Gröbner basis could
be higher than the regularity; see (Bender, 2019, Sec. 8.3.1). To work around
this problem, in (Bender et al., 2018a, 2019), we presented a way to recover
the multiplication maps by truncating our computation of Gröbner bases at a
certain degree. By doing so, we bounded the complexity of our computation. In
what follows, we explain the idea behind this strategy in the general case of
mixed sparse polynomial systems and refer the reader to (Bender, 2019, Chp. 8)
for improvements in special cases.

Following the notation from the previous section, we consider an affine sparse
system $(f_{1},\dots,f_{m})$ such that the subscheme $Y$ associated with
$\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle\subset R^{h}$ has only
solutions on $(\mathbb{C}^{*})^{n}$ (in particular, $Y$ is finite as $X$ is
compact). That is, it has no solutions at infinity. We assume without loss of
generality that $1,x_{1},\dots,x_{n}\in R$.999If the monomials do not belong
to $R$, we change the toric variety $X$ by another one associated with
$P+\Delta_{n}$. As $Y\subset(\mathbb{C}^{*})^{n}$, this change does not affect
$Y$ and adds a degree $d_{0}$ to $R^{h}$ as wanted; see (Bender et al., 2019,
Sec. 4). In this case, we can prove (Bender et al., 2019, Lem. 4.11),

$R/\pi(\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle)\simeq\mathbb{C}[x_{1},\dots,x_{n}]/(\langle
f_{1},\dots,f_{n}\rangle:\langle\Pi_{i}x_{i}\rangle^{\infty}).$

Our strategy will be to perform FGLM using multiplication maps over
$R/\pi(\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle)$ to recover the
Gröbner basis of $\langle
f_{1},\dots,f_{m}\rangle:\langle\Pi_{i}x_{i}\rangle^{\infty}$ in
$\mathbb{C}[x_{1},\dots,x_{n}]$. In what follows, we focus on computing these
multiplication maps by adapting Emiris and Rege (Emiris and Rege, 1994).

Consider $b=\sum_{i}d_{i}$, where $d_{i}$ is the multidegree of
$\tilde{f}_{i}$. Let $d_{0}$ be a multidegree such that
$\Delta_{n}\cap\mathbb{N}^{n}\subset\pi(R^{h}_{d_{0}})$, that is, after
dehomogenization, we can obtain a linear form in $R$. At the degrees $b$ and
$b+d_{0}$, the ideal $R^{h}/\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle$
is a vector space of dimension $\delta$ equal to the number of points in $Y$,
counting multiplicities (Massri, 2016, Thm. 3). Let $B_{0}$ be the set of
monomials of degree $d$ which are not leading monomials in
$LM(\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle)$. The cardinality of
$B_{0}$ is $\delta$. Moreover, also by (Massri, 2016, Thm. 3), as there are no
solutions outside $(\mathbb{C}^{*})^{n}$, for any monomial $x^{\alpha}\in
R^{h}_{d_{0}}$,
$R^{h}_{b+d_{0}}=\langle\tilde{f}_{1},\dots,\tilde{f}_{m},x^{\alpha}\rangle_{b+d_{0}}$,
and using the F5 criterion, it is easy to see that the monomial set
$\\{x^{\alpha}\,x^{\beta}:x^{\beta}\in B_{0}\\}$ forms a basis of the vector
space $(R^{h}/\langle\tilde{f}_{1},\dots,\tilde{f}_{m}\rangle)_{b+d_{0}}$. Let
$x^{\alpha_{0}}$ be the monomial of degree $b+d_{0}$ such that
$\pi(x^{\alpha_{0}})=1$. Then, we can use our Macaulay matrix at degree
$b+d_{0}$ related to $(\tilde{f}_{1},\dots,\tilde{f}_{m})$ to rewrite any
product $x^{\beta}\,f_{0}$, where $f_{0}\in R^{h}_{d_{0}}$ and $x^{\beta}\in
B_{0}$, as a linear combination of monomials in
$\\{x^{\alpha}\,x^{\beta}:x^{\beta}\in B_{0}\\}$. By dehomogenizing this
relation, we recover the multiplication map of $\pi(f_{0})$ over
$R/\langle\pi(\tilde{f}_{1}),\dots,\pi(\tilde{f}_{m})\rangle$, with respect to
the basis $\pi(B_{0})$. As the monomials $1,x_{1},\dots,x_{n}$ belong to
$\pi(B_{0})$, we can recover every multiplication map in
$\mathbb{C}[x_{1},\dots,x_{n}]/(\langle
f_{1},\dots,f_{n}\rangle:\langle\Pi_{i}x_{i}\rangle^{\infty})$.

###### Acknowledgements.

This manuscript is dedicated to the memory of Agnes Szanto. Thank you very
much, Agnes, for your selfless help and support. I would like to thank
Christopher Borger, Jean-Charles Faugère, Angelos Mantzaflaris, Pierre-Jean
Spaenlehauer, Elias Tsigaridas, and Simon Telen, for our joint work where I
learned a lot about what is detailed in this manuscript. Also, to Laurent Busé
and Marc Chardin, for teaching me how to use local cohomology and spectral
sequences to study the Castelnuovo-Mumford regularity. I am grateful to Fatima
Abu Salem and Amir Hashemi for their several comments and corrections on this
manuscript. This work was funded by the ERC under the European’s Horizon 2020
research and innovation programme (grant agreement 787840).

## References

  * (1)
  * Altmann and Ploog (2020) Klaus Altmann and David Ploog. 2020.  Displaying the cohomology of toric line bundles.  _Izvestiya: Mathematics_ 84, 4 (2020), 683\.
  * Auzinger and Stetter (1988) Winfried Auzinger and Hans J. Stetter. 1988.  An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations.  In _Numerical Mathematics Singapore 1988: Proceedings of the International Conference on Numerical Mathematics held at the National University of Singapore, May 31–June 4, 1988_ , Ravi P. Agarwal, Y. M. Chow, and S. J. Wilson (Eds.). 11–30.
  * Bayer and Stillman (1987) David Bayer and Michael Stillman. 1987.  A criterion for detecting m-regularity.  _Inventiones Mathematicae_ 87, 1 (Feb. 1987), 1–11.
  * Bazan and Hubert (2020) Erick Rodriguez Bazan and Evelyne Hubert. 2020.  Ideal interpolation, H-bases and symmetry. In _Proceedings of the 45th international symposium on symbolic and algebraic computation_ (Kalamata, Greece) _(ISSAC ’20)_. 402–409.
  * Bender (2019) Matías R. Bender. 2019\.  _Algorithms for sparse polynomial systems: Groebner basis and resultants_.  Ph. D. Dissertation. Sorbonne Université.
  * Bender et al. (2018b) Matías R. Bender, Jean-Charles Faugère, Angelos Mantzaflaris, and Elias Tsigaridas. 2018b.  Bilinear systems with two supports: Koszul resultant matrices, eigenvalues, and eigenvectors. In _Proceedings of the 2018 ACM international symposium on symbolic and algebraic computation_ _(ISSAC ’18)_. 63–70.
  * Bender et al. (2021) Matías R. Bender, Jean-Charles Faugère, Angelos Mantzaflaris, and Elias Tsigaridas. 2021\.  Koszul-Type determinantal formulas for families of mixed multilinear systems.  _SIAM Journal on Applied Algebra and Geometry_ 5, 4 (2021), 589–619.
  * Bender et al. (2018a) Matías R. Bender, Jean-Charles Faugère, and Elias Tsigaridas. 2018a.  Towards mixed gröbner basis algorithms: the multihomogeneous and sparse case. In _Proceedings of the 2018 ACM international symposium on symbolic and algebraic computation_ _(ISSAC ’18)_. 71–78.
  * Bender et al. (2019) Matías R. Bender, Jean-Charles Faugère, and Elias Tsigaridas. 2019.  Groebner basis over semigroup algebras: Algorithms and applications for sparse polynomial systems. In _Proceedings of the 2019 on international symposium on symbolic and algebraic computation_ _(ISSAC ’19)_. 42–49.
  * Bender and Telen (2021) Matías R. Bender and Simon Telen. 2021.  Yet another eigenvalue algorithm for solving polynomial systems.  _arXiv:2105.08472 [cs, math]_ (May 2021).
  * Bender and Telen (2022) Matías R. Bender and Simon Telen. 2022.  Toric eigenvalue methods for solving sparse polynomial systems.  _Math. Comp._ (2022).  In press; arXiv: 2006.10654.
  * Bernshtein (1975) David N. Bernshtein. 1975\.  The number of roots of a system of equations.  _Functional Analysis and Its Applications_ 9, 3 (July 1975), 183–185.
  * Berthomieu et al. (2021) Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. 2021.  Msolve: a library for solving polynomial systems. In _Proceedings of the 2021 on international symposium on symbolic and algebraic computation_ (Virtual Event, Russian Federation) _(ISSAC ’21)_. 51–58.
  * Bihan and Dickenstein (2017) Frédéric Bihan and Alicia Dickenstein. 2017.  Descartes’ rule of signs for polynomial systems supported on circuits.  _International Mathematics Research Notices_ 2017, 22 (2017), 6867–6893.
  * Bihan and Soprunov (2019) Frédéric Bihan and Ivan Soprunov. 2019.  Criteria for strict monotonicity of the mixed volume of convex polytopes.  _Advances in Geometry_ 19, 4 (2019), 527–540.
  * Bihan and Sottile (2007) Frédéric Bihan and Frank Sottile. 2007.  New fewnomial upper bounds from Gale dual polynomial systems.  _Moscow mathematical journal_ 7, 3 (2007), 387–407.
  * Breiding et al. (2021) Paul Breiding, Türkü Özlüm Çelik, Timothy Duff, Alexander Heaton, Aida Maraj, Anna-Laura Sattelberger, Lorenzo Venturello, and Oǧuzhan Yürük. 2021\.  Nonlinear algebra and applications.  _Numerical Algebra, Control and Optimization_ (2021).
  * Bürgisser and Cucker (2013) Peter Bürgisser and Felipe Cucker. 2013.  _Condition: The geometry of numerical algorithms_.
  * Bürgisser et al. (2020) Peter Bürgisser, Felipe Cucker, and Pierre Lairez. 2020\.  Rigid continuation paths II. Structured polynomial systems.  _arXiv:2010.10997_ (2020).
  * Bürgisser et al. (2019) Peter Bürgisser, Alperen A Ergur, and Josué Tonelli-Cueto. 2019.  On the number of real zeros of random fewnomials.  _SIAM Journal on Applied Algebra and Geometry_ 3, 4 (2019), 721–732.
  * Burr et al. (2022) Michael Burr, Frank Sottile, and Elise Walker. 2022\.  Numerical homotopies from Khovanskii bases.  _Math. Comp._ (2022).  In press; arXiv: 2008.13055.
  * Busé (2006) Laurent Busé. 2006\.  _Elimination theory in codimension one and applications_.  Research Report RR-5918. INRIA. 47 pages.  Notes of lectures given at the CIMPA-UNESCO-IRAN school in Zanjan, Iran, July 9-22 2005.
  * Busé et al. (2020) Laurent Busé, Angelos Mantzaflaris, and Elias Tsigaridas. 2020\.  Matrix formulæ for resultants and discriminants of bivariate tensor-product polynomials.  _Journal of Symbolic Computation_ 98 (May 2020), 65–83.
  * Canny (1990) John Canny. 1990\.  Generalised characteristic polynomials.  _Journal of Symbolic Computation_ 9, 3 (March 1990), 241–250.
  * Canny and Emiris (1993) John Canny and Ioannis Emiris. 1993.  An efficient algorithm for the sparse mixed resultant. In _Applied algebra, algebraic algorithms and error-correcting codes_ , Gérard Cohen, Teo Mora, and Oscar Moreno (Eds.). 89–104.
  * Canny and Rojas (1991) John Canny and J. Maurice Rojas. 1991.  An optimal condition for determining the exact number of roots of a polynomial system. In _Proceedings of the 1991 international symposium on Symbolic and algebraic computation_ _(ISSAC ’91)_. 96–102.
  * Chardin (2003) Marc Chardin. 2003\.  Bounds for Castelnuovo-Mumford regularity in terms of degrees of defining equations.  In _Commutative algebra, singularities and computer algebra_ , Jürgen Herzog and Victor Vuletescu (Eds.). 67–73.
  * Chen and Maza (2012) Changbo Chen and Marc Moreno Maza. 2012.  Algorithms for computing triangular decomposition of polynomial systems.  _Journal of Symbolic Computation_ 47, 6 (2012), 610–642.
  * Chen (2019) Tianran Chen. 2019\.  Unmixing the mixed volume computation.  _Discrete & Computational Geometry_ 62, 1 (July 2019), 55–86.
  * Cifuentes and Parrilo (2016) Diego Cifuentes and Pablo A Parrilo. 2016.  Exploiting chordal structure in polynomial ideals: A grobner bases approach.  _SIAM Journal on Discrete Mathematics_ 30, 3 (2016), 1534–1570.
  * Cox (1995) David A. Cox. 1995\.  The homogeneous coordinate ring of a toric variety, Revised version.  _Journal of Algebraic Geometry_ 4 (1995), 17–50.
  * Cox (2021) David A. Cox. 2021\.  Stickelberger and the eigenvalue theorem.  In _Commutative algebra: Expository papers dedicated to David Eisenbud on the occasion of his 75th birthday_ , Irena Peeva (Ed.). 283–298.
  * Cox et al. (2020) David A. Cox, Carlos D’Andrea, Alicia Dickenstein, Jonathan D. Hauenstein, Henry K. Schenck, and Jessica Sidman. 2020.  _Applications of polynomial systems_.  Number 134 in Conference Board of the Mathematical Sciences CBMS regional conference series in mathematics.
  * Cox et al. (2005) David A. Cox, John Little, and Donal O’Shea. 2005\.  _Using algebraic geometry_ (2 ed.).
  * Cox et al. (2011) David A. Cox, John B. Little, and Henry K. Schenck. 2011\.  _Toric varieties_.
  * Cucker et al. (2008) Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor. 2008.  A numerical algorithm for zero counting, I: Complexity and accuracy.  _Journal of Complexity_ 24, 5-6 (2008), 582–605.
  * D’Andrea (2002) Carlos D’Andrea. 2002\.  Macaulay style formulas for sparse resultants.  _Trans. Amer. Math. Soc._ 354, 7 (2002), 2595–2629.
  * D’Andrea et al. (2022) Carlos D’Andrea, Gabriela Jeronimo, and Martín Sombra. 2022\.  The Canny–Emiris conjecture for the sparse resultant.  _Foundations of Computational Mathematics_ (2022), 1–61.
  * D’Andrea and Khetan (2005) Carlos D’Andrea and Amit Khetan. 2005.  Macaulay style formulas for toric residues.  _Compositio Mathematica_ 141, 03 (May 2005), 713–728.
  * D’Andrea and Sombra (2015) Carlos D’Andrea and Martín Sombra. 2015.  A Poisson formula for the sparse resultant.  _Proceedings of the London Mathematical Society_ 110, 4 (2015), 932–964.
  * Dickenstein and Emiris (2003) Alicia Dickenstein and Ioannis Z. Emiris. 2003.  Multihomogeneous resultant formulae by means of complexes.  _Journal of Symbolic Computation_ 36, 3 (2003), 317–342.
  * Dickenstein and Emiris (2005) Alicia Dickenstein and Ioannis Z. Emiris (Eds.). 2005.  _Solving polynomial equations_. Algorithms and Computation in Mathematics, Vol. 14.
  * Diochnos et al. (2009) Dimitrios I Diochnos, Ioannis Z Emiris, and Elias P Tsigaridas. 2009.  On the asymptotic and practical complexity of solving bivariate systems over the reals.  _Journal of Symbolic Computation_ 44, 7 (2009), 818–835.
  * Drton et al. (2009) Mathias Drton, Bernd Sturmfels, and Seth Sullivant. 2009\.  _Lectures on algebraic statistics_.
  * Eder and Faugère (2017) Christian Eder and Jean-Charles Faugère. 2017.  A survey on signature-based algorithms for computing Gröbner bases.  _Journal of Symbolic Computation_ 80 (2017), 719–784.
  * Emiris and Mantzaflaris (2012) Ioannis Z Emiris and Angelos Mantzaflaris. 2012.  Multihomogeneous resultant formulae for systems with scaled support.  _Journal of Symbolic Computation_ 47, 7 (2012), 820–842.
  * Emiris et al. (2021) Ioannis Z. Emiris, Angelos Mantzaflaris, and Elias P. Tsigaridas. 2021\.  Multilinear polynomial systems: Root isolation and bit complexity.  _Journal of Symbolic Computation_ 105 (July 2021), 145–164.
  * Emiris and Mourrain (1999) Ioannis Z. Emiris and Bernard Mourrain. 1999.  Matrices in elimination theory.  _Journal of Symbolic Computation_ 28, 1 (July 1999), 3–44.
  * Emiris and Rege (1994) Ioannis Z. Emiris and Ashutosh Rege. 1994.  Monomial bases and polynomial system solving (extended abstract). In _Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC ’94_. 114–122.
  * Ergür and de Wolff (2021) Alperen A. Ergür and Timo de Wolff. 2021.  A polyhedral homotopy algorithm for real zeros.  _arXiv:1910.01957 [cs, math]_ (Feb. 2021).
  * Esterov (2010) Alexander Esterov. 2010\.  Newton polyhedra of discriminants of projections.  _Discrete & Computational Geometry_ 44, 1 (2010), 96–148.
  * Faugère et al. (201) Jean-Charles Faugère, Mohab Safey El Din, and Pierre-Jean Spaenlehauer. 201.  Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In _Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation_. 257–264.
  * Faugère et al. (2014) Jean-Charles Faugère, Pierre-Jean Spaenlehauer, and Jules Svartz. 2014.  Sparse Gröbner bases: the unmixed case.  _Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC ’14_ (2014), 178–185.
  * Faugère and Svartz (2013) Jean-Charles Faugère and Jules Svartz. 2013.  Gröbner bases of ideals invariant under a commutative group: the non-modular case. In _Proceedings of the 38th international symposium on symbolic and algebraic computation_. 347–354.
  * Faugère (2002) Jean Charles Faugère. 2002\.  A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In _Proceedings of the 2002 international symposium on symbolic and algebraic computation_ _(ISSAC ’02)_. 75–83.
  * Faugère et al. (1993) Jean-Charles Faugère, Patrizia Gianni, Daniel Lazard, and Teo Mora. 1993.  Efficient computation of zero-dimensional Gröbner bases by change of ordering.  _Journal of Symbolic Computation_ 16, 4 (Oct. 1993), 329–344.
  * Faugère and Mou (2017) Jean-Charles Faugère and Chenqi Mou. 2017.  Sparse FGLM algorithms.  _Journal of Symbolic Computation_ 80 (May 2017), 538–569.
  * Faugère et al. (2011) Jean-Charles Faugère, Mohab Safey El Din, and Pierre-Jean Spaenlehauer. 2011.  Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity.  _Journal of Symbolic Computation_ 46, 4 (April 2011), 406–437.
  * Faugère et al. (2016) Jean-Charles Faugère, Mohab Safey El Din, and Thibaut Verron. 2016.  On the complexity of computing Gröbner bases for weighted homogeneous systems.  _Journal of Symbolic Computation_ 76 (Sept. 2016), 107–141.
  * Faugére (1999) Jean-Charles Faugére. 1999\.  A new efficient algorithm for computing Gröbner bases (F4).  _Journal of Pure and Applied Algebra_ 139, 1 (June 1999), 61–88.
  * Fulton (1993) William Fulton. 1993\.  _Introduction to toric varieties_.
  * Gatermann and Huber (2002) Karin Gatermann and Birkett Huber. 2002.  A family of sparse polynomial systems arising in chemical reaction systems.  _Journal of Symbolic Computation_ 33, 3 (2002), 275–305.
  * Gelfand et al. (2008) Israel M. Gelfand, Mikhail M. Kapranov, and Andrey V. Zelevinsky. 2008.  _Discriminants, resultants, and multidimensional determinants_.
  * Giusti et al. (2001) Marc Giusti, Grégoire Lecerf, and Bruno Salvy. 2001\.  A Gröbner free alternative for polynomial system solving.  _Journal of Complexity_ 17, 1 (2001), 154–211.
  * González-Vega (1991) Laureano González-Vega. 1991\.  A subresultant theory for multivariate polynomials. In _Proceedings of the 1991 international symposium on symbolic and algebraic computation_ _(ISSAC ’91)_. 79–85.  event-place: Bonn, West Germany.
  * Groh (2020) Friedemann Groh. 2020\.  Subdivisions for Macaulay formulas of sparse systems. In _Proceedings of the 45th international symposium on symbolic and algebraic computation_. 218–225.
  * Heintz et al. (2000) Joos Heintz, Teresa Krick, Susana Puddu, Juan Sabia, and Ariel Waissbein. 2000.  Deformation techniques for efficient polynomial equation solving.  _journal of complexity_ 16, 1 (2000), 70–109.
  * Herrero et al. (2013) María Isabel Herrero, Gabriela Jeronimo, and Juan Sabia. 2013\.  Affine solution sets of sparse polynomial systems.  _Journal of Symbolic Computation_ 51 (2013), 34–54.
  * Hochster (1972) Melvin Hochster. 1972\.  Rings of invariants of tori, Cohen-Macaulay rings generated by monomials, and polytopes.  _Annals of Mathematics_ 96, 2 (1972), 318–337.
  * Huber and Sturmfels (1995) Birkett Huber and Bernd Sturmfels. 1995.  A polyhedral method for solving sparse polynomial systems.  _Math. Comp._ 64, 212 (1995), 1541–1555.
  * Huber and Verschelde (2000) Birkett Huber and Jan Verschelde. 2000.  Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control.  _SIAM Journal on Control and Optimization_ 38, 4 (2000), 1265–1287.
  * Jindal et al. (2020) Gorav Jindal, Anurag Pandey, Himanshu Shukla, and Charilaos Zisopoulos. 2020.  How many zeros of a random sparse polynomial are real?. In _Proceedings of the 45th international symposium on symbolic and algebraic computation_. 273–280.
  * Khovanskii (1978) Askold G. Khovanskii. 1978\.  Newton polyhedra and the genus of complete intersections.  _Functional Analysis and Its Applications_ 12, 1 (Jan. 1978), 38–46.
  * Khovanskii (1991) Askold G. Khovanskii. 1991\.  _Fewnomials_. Vol. 88.
  * Kreuzer and Robbiano (2000) Martin Kreuzer and Lorenzo Robbiano. 2000.  _Computational commutative algebra 1_.
  * Kushnirenko (1976) Anatoliy G. Kushnirenko. 1976\.  Newton polytopes and the Bézout theorem.  _Functional Analysis and Its Applications_ 10, 3 (July 1976), 233–235.
  * Labahn et al. (2021) George Labahn, Mohab Safey El Din, Éric Schost, and Thi Xuan Vu. 2021.  Homotopy techniques for solving sparse column support determinantal polynomial systems.  _Journal of Complexity_ 66 (2021), 101557.
  * Lakshman and Lazard (1991) Yagati N. Lakshman and Daniel Lazard. 1991.  On the complexity of zero-dimensional algebraic systems. In _Effective methods in algebraic geometry_. Springer, 217–225.
  * Lazard (1981) Daniel Lazard. 1981\.  Resolution des systemes d’equations algebriques.  _Theoretical Computer Science_ 15, 1 (Jan. 1981), 77–110.
  * Lazard (1983) Daniel Lazard. 1983\.  Gröbner-Bases, gaussian elimination and resolution of systems of algebraic equations. In _Proceedings of the european computer algebra conference on computer algebra_ _(EUROCAL ’83)_. 146–156.
  * Macaulay (1916) Francis Sowerby Macaulay. 1916\.  _The algebraic theory of modular systems_.  Reprint in 1994.
  * Malajovich (2019) Gregorio Malajovich. 2019\.  Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric.  _Foundations of Computational Mathematics_ 19, 1 (2019), 1–53.
  * Massri (2016) César Massri. 2016\.  Solving a sparse system using linear algebra.  _Journal of Symbolic Computation_ 73 (March 2016), 157–174.
  * Monagan and Pearce (2017) Michael Monagan and Roman Pearce. 2017.  An algorithm for spliting polynomial systems based on F4. In _Proceedings of the international workshop on parallel symbolic computation_. 1–5.
  * Mondal (2021) Pinaki Mondal. 2021\.  _How many zeroes?: Counting solutions of systems of polynomials via toric geometry at infinity_. CMS/CAIMS Books in Mathematics, Vol. 2.
  * Morgan and Sommese (1987) Alexander Morgan and Andrew Sommese. 1987.  Computing all solutions to polynomial systems using homotopy continuation.  _Appl. Math. Comput._ 24, 2 (1987), 115–138.
  * Mou et al. (2021) Chenqi Mou, Yang Bai, and Jiahua Lai. 2021.  Chordal graphs in triangular decomposition in top-down style.  _Journal of Symbolic Computation_ 102 (2021), 108–131.
  * Mourrain (1999) Bernard Mourrain. 1999\.  A new criterion for normal form algorithms. In _Applied algebra, algebraic algorithms and error-correcting codes_ _(Lecture Notes in Computer Science)_ , Marc Fossorier, Hideki Imai, Shu Lin, and Alain Poli (Eds.). 430–442.
  * Mourrain and Pavone (2009) Bernard Mourrain and Jean Pascal Pavone. 2009.  Subdivision methods for solving polynomial equations.  _Journal of Symbolic Computation_ 44, 3 (2009), 292–306.
  * Pedersen and Sturmfels (1996) Paul Pedersen and Bernd Sturmfels. 1996.  Mixed monomial bases. In _Algorithms in algebraic geometry and applications_ _(Progress in Mathematics)_ , Laureano González-Vega and Tomás Recio (Eds.). 307–316.
  * Rojas (1999) J. Maurice Rojas. 1999\.  Solving degenerate sparse polynomial systems faster.  _Journal of Symbolic Computation_ 28, 1 (July 1999), 155–186.
  * Rouillier (1999) Fabrice Rouillier. 1999\.  Solving zero-dimensional systems through the rational univariate representation.  _Applicable Algebra in Engineering, Communication and Computing_ 9, 5 (1999), 433–461.
  * Sturmfels (1994) Bernd Sturmfels. 1994\.  On the Newton polytope of the resultant.  _Journal of Algebraic Combinatorics_ 3, 2 (April 1994), 207–236.
  * Sylvester (1840) James Joseph Sylvester. 1840\.  XXIII. A method of determining by mere inspection the derivatives from two equations of any degree.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ 16, 101 (1840), 132–135.
  * Szanto (2008) Agnes Szanto. 2008\.  Solving over-determined systems by the subresultant method (with an appendix by Marc Chardin).  _Journal of Symbolic Computation_ 43, 1 (Jan. 2008), 46–74.
  * Telen (2020a) Simon Telen. 2020a.  Numerical root finding via Cox rings.  _Journal of Pure and Applied Algebra_ 224, 9 (2020), 106367\.
  * Telen (2020b) Simon Telen. 2020b.  _Solving Systems of Polynomial Equations_.  Ph. D. Dissertation. KU Leuven, Leuven, Belgium.  Liras ID: LIRIAS1947881.
  * Telen et al. (2018) Simon Telen, Bernard Mourrain, and Marc van Barel. 2018\.  Solving polynomial systems via truncated normal forms.  _SIAM J. Matrix Anal. Appl._ 39, 3 (Jan. 2018), 1421–1447.
  * Tonelli-Cueto (2019) Josué Tonelli-Cueto. 2019\.  _Condition and homology in semialgebraic geometry_.  Doctoral Thesis. Technische Universität Berlin.
  * Traverso (1996) Carlo Traverso. 1996\.  Hilbert functions and the Buchberger algorithm.  _Journal of Symbolic Computation_ 22, 4 (1996), 355–376.
  * Wang et al. (2020) Dongming Wang, Rina Dong, and Chenqi Mou. 2020.  Decomposition of polynomial sets into characteristic pairs.  _Math. Comp._ 89, 324 (2020), 1993–2015.
  * Weyman (2003) Jerzy Weyman. 2003\.  _Cohomology of vector bundles and syzygies_.
  * Weyman and Zelevinsky (1994) Jerzy Weyman and Andrei Zelevinsky. 1994.  Determinantal formulae for multigraded resultants.  _Journal of Algebraic Geometry_ 3, 4 (1994), 569–597.