Mixed Subdivisions Suitable for the Greedy Canny–Emiris Formula

Description

The Canny–Emiris formula (Canny and Emiris in International symposium on applied algebra, algebraic algorithms, and error-correcting codes, 1993) gives the sparse resultant as the ratio of the determinant of a Sylvester-type matrix over a minor of it, both obtained via a mixed subdivision algorithm. In Checa and Emiris (International symposium on symbolic and algebraic computation, 2022), the authors gave an explicit class of mixed subdivisions for the greedy approach so that the formula holds, and the dimension of the constructed matrices is smaller than that of the subdivision algorithm, following the approach of Canny and Pedersen (Algorithm for the Newton resultant, 1993). Our method improves upon the dimensions of the matrices when the Newton polytopes are zonotopes and the systems are multihomogeneous. In this text, we provide more such cases, and we conjecture which might be the liftings providing minimal size of the resultant matrices. We also describe two applications of this formula, namely in computer vision and in the implicitization of surfaces, while offering the corresponding JULIA code. We finally introduce a novel tropical approach that leads to an alternative proof of a result in Checa and Emiris (2022).

Abstract

International audience

Additional details