Mireille Boutin: On solving polynomial equations with noisy coefficients: A case-study of the global position equations

Abstract.

Symbolic computational algebra methods allow one to reformulate problems defined by a system of polynomial equations in ways that can make them easier to analyze and solve. For example, one can try to eliminate certain variables or obtain a formulation of a lower degree in new variables. The question of how to effectively use these new formulations to deliver better results in practice still remains. In particular, it is not clear how to go from being able to find the solutions of an exact system of polynomial equations to finding the approximate solutions of a system with approximate, noisy or random coefficients.

As an illustration, we explore the system of degree two polynomial equations of the problem of global positioning, where a user (e.g., a car) with an imprecise clock receives the location signals of clock synchronized emitters (e.g., satellites). We show that the problem can be reformulated as a linear equation in certain monomials, and that the matrix representing the system is generically with 5 or more satellites. For the case of 4 satellites, we use algebraic elimination to obtain a single quadratic equation in one variable, which can be solved analytically. Analysis of these new formulations give us a complete understanding of exactly when the problem has a unique solution. We then explore ways to solve these new formulations of the global positioning problem and compare them, from a numerical standpoint where the data acquired is perturbed by noise, with the standard (iterative) approach.

This is joint work with Gregor Kemper and Rob Eggermont.