第1页 / 共425页
第2页 / 共425页
第3页 / 共425页
第4页 / 共425页
第5页 / 共425页
第6页 / 共425页
第7页 / 共425页
第8页 / 共425页
算法代数（Bhubaneswar Mishra）Algorithmic Algebra (Bhubaneswar Mishra).pdf
Algorithmic Algebra
Bhubaneswar Mishra
Courant Institute of Mathematical Sciences
Editor Karen Kosztolnyk
Production Manager ??
Text Design ??
Cover Design ??
Copy Editor ??
Library of Congress Catalogue in Publication Data
Mishra, Bhubaneswar, 1958-
Algorithmic Algebra/ Bhubaneswar Mishra
p.
com.
Bibliography: p.
Includes Index
ISBN ?-?????-???-?
1. Algorithms 2. Algebra 3. Symbolic Computation
90-?????
CIP
display systems. I.Title
T??.???
???.??????-????
1993
Springer-Verlag Incorporated
Editorial Office:
???
???
Order from:
???
???
c1993 by ????
All rights reserved
No part of this publication may be reproduced, stored in a
retrieval system, or transmitted in any form or by any
means—electronic, mechanical, recording or otherwise—without
the prior permission of the publisher.
?? ?? ?? ?? ?? ? ? ? ? ?
To my parents
Purna Chandra & Baidehi Mishra
Preface
In the fall of 1987, I taught a graduate computer science course entitled
“Symbolic Computational Algebra” at New York University. A rough set
of class-notes grew out of this class and evolved into the following final
form at an excruciatingly slow pace over the last five years. This book also
benefited from the comments and experience of several people, some of
whom used the notes in various computer science and mathematics courses
at Carnegie-Mellon, Cornell, Princeton and UC Berkeley.
The book is meant for graduate students with a training in theoretical
computer science, who would like to either do research in computational
algebra or understand the algorithmic underpinnings of various commer-
cial symbolic computational systems: Mathematica, Maple or Axiom, for
instance. Also, it is hoped that other researchers in the robotics, solid
modeling, computational geometry and automated theorem proving com-
munities will find it useful as symbolic algebraic techniques have begun to
play an important role in these areas.
The main four topics–Gr¨obner bases, characteristic sets, resultants and
semialgebraic sets–were picked to reflect my original motivation. The choice
of the topics was partly influenced by the syllabii proposed by the Research
Institute for Symbolic Computation in Linz, Austria, and the discussions
in Hearn’s Report (“Future Directions for Research in Symbolic Computa-
tion”).
The book is meant to be covered in a one-semester graduate course
comprising about fifteen lectures. The book assumes very little background
other than what most beginning computer science graduate students have.
For these reasons, I have attempted to keep the book self-contained and
largely focussed on the very basic materials.
Since 1987, there has been an explosion of new ideas and techniques
in all the areas covered here (e.g., better complexity analysis of Gr¨obner
basis algorithms, many new applications, effective Nullstellensatz, multi-
variate resultants, generalized characteristic polynomial, new stratification
algorithms for semialgebraic sets, faster quantifier elimination algorithm
for Tarski sentences, etc.). However, none of these new topics could be in-
cluded here without distracting from my original intention. It is hoped that
this book will prepare readers to be able to study these topics on their own.
vii
viii
Preface
Also, there have been several new textbooks in the area (by Akritas,
Davenport, Siret and Tournier, and Mignotte) and there are a few more
on the way (by Eisenbaud, Robbiano, Weispfenning and Becker, Yap, and
Zippel). All these books and the current book emphasize different mate-
rials, involve different degrees of depth and address different readerships.
An instructor, if he or she so desires, may choose to supplement the cur-
rent book by some of these other books in order to bring in such topics as
factorization, number-theoretic or group-theoretic algorithms, integration
or differential algebra.
The author is grateful to many of his colleagues at NYU and elsewhere
for their support, encouragement, help and advice. Namely, J. Canny, E.M.
Clarke, B. Chazelle, M. Davis, H.M. Edwards, A. Frieze, J. Gutierrez,
D. Kozen, R. Pollack, D. Scott, J. Spencer and C-K. Yap.
I have also
benefited from close research collaboration with my colleague C-K. Yap
and my graduate students G. Gallo and P. Pedersen. Several students in
my class have helped me in transcribing the original notes and in preparing
some of the solutions to the exercises: P. Agarwal, G. Gallo, T. Johnson,
N. Oliver, P. Pedersen, R. Sundar, M. Teichman and P. Tetali.
I also thank my editors at Springer for their patience and support.
During the preparation of this book I had been supported by NSF and
ONR and I am gratified by the interest of my program officers: Kamal
Abdali and Ralph Wachter.
I would like to express my gratitude to Prof. Bill Wulf for his efforts to
perform miracles on my behalf during many of my personal and professional
crises. I would also like to thank my colleague Thomas Anantharaman for
reminding me of the power of intuition and for his friendship. Thanks are
due to Robin Mahapatra for his constant interest.
In the first draft of this manuscript, I had thanked my imaginary wife
for keeping my hypothetical sons out of my nonexistent hair. In the interim
five years, I have gained a wife Jane and two sons Sam and Tom, necessarily
in that order–but, alas, no hair. To them, I owe my deepest gratitude for
their understanding.
Last but not least, I thank Dick Aynes without whose unkind help this
book would have gone to press some four years ago.
B. Mishra
mishra@nyu.edu.arpa
Contents
Preface
1 Introduction
1.1 Prologue: Algebra and Algorithms . . . . . . . . . . . . . .
1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Constructive Algebra . . . . . . . . . . . . . . . . . .
1.2.2 Algorithmic and Computational Algebra . . . . . . .
Symbolic Computation . . . . . . . . . . . . . . . . .
1.2.3
1.2.4 Applications
. . . . . . . . . . . . . . . . . . . . . .
1.3 Algorithmic Notations . . . . . . . . . . . . . . . . . . . . .
1.3.1 Data Structures . . . . . . . . . . . . . . . . . . . . .
1.3.2 Control Structures . . . . . . . . . . . . . . . . . . .
1.4 Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . .
2 Algebraic Preliminaries
2.1
2.3 Gr¨obner Bases
Introduction to Rings and Ideals
. . . . . . . . . . . . . . .
2.1.1 Rings and Ideals . . . . . . . . . . . . . . . . . . . .
2.1.2 Homomorphism, Contraction and Extension . . . . .
2.1.3
Ideal Operations . . . . . . . . . . . . . . . . . . . .
2.2 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Dickson’s Lemma . . . . . . . . . . . . . . . . . . . .
2.2.2 Admissible Orderings on Power Products
. . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Gr¨obner Bases in K[x1, x2, . . . , xn]
. . . . . . . . . .
2.3.2 Hilbert’s Basis Theorem . . . . . . . . . . . . . . . .
2.3.3 Finite Gr¨obner Bases . . . . . . . . . . . . . . . . . .
2.4 Modules and Syzygies
. . . . . . . . . . . . . . . . . . . . .
2.5 S-Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problems
Solutions to Selected Problems
. . . . . . . . . . . . . . . .
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . .
vii
1
1
4
5
6
7
9
13
13
15
18
20
23
23
26
31
33
35
36
39
44
46
47
49
49
55
61
64
70
ix
x
Contents
3 Computational Ideal Theory
3.1
3.2 Strongly Computable Ring
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
3.2.1 Example: Computable Field . . . . . . . . . . . . . .
3.2.2 Example: Ring of Integers . . . . . . . . . . . . . . .
3.3 Head Reductions and Gr¨obner Bases . . . . . . . . . . . . .
3.3.1 Algorithm to Compute Head Reduction . . . . . . .
3.3.2 Algorithm to Compute Gr¨obner Bases . . . . . . . .
3.4 Detachability Computation . . . . . . . . . . . . . . . . . .
3.4.1 Expressing with the Gr¨obner Basis . . . . . . . . . .
3.4.2 Detachability . . . . . . . . . . . . . . . . . . . . . .
3.5 Syzygy Computation . . . . . . . . . . . . . . . . . . . . . .
Syzygy of a Gr¨obner Basis: Special Case . . . . . . .
Syzygy of a Set: General Case
. . . . . . . . . . . .
71
71
72
73
76
81
84
85
88
89
93
94
94
99
3.6 Hilbert’s Basis Theorem: Revisited . . . . . . . . . . . . . . 103
3.7 Applications of Gr¨obner Bases Algorithms . . . . . . . . . . 104
3.7.1 Membership . . . . . . . . . . . . . . . . . . . . . . . 104
3.7.2 Congruence, Subideal and Ideal Equality . . . . . . 105
Sum and Product . . . . . . . . . . . . . . . . . . . . 105
3.7.3
3.7.4
Intersection . . . . . . . . . . . . . . . . . . . . . . . 106
3.7.5 Quotient . . . . . . . . . . . . . . . . . . . . . . . . . 107
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Problems
Solutions to Selected Problems
. . . . . . . . . . . . . . . . 120
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 132
3.5.1
3.5.2
4 Solving Systems of Polynomial Equations
133
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.1
4.2 Triangular Set
. . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3 Some Algebraic Geometry . . . . . . . . . . . . . . . . . . . 138
. . . . . . . . . . . . . . . . . 141
4.3.1 Dimension of an Ideal
4.3.2
Solvability: Hilbert’s Nullstellensatz . . . . . . . . . 142
4.3.3 Finite Solvability . . . . . . . . . . . . . . . . . . . . 145
4.4 Finding the Zeros . . . . . . . . . . . . . . . . . . . . . . . . 149
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Problems
Solutions to Selected Problems
. . . . . . . . . . . . . . . . 157
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 165
5 Characteristic Sets
167
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.2 Pseudodivision and Successive Pseudodivision . . . . . . . . 168
5.3 Characteristic Sets . . . . . . . . . . . . . . . . . . . . . . . 171
5.4 Properties of Characteristic Sets
. . . . . . . . . . . . . . . 176
5.5 Wu-Ritt Process
. . . . . . . . . . . . . . . . . . . . . . . . 178
5.6 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.7 Geometric Theorem Proving . . . . . . . . . . . . . . . . . . 186
Contents
xi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Problems
Solutions to Selected Problems
. . . . . . . . . . . . . . . . 192
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 196
6 An Algebraic Interlude
199
6.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
6.2 Unique Factorization Domain . . . . . . . . . . . . . . . . . 199
6.3 Principal Ideal Domain . . . . . . . . . . . . . . . . . . . . . 207
6.4 Euclidean Domain . . . . . . . . . . . . . . . . . . . . . . . 208
6.5 Gauss Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.6 Strongly Computable Euclidean Domains
. . . . . . . . . . 212
Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Solutions to Selected Problems
. . . . . . . . . . . . . . . . 220
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 223
7 Resultants and Subresultants
225
7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.2 Resultants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.3 Homomorphisms and Resultants
. . . . . . . . . . . . . . . 232
7.3.1 Evaluation Homomorphism . . . . . . . . . . . . . . 234
. . . . 238
7.4 Repeated Factors in Polynomials and Discriminants
7.5 Determinant Polynomial . . . . . . . . . . . . . . . . . . . . 241
7.5.1 Pseudodivision: Revisited . . . . . . . . . . . . . . . 244
7.5.2 Homomorphism and Pseudoremainder . . . . . . . . 246
7.6 Polynomial Remainder Sequences . . . . . . . . . . . . . . . 247
7.7 Subresultants . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Subresultants and Common Divisors . . . . . . . . . 256
7.8 Homomorphisms and Subresultants . . . . . . . . . . . . . . 262
7.9 Subresultant Chain . . . . . . . . . . . . . . . . . . . . . . . 265
7.10 Subresultant Chain Theorem . . . . . . . . . . . . . . . . . 274
7.10.1 Habicht’s Theorem . . . . . . . . . . . . . . . . . . . 274
7.10.2 Evaluation Homomorphisms . . . . . . . . . . . . . . 277
7.10.3 Subresultant Chain Theorem . . . . . . . . . . . . . 279
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Problems
Solutions to Selected Problems
. . . . . . . . . . . . . . . . 292
Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 297
7.7.1
8 Real Algebra
297
8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
8.2 Real Closed Fields . . . . . . . . . . . . . . . . . . . . . . . 298
8.3 Bounds on the Roots . . . . . . . . . . . . . . . . . . . . . . 306
8.4 Sturm’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 309
8.5 Real Algebraic Numbers . . . . . . . . . . . . . . . . . . . . 315
8.5.1 Real Algebraic Number Field . . . . . . . . . . . . . 316
8.5.2 Root Separation, Thom’s Lemma and Representation 319
相关推荐
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
