Algorithms in Real Algebraic Geometry

by Basu, Saugata; Pollack, Richard; Roy, Marie-Francoise

• ISBN13: 9783540330981
• ISBN10: 3540330984
• Edition: 2nd
• Format: Hardcover
• Copyright: 2006-08-18
• Publisher: Springer-Nature New York Inc

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	1	(350)
1 Algebraically Closed Fields	11	(18)
1.1 Definitions and First Properties	11	(3)
1.2 Euclidean Division and Greatest Common Divisor	14	(6)
1.3 Projection Theorem for Constructible Sets	20	(5)
1.4 Quantifier Elimination and the Transfer Principle	25	(2)
1.5 Bibliographical Notes	27	(2)
2 Real Closed Fields	29	(54)
2.1 Ordered, Real and Real Closed Fields	29	(15)
2.2 Real Root Counting	44	(13)
2.2.1 Descartes's Law of Signs and the Budan-Fourier Theorem	44	(8)
2.2.2 Sturm's Theorem and the Cauchy Index	52	(5)
2.3 Projection Theorem for Algebraic Sets	57	(6)
2.4 Projection Theorem for Semi-Algebraic Sets	63	(6)
2.5 Applications	69	(5)
2.5.1 Quantifier Elimination and the Transfer Principle	69	(2)
2.5.2 Semi-Algebraic Functions	71	(1)
2.5.3 Extension of Semi-Algebraic Sets and Functions	72	(2)
2.6 Puiseux Series	74	(7)
2.7 Bibliographical Notes	81	(2)
3 Semi-Algebraic Sets	83	(18)
3.1 Topology	83	(3)
3.2 Semi-algebraically Connected Sets	86	(1)
3.3 Semi-algebraic Germs	87	(6)
3.4 Closed and Bounded Semi-algebraic Sets	93	(1)
3.5 Implicit Function Theorem	94	(5)
3.6 Bibliographical Notes	99	(2)
4 Algebra	101	(58)
4.1 Discriminant and Subdiscriminant	101	(4)
4.2 Resultant and Subresultant Coefficients	105	(14)
4.2.1 Resultant	105	(5)
4.2.2 Subresultant Coefficients	110	(3)
4.2.3 Subresultant Coefficients and Cauchy Index	113	(6)
4.3 Quadratic Forms and Root Counting	119	(13)
4.3.1 Quadratic Forms	119	(8)
4.3.2 Hermite's Quadratic Form	127	(5)
4.4 Polynomial Ideals	132	(11)
4.4.1 Hilbert's Basis Theorem	132	(4)
4.4.2 Hilbert's Nullstellensatz	136	(7)
4.5 Zero-dimensional Systems	143	(6)
4.6 Multivariate Hermite's Quadratic Form	149	(4)
4.7 Projective Space and a Weak Bézout's Theorem	153	(4)
4.8 Bibliographical Notes	157	(2)
5 Decomposition of Semi-Algebraic Sets	159	(36)
5.1 Cylindrical Decomposition	159	(9)
5.2 Semi-algebraically Connected Components	168	(2)
5.3 Dimension	170	(2)
5.4 Semi-algebraic Description of Cells	172	(2)
5.5 Stratification	174	(7)
5.6 Simplicial Complexes	181	(2)
5.7 Triangulation	183	(3)
5.8 Hardt's Triviality Theorem and Consequences	186	(5)
5.9 Semi-algebraic Sard's Theorem	191	(3)
5.10 Bibliographical Notes	194	(1)
6 Elements of Topology	195	(42)
6.1 Simplicial Homology Theory	195	(26)
6.1.1 The Homology Groups of a Simplicial Complex	195	(4)
6.1.2 Simplicial Cohomology Theory	199	(2)
6.1.3 A Characterization of H¹ in a Special Case.	201	(5)
6.1.4 The Mayer-Vietoris Theorem	206	(3)
6.1.5 Chain Homotopy	209	(4)
6.1.6 The Simplicial Homology Groups Are Invariant Under Homeomorphism	213	(8)
6.2 Simplicial Homology of Closed and Bounded Semi-algebraic Sets	221	(5)
6.2.1 Definitions and First Properties	221	(2)
6.2.2 Homotopy	223	(3)
6.3 Homology of Certain Locally Closed Semi-Algebraic Sets	226	(10)
6.3.1 Homology of Closed Semi-algebraic Sets and of Sign Conditions	226	(2)
6.3.2 Homology of a Pair	228	(3)
6.3.3 Borel-Moore Homology	231	(3)
6.3.4 Euler-Poincaré Characteristic	234	(2)
6.4 Bibliographical Notes	236	(1)
7 Quantitative Semi-algebraic Geometry	237	(44)
7.1 Morse Theory	237	(19)
7.2 Sum of the Betti Numbers of Real Algebraic Sets	256	(6)
7.3 Bounding the Betti Numbers of Realizations of Sign Conditions	262	(6)
7.4 Sum of the Betti Numbers of Closed Semi-algebraic Sets	268	(5)
7.5 Sum of the Betti Numbers of Semi-algebraic Sets	273	(7)
7.6 Bibliographical Notes	280	(1)
8 Complexity of Basic Algorithms	281	(42)
8.1 Definition of Complexity	281	(11)
8.2 Linear Algebra	292	(9)
8.2.1 Size of Determinants	292	(2)
8.2.2 Evaluation of Determinants	294	(5)
8.2.3 Characteristic Polynomial	299	(1)
8.2.4 Signature of Quadratic Forms	300	(1)
8.3 Remainder Sequences and Subresultants	301	(21)
8.3.1 Remainder Sequences	301	(2)
8.3.2 Signed Subresultant Polynomials	303	(4)
8.3.3 Structure Theorem for Signed Subresultants	307	(7)
8.3.4 Size of Remainders and Subresultants	314	(2)
8.3.5 Specialization Properties of Subresultants	316	(1)
8.3.6 Subresultant Computation	317	(5)
8.4 Bibliographical Notes	322	(1)
9 Cauchy Index and Applications	323	(28)
9.1 Cauchy Index	323	(10)
9.1.1 Computing the Cauchy Index	323	(3)
9.1.2 Bezoutian and Cauchy Index	326	(4)
9.1.3 Signed Subresultant Sequence and Cauchy Index on an Interval	330	(3)
9.2 Hankel Matrices	333	(11)
9.2.1 Hankel Matrices and Rational Functions	334	(3)
9.2.2 Signature of Hankel Quadratic Forms	337	(7)
9.3 Number of Complex Roots with Negative Real Part	344	(6)
9.4 Bibliographical Notes	350	(1)
10 Real Roots	351	(52)
10.1 Bounds on Roots	351	(9)
10.2 Isolating Real Roots	360	(23)
10.3 Sign Determination	383	(14)
10.4 Roots in a Real Closed Field	397	(4)
10.5 Bibliographical Notes	401	(2)
11 Cylindrical Decomposition Algorithm	403	(42)
11.1 Computing the Cylindrical Decomposition	404	(11)
11.1.1 Outline of the Method	404	(4)
11.1.2 Details of the Lifting Phase	408	(7)
11.2 Decision Problem	415	(8)
11.3 Quantifier Elimination	423	(3)
11.4 Lower Bound for Quantifier Elimination	426	(2)
11.5 Computation of Stratifying Families	428	(2)
11.6 Topology of Curves	430	(10)
11.7 Restricted Elimination	440	(4)
11.8 Bibliographical Notes	444	(1)
12 Polynomial System Solving	445	(60)
12.1 A Few Results on Graner Bases	445	(6)
12.2 Multiplication Tables	451	(5)
12.3 Special Multiplication Table	456	(6)
12.4 Univariate Representation	462	(9)
12.5 Limits of the Solutions of a Polynomial System	471	(12)
12.6 Finding Points in Connected Components of Algebraic Sets	483	(12)
12.7 Triangular Sign Determination	495	(3)
12.8 Computing the Euler-Poincaré Characteristic of an Algebraic Set	498	(5)
12.9 Bibliographical Notes	503	(2)
13 Existential Theory of the Reals	505	(28)
13.1 Finding Realizable Sign Conditions	506	(10)
13.2 A Few Applications	516	(3)
13.3 Sample Points on an Algebraic Set	519	(9)
13.4 Computing the Euler-Poincaré Characteristic of Sign Conditions	528	(4)
13.5 Bibliographical Notes	532	(1)
14 Quantifier Elimination	533	(30)
14.1 Algorithm for the General Decision Problem	534	(13)
14.2 Quantifier Elimination	547	(4)
14.3 Local Quantifier Elimination	551	(6)
14.4 Global Optimization	557	(1)
14.5 Dimension of Semi-algebraic Sets	558	(4)
14.6 Bibliographical Notes	562	(1)
15 Computing Roadmaps and Connected Components of Algebraic Sets	563	(30)
15.1 Pseudo-critical Values and Connectedness	564	(4)
15.2 Roadmap of an Algebraic Set	568	(12)
15.3 Computing Connected Components of Algebraic Sets	580	(12)
15.4 Bibliographical Notes	592	(1)
16 Computing Roadmaps and Connected Components of Semi-algebraic Sets	593	(42)
16.1 Special Values	593	(8)
16.2 Uniform Roadmaps	601	(7)
16.3 Computing Connected Components of Sign Conditions	608	(6)
16.4 Computing Connected Components of a Semi-algebraic Set	614	(3)
16.5 Roadmap Algorithm	617	(10)
16.6 Computing the First Betti Number of Semi-algebraic Sets	627	(6)
16.7 Bibliographical Notes	633	(2)
References	635	(10)
Index of Notation	645	(10)
Index	655