Algorithms in Real Algebraic GeometrySpringer 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
Resultater 6-10 af 64
Side 40
Denne sides indhold er desværre begrænset..
Denne sides indhold er desværre begrænset..
Side 44
Denne sides indhold er desværre begrænset..
Denne sides indhold er desværre begrænset..
Side 48
Denne sides indhold er desværre begrænset..
Denne sides indhold er desværre begrænset..
Side 54
Denne sides indhold er desværre begrænset..
Denne sides indhold er desværre begrænset..
Side 60
Denne sides indhold er desværre begrænset..
Denne sides indhold er desværre begrænset..
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 |
595 | |
Andre udgaver - Se alle
Algorithms in Real Algebraic Geometry Saugata Basu,Richard Pollack,Marie-Françoise Coste-Roy Begrænset visning - 2007 |
Algorithms in Real Algebraic Geometry Saugata Basu,Richard Pollack,Marie-Françoise Roy Begrænset visning - 2006 |
Algorithms in Real Algebraic Geometry Saugata Basu,Richard Pollack,Marie-Françoise Coste-Roy Begrænset visning - 2013 |
Almindelige termer og sætninger
algebraic set analysis of Algorithm arithmetic operations Betti numbers bitsizes Bounded Algebraic Cauchy index cells Chapter coefficients complexity analysis consider Corollary critical point curve segments cylindrical decomposition denote dimension do(k domain D contained Euler-Poincaré characteristic exists finite number finite set follows Gröbner basis Hence homeomorphic Input integral domain intermediate computations Lemma linear matrix monomials multiplication table non-empty non-zero Notation Note output are bounded P₁ Parametrized polynomial system polynomials are bounded polynomials of degree projection Proof of correctness Proposition prove Quantifier Elimination quantifier free formula real closed field real roots realizable sign conditions respectively ring roadmap sample points semi semi-algebraic function semi-algebraic homeomorphism semi-algebraic set semi-algebraic subset semi-algebraically connected component set of polynomials Sign Determination Sign(P signed remainder sequence signed subresultant simplicial complex Structure Sturm-query Triangular Thom Encoding univariate polynomial V(Der(P variables X₁ zero