Algorithms in Real Algebraic Geometry

by Basu, Saugata; Pollack, Richard; Coste-roy, Marie-françoise

• ISBN13: 9783540280200
• ISBN10: 3540280200
• Format: Hardcover
• Copyright: 2016-01-21
• Publisher: Springer Verlag

Summary

The algorithmic problems of real algebraic geometry such as real root counting, deciding the existence of solutions of systems of polynomial equations and inequalities, or deciding whether two points belong in the same connected component of a semi-algebraic set occur in many contexts. In this first-ever graduate textbook on the algorithmic aspects of real algebraic geometry, the main ideas and techniques presented form a coherent and rich body of knowledge, linked to many areas of mathematics and computing.Mathematicians already aware of real algebraic geometry will find relevant information about the algorithmic aspects, and researchers in computer science and engineering will find the required mathematical background.Being self-contained the book is accessible to graduate students and even, for invaluable parts of it, to undergraduate students.

Table of Contents

Introduction	p. 1
Algebraically Closed Fields	p. 9
Definitions and First Properties	p. 9
Euclidean Division and Greatest Common Divisor	p. 12
Projection Theorem for Constructible Sets	p. 16
Quantifier Elimination and the Transfer Principle	p. 22
Bibliographical Notes	p. 24
Real Closed Fields	p. 25
Definitions and First Properties	p. 25
Real Root Counting	p. 37
Descartes's Law of Signs and the Budan-Fourier Theorem	p. 37
The Cauchy Index	p. 43
Sign Determination	p. 50
Projection Theorem for Semi-Algebraic Sets	p. 54
Applications	p. 60
Quantifier Elimination and the Transfer Principle	p. 60
Semi-Algebraic Functions	p. 62
Extension of Semi-Algebraic Sets and Functions	p. 63
Puiseux Series	p. 64
Bibliographical Notes	p. 72
Semi-Algebraic Sets	p. 73
Topology	p. 73
Semi-algebraically Connected Sets	p. 76
Semi-algebraic Germs	p. 77
Closed and Bounded Semi-algebraic Sets	p. 82
Implicit Function Theorem	p. 83
Bibliographical Notes	p. 89
Algebra	p. 91
Quadratic Forms and Root Counting	p. 91
Quadratic Forms	p. 91
Hermite's Quadratic Form and the Discriminant	p. 96
Resultant and Subresultant Coefficients	p. 103
Hilbert's Nullstellensatz	p. 111
Zero-dimensional Systems	p. 121
Multivariate Hermite's Quadratic Form	p. 127
Projective Space and a Weak Bézout's Theorem	p. 131
Bibliographical Notes	p. 136
Decomposition of Semi-Algebraic Sets	p. 137
Cylindrical Decomposition	p. 137
Semi-algebraically Connected Components	p. 147
Dimension	p. 148
Semi-algebraic Description of Cells	p. 150
Stratification	p. 152
Simplicial Complexes	p. 158
Triangulation	p. 160
Hardt's Triviality Theorem and Consequences	p. 164
Semi-algebraic Sard's Theorem	p. 169
Bibliographical Notes	p. 172
Elements of Topology	p. 173
Simplicial Homology Theory	p. 173
The Homology Groups of a Simplicial Complex	p. 173
The Mayer-Vietoris Theorem	p. 177
Chain Homotopy	p. 179
The Simplicial Homology Groups Are Invariant Under Homeomorphism	p. 182
Simplicial Homology of Closed and Bounded Semi-algebraic Sets	p. 190
Definitions and First Properties	p. 190
Homotopy	p. 193
Homology Groups of Closed Semi-algebraic Sets and of Sign Conditions	p. 195
Euler-Poincaré Characteristic	p. 197
Bibliographical Notes	p. 200
Quantitative Semi-algebraic Geometry	p. 201
Morse Theory	p. 201
Sum of the Betti Numbers of Real Algebraic Sets	p. 220
Bounding the Betti Numbers of Realizations of Sign Conditions	p. 228
Sum of the Betti Numbers of Closed Semi-algebraic Sets	p. 235
Bibliographical Notes	p. 239
Complexity of Basic Algorithms	p. 241
Definition of Complexity	p. 241
Linear Algebra	p. 252
Size of Determinants	p. 252
Evaluation of Determinants	p. 254
Characteristic Polynomial	p. 259
Signature of Quadratic Forms	p. 262
Remainder Sequences and Subresultants	p. 263
Remainder Sequences	p. 263
Signed Subresultant Polynomials	p. 265
Size of Remainders and Subresultants	p. 276
Subresultant Computation	p. 279
Bibliographical Notes	p. 282
Cauchy Index and Applications	p. 283
Cauchy Index	p. 283
Signed Remainder Sequence and Cauchy Index	p. 283
Signed Subresultant Coefficients and Cauchy Index	p. 284
Bezoutian and Cauchy Index	p. 290
Cauchy Index Computation	p. 297
Signed Subresultant Sequence and Cauchy Index on an Interval	p. 298
Hankel Matrices	p. 301
Hankel Matrices and Rational Functions	p. 302
Signature of Hankel Quadratic Forms	p. 305
Number of Complex Roots with Negative Real Part	p. 313
Bibliographical Notes	p. 319
Real Roots	p. 321
Bounds on Roots	p. 321
Isolating Real Roots	p. 329
Sign Determination	p. 346
Roots in a Real Closed Field	p. 358
Bibliographical Notes	p. 363
Polynomial System Solving	p. 365
A Few Results on Gröbner Bases	p. 365
Multiplication Tables	p. 372
Special Multiplication Table	p. 375
Univariate Representation	p. 382
Limits of the Solutions ofa Polynomial System	p. 389
Finding Points in Connected Components of Algebraic Sets	p. 402
Computing the Euler-Poincaré Characteristic of an Algebraic Set	p. 414
Bibliographical Notes	p. 419
Cylindrical Decomposition Algorithm	p. 421
Computing the Cylindrical Decomposition	p. 422
Outline of the Method	p. 422
Details of the Lifting Phase	p. 428
Decision Problem	p. 435
Quantifier Elimination	p. 443
Computation of Stratifying Families	p. 447
Topology of Curves	p. 449
Restricted Elimination	p. 459
Bibliographical Notes	p. 463
Existential Theory of the Reals	p. 465
Finding Realizable Sign Conditions	p. 466
A Few Applications	p. 476
Sample Points on an Algebraic Set	p. 479
Computing the Euler-Poincaré Characteristic of Sign Conditions	p. 488
Bibliographical Notes	p. 492
Quantifier Elimination	p. 493
Algorithm for the General Decision Problem	p. 494
Quantifier Elimination	p. 507
Local Quantifier Elimination	p. 512
Dimension and Closure Semi-algebraic Sets	p. 517
Bibliographical Notes	p. 521
Computing Roadmaps and Connected Components of Algebraic Sets	p. 523
Pseudo-critical Values and Connectedness	p. 524
Roadmap of an Algebraic Set	p. 526
Computing Connected Components of Algebraic Sets	p. 538
Bibliographical Notes	p. 547
Computing Roadmaps and Connected Components of Semi-algebraic Sets	p. 549
Special Values	p. 549
Uniform Roadmaps	p. 557
Computing Connected Components of Sign Conditions	p. 564
Computing Connected Components of a Semi-algebraic Set	p. 570
Roadmap Algorithm	p. 574
Bibliographical Notes	p. 584
References	p. 587
Index	p. 595
Table of Contents provided by Publisher. All Rights Reserved.