Computing tropical resultants (Q2438901)

Let \(A = (A_1, \ldots, A_k)\) be a tuple describing an integer point configuration in \(\mathbb Z^n\). The sparse resultant \(R(A)\) of \(A\) is the closure in \((\mathbb C^*)^{A_1} \times \cdots \times (\mathbb C^*)^{A_k}\) of the collection of tuples of polynomials \((f_1, \ldots, f_k)\) such that \(f_1 = \cdots = f_k = 0\) has a solution in \((\mathbb C^*)^n\) and each \(f_i\) has support \(A_i\). \textit{B. Sturmfels} [J. Algebr. Comb. 3, No. 2, 207--236 (1994; Zbl 0798.05074)] showed that \(R(A)\) is irreducible and defined over \(\mathbb Q\). When \(R(A)\) is a hypersurface, its monic defining polynomial is called resultant polynomial of \(A\). Its Newton polytope is called the resultant poolytope of \(A\). In general, computing the resultant is difficult, even only its dimension. In the hypersurface case, Sturmfels also gave a combinatorial description of the resultant polytope from the Cayley configuration of \(A\), \(\text{Cay}(A)\). In the paper under review, the authors study tropical resultants and their computational efficiency. The tropical resultants are defined analogously for tropical polynomials. They show that the tropical resultant \(TR(A)\) coincides with the tropicalization of the resultant \(R(A)\). Furthermore, the tropical resultant is combinatorial in nature. They give a combinatorial description of it as a subfan of the secondary fan of \(\text{Cay}(A)\). From that they deduce a formula for codimension of the (tropical) resultant. They show that it can be computed in polynomial time using the cardinality matroid intersection algorithm. They also study specialized resultants and their tropicalizations. They develop algorithms for computing tropical resultants and tropicalization of specialized resultants.