|Title||Solving polynomial systems by matrix computations|
|Author(s)|| Bernard Mourrain|
|Text||B. Mourrain. Solving polynomial systems by matrix computations. Manuscript.
INRIA Sophia-Antipolis, France. Submitted for publication, 1997.|
|Type||Technical Report, Misc|
|Abstract||Two main approaches are used, nowadays, to compute the roots of a zero-dimensional polynomial system. The first one involves Gröbner basis computation, and applies to any zero-dimensional system. But, it is performed with exact arithmetic and, usually, big numbers appear during the computation. The other approach is based on resultant formulations and can be performed with floating point arithmetic. However, it applies only to generic situations, leading to singular problems in several systems coming from robotics and computational vision, for instance.|
In this paper, reinvestigating the resultant approach from the linear algebra point of view, we present a new algorithm, for computing the roots even in the non-generic cases. We analyze 3 types of resultant formulations, transform them in eigenvector problems, and apply special linear algebra operations on the matrix pencils, in order to reduce the root computation to a non-singular eigenvector problem.