A toolkit for algebra and geometry

摘要

This thesis deals with the efficient solution of systems of polynomial equations and inequalities, with particular emphasis on solutions over the reals. We describe the algorithms and data structures which form the basis of an implemented library of routines--a toolkit--for solving a variety of problems involving systems of multivariate polynomial equations and inequalities. The problems we are interested in solving can be broadly categorized as counting, enumerating, and answering queries about the common (real) solutions of such systems. We describe the application of the toolkit to problems in different areas including robotics, geometric modeling and geometric theorem proving. These problems raise interesting questions in their own right and we provide algorithmic solutions, of independent interest, to some of them. The two fundamental components of our toolkit are the resultant and the straight-line program. We use resultant-based algorithms for a variety of symbolic computations in the toolkit including reduction of a multivariate system to a univariate one via elimination, symbolic encoding of the common roots of a system of polynomial equations and determining the signs of such a system at the common roots of another. We describe the use of the straight-line program approach to reduce the symbolic complexity of such algorithms. The utility of these two ideas, i.e., resultant-based computations and straight-line programs is demonstrated in several problems: We demonstrate an efficient way to correctly count the number of real roots of a given system of equations. In geometric modeling, we describe the algorithms for the problem of implicit point location and predicates for geometry. We also provide an algorithm for efficiently solving triangular systems such as those arising in geometric theorem proving. We give necessary and sufficient conditions for theorem proving over algebraically closed fields as well as over the reals. These algorithms and conditions are combined to provide an efficient geometric theorem provide which we have successfully applied to various nontrivial theorems.