第1页 / 共664页
第2页 / 共664页
第3页 / 共664页
第4页 / 共664页
第5页 / 共664页
第6页 / 共664页
第7页 / 共664页
第8页 / 共664页
实代数几何算法.pdf
front-matter
1Introduction
2Algebraically Closed Fields
3Real Closed Fields
4Semi-Algebraic Sets
5Algebra
6Decomposition of Semi-Algebraic Sets
7Elements of Topology
8Quantitative Semi-algebraic Geometry
9Complexity of Basic Algorithms
10Cauchy Index and Applications
11Real Roots
12Cylindrical Decomposition Algorithm
13Polynomial System Solving
14Existential Theory of the Reals
15Quantifier Elimination
16Computing Roadmaps and Connected Components of Algebraic Sets
17Computing Roadmaps and Connected Components of Semi-algebraic Sets
back-matter
Algorithms and Computation
in Mathematics • Volume 10
Editors
Arjeh M. Cohen Henri Cohen
David Eisenbud Michael F. Singer
Bernd Sturmfels
Saugata Basu
Richard Pollack
Marie-Françoise Roy
Algorithms in
Real Algebraic
Geometry
Second Edition
With 37 Figures
123
Saugata Basu
Georgia Institute of Technology
School of Mathematics
Atlanta, GA 30332-0160
USA
e-mail: saugata@math.gatech.edu
Richard Pollack
Courant Institute of
Mathematical Sciences
251 Mercer Street
New York, NY 10012
USA
e-mail: pollack@cims.nyu.edu
Marie-Françoise Roy
IRMAR Campus de Beaulieu
Université de Rennes I
35042 Rennes cedex
France
e-mail: Marie-Francoise.Roy@univ-rennes1.fr
Library of Congress Control Number: 2006927110
Mathematics Subject Classification (2000): 14P10, 68W30, 03C10, 68Q25, 52C45
ISSN 1431-1550
ISBN-10 3-540-33098-4 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-33098-1 Springer Berlin Heidelberg New York
ISBN 3-540-00973-6 1st edition Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material
is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication
of this publication or parts thereof is permitted only under the provisions of the German Copyright
Law of September 9, 1965, in its current version, and permission for use must always be obtained
from Springer. Violations are liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springer.com
© Springer-Verlag Berlin Heidelberg 2003, 2006
Printed in Germany
The use of general descriptive names, registered names, trademarks, etc. in this publication does not
imply, even in the absence of a specific statement, that such names are exempt from the relevant pro-
tective laws and regulations and therefore free for general use.
Typeset by the authors using a Springer LATEX macro package
Production: LE-TEX Jelonek, Schmidt & Vöckler GbR, Leipzig
Cover design: design & production GmbH, Heidelberg
Printed on acid-free paper
46/3100YL - 5 4 3 2 1 0
Table of Contents
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Algebraically Closed Fields . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
1.1 Definitions and First Properties
. . . . . .
1.2 Euclidean Division and Greatest Common Divisor
1.3 Projection Theorem for Constructible Sets
. . . . . . . . . . .
1.4 Quantifier Elimination and the Transfer Principle . . . . . . .
1.5 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
2 Real Closed Fields
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
2.1 Ordered, Real and Real Closed Fields
2.2 Real Root Counting . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Descartes’s Law of Signs and the Budan-Fourier The-
orem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Sturm’s Theorem and the Cauchy Index . . . . . . . .
2.3 Projection Theorem for Algebraic Sets . . . . . . . . . . . . . .
2.4 Projection Theorem for Semi-Algebraic Sets
. . . . . . . . . .
2.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1 Quantifier Elimination and the Transfer Principle
. .
2.5.2 Semi-Algebraic Functions . . . . . . . . . . . . . . . . . .
2.5.3 Extension of Semi-Algebraic Sets and Functions
. . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Puiseux Series
2.7 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
3
Semi-Algebraic Sets
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Semi-algebraically Connected Sets . . . . . . . . . . . . . . . . .
3.3 Semi-algebraic Germs . . . . . . . . . . . . . . . . . . . . . . . . .
1
11
11
14
20
25
27
29
29
44
44
52
57
63
69
69
71
72
74
81
83
83
86
87
VI
Table of Contents
3.4 Closed and Bounded Semi-algebraic Sets
. . . . . . . . . . . .
3.5 Implicit Function Theorem . . . . . . . . . . . . . . . . . . . . .
3.6 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
Su
4.2.1 Resultant
4.2.2 Subresultant
4.2.3 Subresultant
Co
Co
4.1 Discriminant and
4.2 Resultant and Subresultant Coefficients
4 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
bdiscriminant . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
efficients
. . . . . . . . . . . . . . . . . .
efficients and Cauchy Index . . . . . .
4.3 Quadratic Forms and Root Counting . . . . . . . . . . . . . . .
4.3.1 Quadratic Forms
. . . . . . . . . . . . . . . . . . . . . . .
4.3.2 Hermite’s Quadratic Form . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Hilbert’s Basis Theorem . . . . . . . . . . . . . . . . . . .
4.4.2 Hilbert’s Nullstellensatz . . . . . . . . . . . . . . . . . . .
4.5 Zero-dimensional Systems
. . . . . . . . . . . . . . . . . . . . . .
4.6 Multivariate Hermite’s Quadratic Form . . . . . . . . . . . . .
4.7 Projective Space and a Weak Bézout’s Theorem . . . . . . . .
4.8 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Polynomial Ideals
5 Decomposition of Semi-Algebraic Sets . . . . . . . . . . . . . .
5.1 Cylindrical Decomposition . . . . . . . . . . . . . . . . . . . . . .
5.2 Semi-algebraically Connected Components
. . . . . . . . . . .
5.3 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Semi-algebraic Description of Cells
. . . . . . . . . . . . . . . .
5.5 Stratification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Simplicial Complexes
. . . . . . . . . . . . . . . . . . . . . . . . .
5.7 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8 Hardt’s Triviality Theorem and Consequences
. . . . . . . . .
5.9 Semi-algebraic Sard’s Theorem . . . . . . . . . . . . . . . . . . .
5.10 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 Simplicial Homology Theory
6 Elements of Topology . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
6.1.1 The Homology Groups of a Simplicial Complex . . . .
6.1.2 Simplicial Cohomology Theory
. . . . . . . . . . . . . .
6.1.3 A Characterization of H1 in a Special Case.
. . . . . .
6.1.4 The Mayer-Vietoris Theorem . . . . . . . . . . . . . . .
93
94
99
101
101
105
105
110
113
119
119
127
132
132
136
143
149
153
157
159
159
168
170
172
174
181
183
186
191
194
195
195
195
199
201
206
Table of Contents
6.1.5 Chain Homotopy . . . . . . . . . . . . . . . . . . . . . . .
6.1.6 The Simplicial Homology Groups Are Invariant Under
Homeomorphism . . . . . . . . . . . . . . . . . . . . . . .
6.2 Simplicial Homology of Closed and Bounded Semi-algebraic
Sets
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Definitions and First Properties . . . . . . . . . . . . . .
6.2.2 Homotopy . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. .
6.3 Homology of Certain Locally Closed Semi-Algebraic Sets
6.3.1 Homology of Closed Semi-algebraic Sets and of Sign Con-
ditions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2 Homology of a Pair . . . . . . . . . . . . . . . . . . . . . .
6.3.3 Borel-Moore Homology
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
6.3.4 Euler-Poincaré Characteristic
6.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
7 Quantitative Semi-algebraic Geometry . . . . . . . . . . . . .
7.1 Morse Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Sum of the Betti Numbers of Real Algebraic Sets . . . . . . .
7.3 Bounding the Betti Numbers of Realizations of Sign Conditions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. .
7.4 Sum of the Betti Numbers of Closed Semi-algebraic Sets
7.5 Sum of the Betti Numbers of Semi-algebraic Sets
. . . . . . .
7.6 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
8 Complexity of Basic Algorithms
. . . . . . . . . . . . . . . . . .
8.1 Definition of Complexity . . . . . . . . . . . . . . . . . . . . . . .
8.2 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2.1 Size of Determinants . . . . . . . . . . . . . . . . . . . . .
8.2.2 Evaluation of Determinants
. . . . . . . . . . . . . . . .
8.2.3 Characteristic Polynomial . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
8.2.4 Signature of Quadratic Forms
8.3 Remainder Sequences and Subresultants . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
8.3.1 Remainder Sequences
8.3.2 Signed Subresultant Polynomials
. . . . . . . . . . . . .
8.3.3 Structure Theorem for Signed Subresultants . . . . . .
8.3.4 Size of Remainders and Subresultants
. . . . . . . . . .
8.3.5 Specialization Properties of Subresultants
. . . . . . .
8.3.6 Subresultant Computation . . . . . . . . . . . . . . . . .
8.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
VII
209
213
221
221
223
226
226
228
231
234
236
237
237
256
262
268
273
280
281
281
292
292
294
299
300
301
301
303
307
314
316
317
322
VIII
Table of Contents
9 Cauchy Index and Applications . . . . . . . . . . . . . . . . . . .
9.1 Cauchy Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.1.1 Computing the Cauchy Index . . . . . . . . . . . . . . .
9.1.2 Bezoutian and Cauchy Index . . . . . . . . . . . . . . . .
9.1.3 Signed Subresultant Sequence and Cauchy Index on an
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .
. . . . . . . . . .
9.3 Number of Complex Roots with Negative Real Part
. . . . .
9.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
9.2.1 Hankel Matrices and Rational Functions
9.2.2 Signature of Hankel Quadratic Forms
Interval
9.2 Hankel Matrices
10 Real Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.1 Bounds on Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2 Isolating Real Roots . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3 Sign Determination . . . . . . . . . . . . . . . . . . . . . . . . . .
10.4 Roots in a Real Closed Field . . . . . . . . . . . . . . . . . . . .
10.5 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
11.1 Computing the Cylindrical Decomposition
11 Cylindrical Decomposition Algorithm . . . . . . . . . . . . . .
. . . . . . . . . . .
11.1.1 Outline of the Method . . . . . . . . . . . . . . . . . . . .
11.1.2 Details of the Lifting Phase
. . . . . . . . . . . . . . . .
11.2 Decision Problem . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3 Quantifier Elimination . . . . . . . . . . . . . . . . . . . . . . . .
11.4 Lower Bound for Quantifier Elimination . . . . . . . . . . . . .
11.5 Computation of Stratifying Families
. . . . . . . . . . . . . . .
11.6 Topology of Curves
. . . . . . . . . . . . . . . . . . . . . . . . . .
11.7 Restricted Elimination . . . . . . . . . . . . . . . . . . . . . . . .
11.8 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
12 Polynomial System Solving . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
12.1 A Few Results on Gröbner Bases
12.2 Multiplication Tables
. . . . . . . . . . . . . . . . . . . . . . . . .
12.3 Special Multiplication Table . . . . . . . . . . . . . . . . . . . . .
12.4 Univariate Representation . . . . . . . . . . . . . . . . . . . . . .
12.5 Limits of the Solutions of a Polynomial System . . . . . . . .
12.6 Finding Points in Connected Components of Algebraic Sets .
12.7 Triangular Sign Determination . . . . . . . . . . . . . . . . . . .
323
323
323
326
330
333
334
337
344
350
351
351
360
383
397
401
403
404
404
408
415
423
426
428
430
440
444
445
445
451
456
462
471
483
495
Table of Contents
IX
12.8 Computing the Euler-Poincaré Characteristic of an Algebraic
Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12.9 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
13 Existential Theory of the Reals . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
13.1 Finding Realizable Sign Conditions
. . . . . . . . . . . . . . . . . . . . . . . . . .
13.2 A Few Applications
. . . . . . . . . . . . . . . .
13.3 Sample Points on an Algebraic Set
13.4 Computing the Euler-Poincaré Characteristic of Sign Condi-
tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13.5 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
14 Quantifier Elimination . . . . . . . . . . . . . . . . . . . . . . . . .
14.1 Algorithm for the General Decision Problem . . . . . . . . . .
14.2 Quantifier Elimination . . . . . . . . . . . . . . . . . . . . . . . .
14.3 Local Quantifier Elimination . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
14.4 Global Optimization
14.5 Dimension of Semi-algebraic Sets
. . . . . . . . . . . . . . . . .
14.6 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
15 Computing Roadmaps and Connected Components of Alge-
braic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.1 Pseudo-critical Values and Connectedness . . . . . . . . . . . .
15.2 Roadmap of an Algebraic Set . . . . . . . . . . . . . . . . . . . .
15.3 Computing Connected Components of Algebraic Sets
. . . .
15.4 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
16 Computing Roadmaps and Connected Components of Semi-
algebraic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.1 Special Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
16.2 Uniform Roadmaps
16.3 Computing Connected Components of Sign Conditions
. . .
16.4 Computing Connected Components of a Semi-algebraic Set .
16.5 Roadmap Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .
16.6 Computing the First Betti Number of Semi-algebraic Sets
.
16.7 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Index of Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
498
503
505
506
516
519
528
532
533
534
547
551
557
558
562
563
564
568
580
592
593
593
601
608
614
617
627
633
635
645
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
655
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
