Automatic Solver Generator for Systems of Laurent Polynomial Equations
Evgeniy Martyushev Snehal Bhayani Tomas Pajdla
In computer vision applications, the following problem often arises: Given a
family of (Laurent) polynomial systems with the same monomial structure but
varying coefficients, find a solver that computes solutions for any family
member as fast as possible. Under appropriate genericity assumptions, the
dimension and degree of the respective polynomial ideal remain unchanged for
each particular system in the same family. The state-of-the-art approach to
solving such problems is based on elimination templates, which are the
coefficient (Macaulay) matrices that encode the transformation from the initial
polynomials to the polynomials needed to construct the action matrix. Knowing
an action matrix, the solutions of the system are computed from its
eigenvectors. The important property of an elimination template is that it
applies to all polynomial systems in the family. In this paper, we propose a
new practical algorithm that checks whether a given set of Laurent polynomials
is sufficient to construct an elimination template. Based on this algorithm, we
propose an automatic solver generator for systems of Laurent polynomial
equations. The new generator is simple and fast; it applies to ideals with
positive-dimensional components; it allows one to uncover partial $p$-fold
symmetries automatically. 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 the solvers for
the following problems: optimal 3-view triangulation, semi-generalized hybrid
pose estimation and minimal time-of-arrival self-calibration. The experiments
on synthetic scenes show that our solvers are numerically accurate and either
comparable to or significantly faster than the state-of-the-art solvers.