实代数几何算法：求解实数域多项式根的工具

需积分: 15 140 浏览量更新于2024-07-19 1 收藏 5.54MB PDF 举报

"《实代数几何算法》第二版，由Saugata Basu、Richard Pollack和Marie-Françoise Roy合著，是一部深入探讨实数域下多项式求根及相关代数几何问题的著作。书中包含37幅插图，并提供了数学分类号，表明其涉及的主要领域包括代数几何、计算理论、逻辑、算法和几何学。" 实代数几何是数学的一个分支，主要研究实数域上代数簇的性质。在这个领域中，算法起着至关重要的作用，因为它们能够帮助我们理解和解决多项式方程在实数域内的根的问题。实代数几何算法通常涉及以下几个核心概念： 1. **多项式求根**：多项式方程的解是代数几何的基础，尤其是在实数域中，解的存在性和性质可能会引起复杂的几何结构。例如，根据实数根的个数和分布，可以推断出相应的代数簇的维数和拓扑结构。 2. **Buchberger算法**：在实代数几何中，Buchberger算法用于找到一个多项式的格罗布纳基，这有助于理解多项式理想的结构。通过这种方法，我们可以确定哪些多项式组合成零集，进而分析实数解的性质。 3. **实闭包算法**：实闭包算法是实代数几何中的关键工具，它用于确定一个理想在实数域中的最小闭包，即所有可能的实数解的集合。这个过程可以帮助我们识别是否存在实数解，以及如何描述这些解的集合。 4. **维数理论**：理解代数簇的维数是实代数几何的核心任务之一。通过计算多项式理想的维度，我们可以推断出簇的几何形状和可能的实数解的复杂性。 5. **分支定理**：在处理实代数簇时，分支定理描述了当一个簇在其他簇上投影时，如何预测和计算分支点的数量和类型。这对于理解和计算实数解的分布至关重要。 6. **算法复杂性**：由于实代数几何问题往往涉及到复杂数学运算，因此算法的效率和可行性是研究的关键。作者们在书中可能讨论了各种算法的运行时间及其在计算资源上的限制。 7. **几何可视化**：书中包含的37幅插图有助于将抽象的数学概念具象化，使读者能够直观地理解实代数几何的几何结构和算法结果。《实代数几何算法》第二版是深入研究实数域中多项式求根问题和相关代数几何问题的宝贵资源，适合对这个领域感兴趣的数学家、计算机科学家和工程师阅读。它提供了一套强大的工具集，用于理解和解决与实数解有关的代数几何挑战。

4 Comments about the second edition An imp ortant change in content

between the ﬁrst edition [20] and the second one is the inversion of the order

of Chapter 12 and Chapter 11. Indeed when teachin g courses based on t he

book, we felt that the material on polynomial system solving was not nec-

essary to explain cylindrical decomposition and it was better to make these

two chapters independent for teaching purposes. For the same reason, we

also made the real root counting technique based on signed subresultant coef-

ﬁcients independent of the signed subresultant polynomials and included it

in Chapter 4 rather than in Chapter 9 as before. Some other chapters have

been slightly reorganized. Several new topics are included in this second edi-

tion: results about normal polynomials and virtual roots in Chapter 2, about

discriminants of symmetric matrices in Chapter 4, a new section bounding

the Betti numbers of semi-algebraic sets in Chapter 7, an improved complexity

analysis of real root isolation, as well as the real root isolation algorithm

in the monomial basis, in Chapter 10, the notion of parametrized path in

Chapter 15 and the computation of the ﬁrst Betti number of a semi-alge-

braic set in single exponential time. We also included a table of notation

and completed the bibliography and bibliographical notes at the end of the

chapters. Various mistakes and typos have been corrected, and new ones

introduced, for sure. As a result of the changes, the numbering of Deﬁni-

tions, Theorems etc. are n ot identical in the ﬁrst edition [20] and the second

one. Also, Algorithms now have their own numbering.

According to our contract with Springer-Verlag, we have had the right to

post updated versions of the ﬁrst edition of the book on our websites since

December 2004. Currently an updated version of the ﬁrst edition is available

online as bpr-posted1.pdf. We are going to update on a regular basis this

posted version. Here are the various url where these ﬁles can be obtained

through http:// at

www.math.gatech.edu/ ∼saugata/bpr-posted1.html

www.math.nyu.edu/faculty/pollack/bpr-posted1.html

perso.univ-rennes1.fr/marie-francoise.roy/bpr-posted1.html

An implementation of algorithms from Chapters 8 to 10 and part of

Chapter 11 written in Maxima by Fabrizio C aruso, as well as a version of Jean-

Charles Faugère [59] and Fabrice Rouillier [135] software illustrating part of

Chapter 12, can also be down loaded at bpr-posted1-annex.

Note that the second edition has been prepared inside T

MAC S

.The

MACS

ﬁles have been initially produced from classical latex ﬁles of the

ﬁrst edition. Even though some manual changes in the latex ﬁles have been

necessary to obtain correct T

MAC S

ﬁles, the translation into T

MAC S

was

made automatically, and it has not been necessary to retype the text and

formulas, besides a few exceptions.

8 Introduction

After eighteen months of the publication of the current edition of the book,

we will post the second edition online and it will be available for downloading

from the same url as abo ve.

5 Interactive version of the book Another possibility is to get the book as

MACS

project by downloading bpr-posted1-int.IntheT

MAC S

pro-

ject version, you are able to travel in th e book by clicking on references,

to fold/unfold proofs, descriptions of the algorithms and parts of the text.

You can use the open-source maxima code corresponding to algorithms of

Chapters 8 to 10 and part of Chapter 11 written by Fabrizio Caruso [40]: check

examples, read the source code and make your own computations inside the

book. You can also use the part of [59] and [135] provided by Jean-Charles

Faugère and Fabrice Rouillier to illustrate pa rt of Chapter 12 direct ly in the

book. These f unctionalities are still experimental. You are welcome to report

to the authors’ email addresses any problem you might meet in using them.

In the future, T

MAC S

versions of the bo ok will include other interactive

features, such as being able to ﬁnd all places in the book where a given theorem

is quoted.

6ErrorsIf you ﬁnd remaining errors in the book, we would appreciate it if

you would let us know

email: saugata.basu@math.gatech.edu

pollack@cims.nyu.edu

marie-francoise.roy@univ-rennes1.fr

A list of errors identiﬁed in this version will be found at

www.math.gatech.edu/ ∼saugata/bpr_book/bpr-ed2-errata.html.

7 Acknowledgment We thank Michel Coste, Gr eg Friedman, Laureano Gon-

zalez-Vega, Abdeljaoued Jounaidi, Henri Lombardi, Dimitri Pasechnik, Fab-

rice Rouillier for their advice and help. We also thank Solen Corvez, Gwenael

Guérard, Michael Kettner, Tomas Lajous, Samuel Lelièvre, Mohab Safey,

and Brad Weir for studying preliminary versions of the text and helping

to improve it. Mistakes or typos in [20] have been identiﬁed by Morou Amidou,

Emmanuel Briand, Fa brizio Caruso, Fernand o Carreras, Keven Commaul t,

Anne Devys, Arno Eigenwillig, Vincent Guenanﬀ, Michael Kettner, Assia

Mahboubi, Iona Necula, Adamou Otto, Dimitri Pasechnik, Hervé Perdry,

Savvas Perikleous, Moussa Seydou.

Joris Van der Hoeven has provided support for the use of T

MAC S

and pro-

duced several new version s of the software adapted to our purpose. Most

ﬁgures are the same as in the ﬁrst ed ition. However, Henri Lesourd produced

some native T

MAC S

diagrams and ﬁgures for us.

Introduction 9

Exercise 1.1. Prove that an a lgebraic subset of C is either a ﬁnite set or

empty or equal to C.

It is natural to co nsider the smallest family of sets which contain the alge-

braic sets and is also closed under the boolean operations (complementation,

ﬁnite unions, and ﬁnite intersections). These are the constructi ble sets.

Similarly, the smallest family of sets which contain the algebraic sets, their

complements, and is closed under ﬁnite intersections is the family of basic

constructible sets. Such a basic constructible set S can be described as a

conjunction of polynomial equations and inequations, namely

S = {x ∈C



P ∈P

P (x)=0∧



Q∈Q

Q(x)



with P, Q ﬁnite subsets of C[X



Exercise 1.2. Prove that a constructible subset of C is either a ﬁnite set or

the complement of a ﬁnite set.

Exercise 1.3. Prove that a constructible set in C

is a ﬁnite union of basic

constructible sets.

The principal goal of this chapter is to prove that the projection from C

k+1

to C

that is deﬁned by “forgetting" the last coordinate maps constructible

sets to constructible sets. For this, since projection commutes with union, it

suﬃces to prove that the projection

{y ∈C

∃ x ∈C



P ∈P

P (y,x)=0∧



Q∈Q

Q(y,x)



of a basic constructible set,

{(y,x) ∈C

k+1



P ∈P

P (y,x)=0∧



Q∈Q

Q(y,x)



is constructible, i.e. can be described by a boolean combination of polynomial

equations (P =0)andinequations (P



0)inY =(Y



Some term inology from logic is useful for the study of constructible sets.

We deﬁne the language of ﬁelds by describing the formulas of this language.

The formulas are built starting with atoms, which are p o lynomial equations

and inequations. A formula is written using atoms together with the logical

connectives “and", “or", and “negation" ( ∧, ∨,and¬) and the existential and

universal quantiﬁers (∃, ∀). A formula has free variables, i.e. non-quantiﬁed

variables, and bound va riables, i.e. quantiﬁed variables. More precisely, let

D be a subring of C. We deﬁne the language of ﬁelds with coeﬃcients

in D as follows. An atom is P =0or P



0,whereP is a polynomial

in D[X



]. We deﬁne simultaneously the formulas and Free(Φ),theset

of free variables of a formula Φ, as follows

− an atom P =0 or P



0,whereP is a polynomial in D[X



] is a

formula with free variables {X



12 1 Algebraica lly Closed Fields

剩余663页未读，继续阅读

crazy_lazy_pig

粉丝: 5
资源: 6

实代数几何算法：求解实数域多项式根的工具

漫谈微分几何、多复变函数与代数几何

代数几何原理（学习复几何最基本最经典的教材）（P.Griffiths;J.Harris ）

使用Macaulay 2进行代数几何计算Computations in Algebraic Geometry with Macaulay 2

代数几何码 feng-rao算法

计算几何算法与实现 twinklingstar

线性代数几何意义 pdf 下载

高等代数与解析几何在人工智能方面的应用

算法2.1-算法2.12顺序表和链表模拟

代数与编码 万哲先pdf

有一幅蝴蝶、一幅风景图片，基于几何、代数和色彩通道运算，编程实现漫天蝴蝶飞舞的合成图像

最新资源

代数与编码万哲先pdf