Many problems in applied science require solving families of (Laurent) polynomial systems that share a monomial structure but have varying coefficients. The state-of-the-art approach uses elimination templates — coefficient (Macaulay) matrices that encode the transformation from the original polynomials to the polynomials needed to construct the action matrix. Knowing an action matrix, the solutions of the system are computed from its eigenvectors. A key advantage of this approach is that a single template generalizes to an entire family. In this paper, we propose a new practical algorithm for verifying whether a given set of Laurent polynomials is sufficient to construct an elimination template. Based on this algorithm, we present an automatic generator for creating efficient solvers for systems of Laurent polynomial equations. Our proposed generator offers several advantages: it is conceptually simple and fast; it naturally handles ideals with positive-dimensional components; and it can automatically uncover partial p -fold symmetries. We test our generator on various minimal problems, mostly in geometric computer vision. The speed of the generated solvers exceeds the state-of-the-art in most cases. In particular, we propose solvers for the following problems: optimal 3-view triangulation, semi-generalized hybrid pose estimation, and minimal time-of-arrival self-calibration. Experiments on synthetic scenes demonstrate that our solvers are numerically accurate and either comparable to or significantly faster than existing alternatives.
Martyushev et al. (Tue,) studied this question.