Polynomial Solvers for Saturated Ideals

Abstract:
In this paper we present a new method for creating polynomial
solvers for problems where a (possibly infinite) subset
of the solutions are undesirable or uninteresting. These
solutions typically arise from simplifications made during
modeling, but can also come from degeneracies which are
inherent to the geometry of the original problem.
The proposed approach extends the standard action matrix
method to saturated ideals. This allows us to add constraints
that some polynomials should be non-zero on the
solutions. This does not only offer the possibility of improved
performance by removing superfluous solutions, but
makes a larger class of problems tractable. Previously,
problems with infinitely many solutions could not be solved
directly using the action matrix method as it requires a
zero-dimensional ideal. In contrast we only require that
after removing the unwanted solutions only finitely many
remain. We evaluate our method on three applications, optimal
triangulation, time-of-arrival self-calibration and optimal
vanishing point estimation.