Algorithms in Real Algebraic Geometry

Forsideomslag
Springer Science & Business Media, 2003 - 602 sider
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.

Fra bogen

Indhold

Algebraically Closed Fields
9
12 Euclidean Division and Greatest Common Divisor
12
13 Projection Theorem for Constructible Sets
16
14 Quantifier Elimination and the Transfer Principle
22
15 Bibliographical Notes
24
Real Closed Fields
25
22 Real Root Counting
37
222 The Cauchy Index
43
834 Subresultant Computation
279
84 Bibliographical Notes
282
Cauchy Index and Applications
283
912 Signed Subresultant Coefficients and Cauchy Index
284
913 Bezoutian and Cauchy Index
290
914 Cauchy Index Computation
297
915 Signed Subresultant Sequence and Cauchy Index on an Interval
298
92 Hankel Matrices
301

223 Sign Determination
50
23 Projection Theorem for Semi Algebraic Sets
54
24 Applications
60
242 SemiAlgebraic Functions
62
243 Extension of Semi Algebraic Sets and Functions
63
25 Puiseux Series
64
26 Bibliographical Notes
72
SemiAlgebraic Sets
73
32 Semialgebraically Connected Sets
76
33 Semialgebraic Germs
77
34 Closed and Bounded Semialgebraic Sets
82
35 Implicit Function Theorem
83
36 Bibliographical Notes
89
Algebra
91
412 Hermites Quadratic Form and the Discriminant
96
42 Resultant and Subresultant Coefficients
103
43 Hilberts Nullstellensatz
111
44 Zerodimensional Systems
121
45 Multivariate Hermites Quadratic Form
127
46 Projective Space and a Weak Bezouts Theorem
131
47 Bibliographical Notes
136
Decomposition of SemiAlgebraic Sets
137
52 Semialgebraically Connected Components
147
53 Dimension
148
54 Semialgebraic Description of Cells
150
55 Stratification
152
56 Simplicial Complexes
158
57 Triangulation
160
58 Hardts Triviality Theorem and Consequences
164
59 Semialgebraic Sards Theorem
169
Elements of Topology
173
612 The MayerVictor is Theorem
177
613 Chain Homotopy
179
614 The Simplicial Homology Groups Are Invariant Under Homeomorphism
182
62 Simplicial Homology of Closed and Bounded Semialgebraic Sets
190
622 Homotopy
193
623 Homology Groups of Closed Semialgebraic Sets and of Sign Conditions
195
63 EulerPoincare Characteristic
197
64 Bibliographical Notes
200
Quantitative Semialgebraic Geometry
201
72 Sum of the Betti Numbers of Real Algebraic Sets
220
73 Bounding the Betti Numbers of Realizations of Sign Conditions
228
74 Sum of the Betti Numbers of Closed Semialgebraic Sets
235
75 Bibliographical Notes
239
Complexity of Basic Algorithms
241
82 Linear Algebra
252
822 Evaluation of Determinants
254
823 Characteristic Polynomial
259
824 Signature of Quadratic Forms
262
83 Remainder Sequences and Subresultants
263
832 Signed Subresultant Polynomials
265
833 Size of Remainders and Subresultants
276
921 Hankel Matrices and Rational Functions
302
922 Signature of Hankel Quadratic Forms
305
93 Number of Complex Roots with Negative Real Part
313
94 Bibliographical Notes
319
Real Roots
321
102 Isolating Real Roots
329
103 Sign Determination
346
104 Roots in a Real Closed Field
358
105 Bibliographical Notes
363
Polynomial System Solving
365
112 Multiplication Tables
372
113 Special Multiplication Table
375
114 Univariate Representation
382
115 Limits of the Solutions of a Polynomial System
389
116 Finding Points in Connected Components of Algebraic Sets
402
117 Computing the EulerPoincare Characteristic of an Algebraic Set
414
118 Bibliographical Notes
419
Cylindrical Decomposition Algorithm
421
121 Computing the Cylindrical Decomposition
422
1212 Details of the Lifting Phase
428
122 Decision Problem
435
123 Quantifier Elimination
443
124 Computation of Stratifying Families
447
125 Topology of Curves
449
126 Restricted Elimination
459
127 Bibliographical Notes
463
Existential Theory of the Reals
465
131 Finding Realizable Sign Conditions
466
132 A Few Applications
476
133 Sample Points on an Algebraic Set
479
134 Computing the EulerPoincare Characteristic of Sign Conditions
488
135 Bibliographical Notes
492
Quantifier Elimination
493
141 Algorithm for the General Decision Problem
494
142 Quantifier Elimination
507
143 Local Quantifier Elimination
512
144 Dimension and Closure Semialgebraic Sets
517
145 Bibliographical Notes
521
Computing Roadmaps and Connected Components of Algebraic Sets
523
151 Pseudocritical Values and Connectedness
524
152 Roadmap of an Algebraic Set
526
153 Computing Connected Components of Algebraic Sets
538
154 Bibliographical Notes
547
Computing Roadmaps and Connected Components of Semialgebraic Sets
549
162 Uniform Roadmaps
557
163 Computing Connected Components of Sign Conditions
564
164 Computing Connected Components of a Semialgebraic Set
570
165 Roadmap Algorithm
574
166 Bibliographical Notes
584
References
587
Index
595
Copyright

Andre udgaver - Se alle

Almindelige termer og sætninger

Bibliografiske oplysninger