Basu S., Pollack R., Roy M.-F. Algorithms in Real Algebraic Geometry

Springer, 2006. — 664 p.Since a real univariate polynomial does not always have real roots, a very natural algorithmic problem, is to design a method to count the number of real roots of a given polynomial (and thus decide whether it has any). The real root counting problem plays a key role in nearly all the algorithms in real algebraic geometry studied in this book.
Much of mathematics is algorithmic, since the proofs of many theorems provide a finite procedure to answer some question or to calculate something. A classic example of this is the proof that any pair of real univariate polynomials (P,Q) have a greatest common divisor by giving a finite procedure for constructing the greatest common divisor of (P,Q), namely the euclidean remainder sequence. However, different procedures to solve a given problem differ in how much calculation is required by each to solve that problem. To understand what is meant by how much calculation is required, one needs a fuller understanding of what an algorithm is and what is meant by its complexity. This will be discussed at the beginning of the second part of the book, in Chapter 8.
This book is intended to be self contained, assuming only that the reader has a basic knowledge of linear algebra and the rudiments of a basic course in algebra through the definitions and basic properties of groups, rings and fields, and in topology through the elementary properties of closed, open, compact and connected sets.
There are many other aspects of real algebraic geometry that are not considered in this book. The reader who wants to pursue the many aspects of real algebraic geometry beyond the introduction to the small part of it that we provide is encouraged to study other text books [26, 95, 5]. There is also a great deal of material about algorithms in real algebraic geometry that we are not covering in this book. To mention but a few: fewnomials, effective positivstellensatz, semi-definite programming, complexity of quadratic maps and quadratic sets.
We have tried to keep our style as informal as possible. Rather than giving bibliographic references and footnotes in the body of the text, we have a section at the end of each chapter giving a brief description of the history of the results with a few of the relevant bibliographic citations. We only try to indicate where, to the best of our knowledge, the main ideas and results appear for the first time, and do not describe the full history and bibliography. We also list below the references containing the material we have used directly.
In terms of existing implementation of the algorithms described in the book, the current situation can be roughly summarized as follows: algorithms appearing in Chapters 8 to 12, or more efficient versions based on similar ideas, have been implemented (see a few references below). For most of the algorithms presented in Chapter 13 to 16, there is no implementation at all. The reason for that is that the methods developed are well adapted to complexity results but are not adapted to efficient implementation. Most algorithms from Chapters 8 to 11 are quite classical and have been implemented several times. We refer to [40] since it is a recent implementation based directly on [20]. It uses in part the work presented in [29]. A very efficient variant of the real root isolation algorithm in the monomial basis in Chapter 10 is described in [138]. Cylindrical algebraic decomposition discussed in Chapter 11 has also been implemented many times, see for example [46, 30, 151]. We refer to [71] for an implementation of an algorithm computing the topology of real algebraic curves close to the one we present in Chapter 11 . About algorithms discussed in Chapter 12, most computer algebra systems include Grobner basis computations. Particularly efficient Grobner basis computations, based on algorithms not described in the book, can be found in [59]. A very efficient rational univariate representation can be found in [135]. Computing a point in every connected component of an algebraic set based on critical point method techniques is done efficiently in [143], based on the algorithms developed in [8, 144].Algebraically Closed Fields
Real Closed Fields
Semi-Algebraic Sets
Algebra
Decomposition of Semi-Algebraic Sets
Elements of Topology
Quantitative Semi-algebraic Geometry
Complexity of Basic Algorithms
Cauchy Index and Applications
Real Roots
Cylindrical Decomposition Algorithm
Polynomial System Solving
Existential Theory of the Reals
Quantifier Elimination
Computing Roadmaps and Connected Components of Algebraic Sets
Computing Roadmaps and Connected Components of Semialgebraic Sets