Engineered Complete Intersections: Algorithmic Aspects

Overview & Synopsis

Engineered Complete Intersections (ECI's) are a class of sparse polynomial systems frequently arising in a number of contexts, both in pure mathematics (e.g. enumerative geometry) and applications (e.g. chemical reaction networks). Based on theoretical results given by the first author, we give several contributions. First we give a new effective technique to tropicalize such systems by generalizing the classical notion of mixed subdivisions introduced by Huber and Sturmfels (1995) to ECI's with the particular goal to efficiently count solutions of square systems of equations in ECI form. We further design a tropical homotopy continuation algorithm for computing such mixed subdivisions, inspired by Jensen (2016), Malajovich (2017) and Daisey and Ren (2024). Our techniques can be used to numerically solve such systems by coupling them with the algorithms introduced by Helminck, Henriksson and Ren (2024). Finally, we give an algorithm to compute Newton polytopes of eliminants of ECI's. This gives a new way to compute, for example, Newton polytopes of so-called A-discriminants. Coupled with evaluation-interpolation paradigms our algorithm gives an efficient approach to compute such eliminants. We implemented our algorithms in the form of a software package which we use to demonstrate their practical feasibility on a range of examples.