Algorithms in Real Algebraic Geometry

Title page Introduction 1 Algebraically Closed Fields 1.1 Definitions and First Properties 1.2 Euclidean Division and Greatest Common Divisor 1.3 Projection Theorem for Constructible Sets 1.4 Quantifier Elimination and the Transfer Principle 1.5 Bibliographical Notes 2 Real Closed Fields 2.1 Ordered, Real and Real Closed Fields 2.2 Real Root Counting 2.2.1 Descartes's Law of Signs and the Budan-Fourier Theorem 2.2.2 Sturm's Theorem and the Cauchy Index 2.3 Projection Theorem for Aigebraic Sets 2.4 Projection Theorem for Semi-Algebraic Sets 2.5 Applications 2.5.1 Quantifier Elimination and the Transfer Principle 2.5.2 Semi-Algebraic Functions 2.5.3 Extension of Semi-Algebraic Sets and Functions 2.6 Puiseux Series 2.7 Bibliographical Notes 3 Semi-Algebraic Sets 3.1 Topology 3.2 Semi-algebraically Connected Sets 3.3 Semi-algebraic Germs 3.4 Closed and Bounded Semi-algebraic Sets 3.5 Implicit Function Theorem 3.6 Bibliographical Notes 4 Algebra 4.1 Discriminant and subdiscriminant 4.2 Resultant and Subresultant Coefficients 4.2.1 Resultant 4.2.2 Subresultant coefficients 4.2.3 Subresultant coefficients and Cauchy Index 4.3 Quadratic Forms and Root Counting 4.3.1 Quadratic Forms 4.3.2 Hermite's Quadratic Form 4.4 Polynomial Ideals 4.4.1 Hilbert's Basis Theorem 4.4.2 Hilbert's Nullstellensatz 4.5 Zero-dimensional Systems 4.6 Multivariate Hermite's Quadratic Form 4.7 Projective Space and a Weak Bézout's Theorem 4.8 Bibliographical Notes 5 Decomposition of Semi-Algebraic Sets 5.1 Cylindrical Decomposition 5.2 Semi-algebraically Connected Components 5.3 Dimension 5.4 Semi-algebraic Description of Cells 5.5 Stratification 5.6 Simplicial Complexes 5.7 Triangulation 5.8 Hardt's Triviality Theorem and Consequences 5.9 Semi-algebraic Sard's Theorem 5.10 Bibliographical Notes 6 Elements of Topology 6.1 Simplicial Homology Theory 6.1.1 The Homology Groups of a Simplicial Complex 6.1.2 Simplicial Cohomology Theory 6.1.3 A Characterization of Hl in a Special Case 6.1.4 The Mayer-Vietoris Theorem 6.1.5 Chain Homotopy 6.1.6 The Simplicial Homology Groups Are Invariant Under Homeomorphism 6.2 Simplicial Homology of Closed and Bounded Semi-algebraic Sets 6.2.1 Definitions and First Properties 6.2.2 Homotopy 6.3 Homology of Certain Locally Closed Semi-Algebraic Sets 6.3.1 Homology of Closed Semi-algebraic Sets and of Sign Conditions 6.3.2 Homology of a Pair 6.3.3 Borel-Moore Homology 6.3.4 Euler-Poincaré Characteristic 6.4 Bibliographical Notes 7 Quantitative Semi-algebraic Geometry 7.1 Morse Theory 7.2 Sum of the Betti Numbers of Real Aigebraic Sets 7.3 Bounding the Betti Numbers of Realizations of Sign Conditions 7.4 Sum of the Betti Numbers of Closed Semi-algebraic Sets 7.5 Sum of the Betti Numbers of Semi-algebraic Sets 7.6 Bibliographical Notes 8 Complexity of Basic Algorithms 8.1 Definition of Complexity 8.2 Linear Aigebra 8.2.1 Size of Determinants 8.2.2 Evaluation of Determinants 8.2.3 Characteristic Polynomial 8.2.4 Signature of Quadratic Forms 8.3 Remainder Sequences and Subresultants 8.3.1 Remainder Sequences 8.3.2 Signed Subresultant Polynomials 8.3.3 Structure Theorem for Signed Subresultants 8.3.4 Size of Remainders and Subresultants 8.3.5 Specialization Properties of Subresultants 8.3.6 Subresultant Computation 8.4 Bibliographical Notes 9 Cauchy Index and Applications 9.1 Cauchy Index 9.1.1 Computing the Cauchy Index 9.1.2 Bezoutian and Cauchy Index 9.1.3 Signed Subresultant Sequence and Cauchy Index on an Interval 9.2 Hankel Matrices 9.2.1 Hankel Matrices and Rational Functions 9.2.2 Signature of Hankel Quadratic Forms 9.3 Number of Complex Roots with Negative Real Part 9.4 Bibliographical Notes 10 Real Roots 10.1 Bounds on Roots 10.2 Isolating Real Roots 10.3 Sign Determination 10.4 Roots in a Real Closed Field 10.5 Bibliographical Notes 11 Cylindrical Decomposition Algorithm 11.1 Computing the Cylindrical Decomposition 11.1.1 Outline of the Method 11.1.2 Details of the Lifting Phase 11.2 Decision Problem 11.3 Quantifier Elimination 11.4 Lower Bound for Quantifier Elimination 11.5 Computation of Stratifying Families 11.6 Topology of Curves 11.7 Restricted Elimination 11.8 Bibliographical Notes 12 Polynomial System Solving 12.1 A Few Results on Grôbner Bases 12.2 Multiplication Tables 12.3 Special Multiplication Table 12.4 Univariate Representation 12.5 Limits of the Solutions of a Polynomial System 12.6 Finding Points in Connected Components of Aigebraic Sets 12.7 Triangular Sign Determination 12.8 Computing the Euler-Poincaré Characteristic of an Aigebraic Set 12.9 Bibliographical Notes 13 Existential Theory of the Reals 13.1 Finding Realizable Sign Conditions 13.2 A Few Applications 13.3 Sample Points on an Aigebraic Set 13.4 Computing the Euler-Poincaré Characteristic of Sign Conditions 13.5 Bibliographical Notes 14 Quantifier Elimination 14.1 Aigorithm for the General Decision Problem 14.2 Quantifier Elimination 14.3 Local Quantifier Elimination 14.4 Global Optimization 14.5 Dimension of Semi-algebraic Sets 14.6 Bibliographical Notes 15 Computing Roadmaps and Connected Components of Algebraic Sets 15.1 Pseudo-critical Values and Connectedness 15.2 Roadmap of an Algebraic Set 15.3 Computing Connected Components of Algebraic Sets 15.4 Bibliographical Notes 16 Computing Roadmaps and Connected Components of Semi-algebraic Sets 16.1 Special Values 16.2 Uniform Roadmaps 16.3 Computing Connected Components of Sign Conditions 16.4 Computing Connected Components of a Semi-algebraic Set 16.5 Roadmap Aigorithm 16.6 Computing the First Betti Number of Semi-algebraic Sets 16.7 Bibliographical Notes References Index of Notation Index