You are here

Algorithms in Real Algebraic Geometry

Saugata Basu, Richard Pollack, and Marie-Françoise Roy
Springer Verlag
Publication Date: 
Number of Pages: 
Algorithms and Computation in Mathematics 10
[Reviewed by
Darren Glass
, on

One of the ironies in mathematical terminology is that it is simpler to deal with complex numbers is simpler than to limit ourselves to dealing with real numbers. For example, all polynomials of degree n have n complex roots (at least when counted with multiplicity), but the question of how many of these roots are real is far more subtle. This "real root counting problem" is one of the main problems under consideration in Algorithms in Real Algebraic Geometry by Saugata Basu, Richard Pollack, and Marie-Françoise Roy. The second edition of the book was recently released by Springer-Verlag and, as with the first edition, the authors have posted an interactive version of the book on each of their websites (Basu's website can be found here, for example).

The book attempts to be self-contained and for the most part the authors succeed at this attempt. The first seven chapters of the book contain background material on algebraically closed fields, real closed fields, the interplay between geometry and logic, and elementary algebraic topology. The most critical objects introduced are semi-algebraic sets, which are subsets of R n defined by a finite number of polynomial inequalities. These sets can be shown to always have a finite number of connected components, and the question of determining algorithmically how many components there are is a natural extension of the real root counting problem.

After discussing some aspects of complexity theory, the authors then get into the meat of the book, which discusses in depth several algorithmic problems, such as deciding the existence of solutions of systems of inequalities, eliminating quantifiers, computing topological properties of semi-algebraic sets, and determining what happens when you restrict semi-algebraic sets to lower dimensions, in addition to the aforementioned real roots counting problem.

Basu, Pollack, and Roy have written a detailed book with quite a few examples and a large number of bibliographic references. The exposition is dense but readable, and while there is a larger number of typos and misspellings than I would expect from a book in its second edition, the authors do keep a list of errata on their website, to which I went the few times that a typo made the text hard to follow. The websites also contain implementations of several of the algorithms in the book which this reviewer found particularly illuminating. Algorithms in Real Algebraic Geometry is not an easy read, but it is a worthwhile one for anyone interested in learning about this field.

Darren Glass is an assistant professor of mathematics at Gettysburg College whose interests in algebraic geometry typically stay in characteristic p. He can be reached at

 Introduction.- 1 Algebraically Closed Fields.- 2 Real Closed Fields.- 3 Semi-Algebraic Sets.- 4 Algebra.- 5 Decomposition of Semi-Algebraic Sets.- 6 Elements of Topology.- 7 Quantitative Semi-Algebraic Geometry.- 8 Complexity of Basic Algorithms.- 9 Cauchy Index and Applications.- 10 Real Roots.- 11 Cylindrical Decomposition Algorithm.- 12 Polynomial System Solving.- 13 Existential Theory of the Reals.- 14 Quantifier Elimination.- 15 Computing Roadmaps and Connected Components of Algebraic Sets.- 16 Computing Roadmaps and Connected Components of Semi-Algebraic Sets.- References.- Index of Notation.- Index.