Algorithms in Real Algebraic Geometry

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

• ISBN13: 9783540009733
• ISBN10: 3540009736
• Format: Hardcover
• Copyright: 2003-09-01
• 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

0 Introduction	1	(8)
1 Algebraically Closed Fields	9	(16)
1.1 Definitions and First Properties	9	(3)
1.2 Euclidean Division and Greatest Common Divisor	12	(4)
1.3 Projection Theorem for Constructible Sets	16	(6)
1.4 Quantifier Elimination and the Transfer Principle	22	(2)
1.5 Bibliographical Notes	24	(1)
2 Real Closed Fields	25	(48)
2.1 Definitions and First Properties	25	(12)
2.2 Real Root Counting	37	(17)
2.2.1 Descartes's Law of Signs and the Budan-Fourier Theorem	37	(6)
2.2.2 The Cauchy Index	43	(7)
2.2.3 Sign Determination	50	(4)
2.3 Projection Theorem for Semi-Algebraic Sets	54	(6)
2.4 Applications	60	(4)
2.4.1 Quantifier Elimination and the Transfer Principle	60	(2)
2.4.2 Semi-Algebraic Functions	62	(1)
2.4.3 Extension of Semi-Algebraic Sets and Functions	63	(1)
2.5 Puiseux Series	64	(8)
2.6 Bibliographical Notes	72	(1)
3 Semi-Algebraic Sets	73	(18)
3.1 Topology	73	(3)
3.2 Semi-algebraically Connected Sets	76	(1)
3.3 Semi-algebraic Germs	77	(5)
3.4 Closed and Bounded Semi-algebraic Sets	82	(1)
3.5 Implicit Function Theorem	83	(6)
3.6 Bibliographical Notes	89	(2)
4 Algebra	91	(46)
4.1 Quadratic Forms and Root Counting	91	(12)
4.1.1 Quadratic Forms	91	(5)
4.1.2 Hermite's Quadratic Form and the Discriminant	96	(7)
4.2 Resultant and Subresultant Coefficients	103	(8)
4.3 Hilbert's Nullstellensatz	111	(10)
4.4 Zero-dimensional Systems	121	(6)
4.5 Multivariate Hermite's Quadratic Form	127	(4)
4.6 Projective Space and a Weak Bézout's Theorem	131	(5)
4.7 Bibliographical Notes	136	(1)
5 Decomposition of Semi-Algebraic Sets	137	(36)
5.1 Cylindrical Decomposition	137	(10)
5.2 Semi-algebraically Connected Components	147	(1)
5.3 Dimension	148	(2)
5.4 Semi-algebraic Description of Cells	150	(2)
5.5 Stratification	152	(6)
5.6 Simplicial Complexes	158	(2)
5.7 Triangulation	160	(4)
5.8 Hardt's Triviality Theorem and Consequences	164	(5)
5.9 Semi-algebraic Sard's Theorem	169	(3)
5.10 Bibliographical Notes	172	(1)
6 Elements of Topology	173	(28)
6.1 Simplicial Homology Theory	173	(17)
6.1.1 The Homology Groups of a Simplicial Complex	173	(4)
6.1.2 The Mayer-Vietoris Theorem	177	(2)
6.1.3 Chain Homotopy	179	(3)
6.1.4 The Simplicial Homology Groups Are Invariant Under Homeomorphism	182	(8)
6.2 Simplicial Homology of Closed and Bounded Semi-algebraic Sets	190	(7)
6.2.1 Definitions and First Properties	190	(3)
6.2.2 Homotopy	193	(2)
6.2.3 Homology Groups of Closed Semi-algebraic Sets and of Sign Conditions	195	(2)
6.3 Euler-Poincaré Characteristic	197	(3)
6.4 Bibliographical Notes	200	(1)
7 Quantitative Semi-algebraic Geometry	201	(40)
7.1 Morse Theory	201	(19)
7.2 Sum of the Betti Numbers of Real Algebraic Sets	220	(8)
7.3 Bounding the Betti Numbers of Realizations of Sign Conditions	228	(7)
7.4 Sum of the Betti Numbers of Closed Semi-algebraic Sets	235	(4)
7.5 Bibliographical Notes	239	(2)
8 Complexity of Basic Algorithms	241	(42)
8.1 Definition of Complexity	241	(11)
8.2 Linear Algebra	252	(11)
8.2.1 Size of Determinants	252	(2)
8.2.2 Evaluation of Determinants	254	(5)
8.2.3 Characteristic Polynomial	259	(3)
8.2.4 Signature of Quadratic Forms	262	(1)
8.3 Remainder Sequences and Subresultants	263	(19)
8.3.1 Remainder Sequences	263	(2)
8.3.2 Signed Subresultant Polynomials	265	(11)
8.3.3 Size of Remainders and Subresultants	276	(3)
8.3.4 Subresultant Computation	279	(3)
8.4 Bibliographical Notes	282	(1)
9 Cauchy Index and Applications	283	(38)
9.1 Cauchy Index	283	(18)
9.1.1 Signed Remainder Sequence and Cauchy Index	283	(1)
9.1.2 Signed Subresultant Coefficients and Cauchy Index	284	(6)
9.1.3 Bezoutian and Cauchy Index	290	(7)
9.1.4 Cauchy Index Computation	297	(1)
9.1.5 Signed Subresultant Sequence and Cauchy Index on an Interval	298	(3)
9.2 Hankel Matrices	301	(12)
9.2.1 Hankel Matrices and Rational Functions	302	(3)
9.2.2 Signature of Hankel Quadratic Forms	305	(8)
9.3 Number of Complex Roots with Negative Real Part	313	(6)
9.4 Bibliographical Notes	319	(2)
10 Real Roots	321	(44)
10.1 Bounds on Roots	321	(8)
10.2 Isolating Real Roots	329	(17)
10.3 Sign Determination	346	(12)
10.4 Roots in a Real Closed Field	358	(5)
10.5 Bibliographical Notes	363	(2)
11 Polynomial System Solving	365	(56)
11.1 A Few Results on Gröbner Bases	365	(7)
11.2 Multiplication Tables	372	(3)
11.3 Special Multiplication Table	375	(7)
11.4 Univariate Representation	382	(7)
11.5 Limits of the Solutions of a Polynomial System	389	(13)
11.6 Finding Points in Connected Components of Algebraic Sets	402	(12)
11.7 Computing the Euler-Poincaré Characteristic of an Algebraic Set	414	(5)
11.8 Bibliographical Notes	419	(2)
12 Cylindrical Decomposition Algorithm	421	(44)
12.1 Computing the Cylindrical Decomposition	422	(13)
12.1.1 Outline of the Method	422	(6)
12.1.2 Details of the Lifting Phase	428	(7)
12.2 Decision Problem	435	(8)
12.3 Quantifier Elimination	443	(4)
12.4 Computation of Stratifying Families	447	(2)
12.5 Topology of Curves	449	(10)
12.6 Restricted Elimination	459	(4)
12.7 Bibliographical Notes	463	(2)
13 Existential Theory of the Reals	465	(28)
13.1 Finding Realizable Sign Conditions	466	(10)
13.2 A Few Applications	476	(3)
13.3 Sample Points on an Algebraic Set	479	(9)
13.4 Computing the Euler-Poincaré Characteristic of Sign Conditions	488	(4)
13.5 Bibliographical Notes	492	(1)
14 Quantifier Elimination	493	(30)
14.1 Algorithm for the General Decision Problem	494	(13)
14.2 Quantifier Elimination	507	(5)
14.3 Local Quantifier Elimination	512	(5)
14.4 Dimension and Closure Semi-algebraic Sets	517	(4)
14.5 Bibliographical Notes	521	(2)
15 Computing Roadmaps and Connected Components of Algebraic Sets	523	(26)
15.1 Pseudo-critical Values and Connectedness	524	(2)
15.2 Roadmap of an Algebraic Set	526	(12)
15.3 Computing Connected Components of Algebraic Sets	538	(9)
15.4 Bibliographical Notes	547	(2)
16 Computing Roadmaps and Connected Components of Semi-algebraic Sets	549	(38)
16.1 Special Values	549	(8)
16.2 Uniform Roadmaps	557	(7)
16.3 Computing Connected Components of Sign Conditions	564	(6)
16.4 Computing Connected Components of a Semi-algebraic Set	570	(4)
16.5 Roadmap Algorithm	574	(10)
16.6 Bibliographical Notes	584	(3)
References	587	(8)
Index	595