Algorithms in real algebraic geometry (Q5906950): Difference between revisions

The monograph gives a self-contained detailed exposition of the algorithmic real algebraic geometry. The first part of the book is intended to prepare the reader for understanding the main part, devoted to the algorithms. The preparatory topics include the theory of algebraically closed and real closed fields with quantifier elimination and transfer principles, the semi-algebraic sets and the related quadratic form theory, elements of topology culminating with the Oleinik-Petrovsky-Milnor-Thom upper bounds to the Betti numbers of real algebraic and semi-algebraic sets. The algorithmic problems discussed in the book are mainly real root counting, deciding the existence of solutions for systems of equalities and inequalities, computing the projections of semi-algebraic sets, deciding a sentence of the theory of real closed fields, eliminating quantifiers, and computing topological properties of algebraic and semi-algebraic sets. Among the particular algorithms studied in the book, one finds the Cauchy index theory, various methods for counting real roots and solving polynomial systems, the cylindrical decomposition algorithm, finding realizable sign conditions, computing roadmaps and connected components of algebraic and semi-algebraic sets. A special attention is paid to the complexity of the basic algorithms for linear algebra, remainder sequences, subresultant sequences, root counting methods. In general, the monograph is well written and will be useful both for beginners and for advanced readers, who work in real algebraic geometry or apply its methods in other fields.