1 Introduction 1
1.1 Prologue:Algebra and Algorithms 1
1.2 Motivations 4
1.2.1 Constructive Algebra 5
1.2.2 Algorithmic and Computational Algebra 6
1.2.3 Symbolic Computation 7
1.2.4 Applications 9
1.3 Algorithmic Notations 13
1.3.1 Data Structures 13
1.3.2 Control Structures 15
1.4 Epilogue 18
Bibliographic Notes 20
2 Algebraic Preliminaries 23
2.1 Introduction to Rings and Ideals 23
2.1.1 Rings and Ideals 26
2.1.2 Homomorphism,Contraction and Extension 31
2.1.3 Ideal Operations 33
2.2 Polynomial Rings 35
2.2.1 Dickson's Lemma 36
2.2.2 Admissible Orderings on Power Products 39
2.3 Gr？bner Bases 44
2.3.1 Gr？bner Bases in K[x1,x2,...,xn] 46
2.3.2 Hilbert's Basis Theorem 47
2.3.3 Finite Gr？bner Bases 49
2.4 Modules and Syzygies 49
2.5 S-Polynomials 55
Problems 60
Solutions to Selected Problems 63
Bibliographic Notes 69
3 Computational Ideal Theory 71
3.1 Introduction 71
3.2 Strongly Computable Ring 72
3.2.1 Example:Computable Field 73
3.2.2 Example:Ring of Integers 76
3.3 Head Reductions and Gr？bner Bases 80
3.3.1 Algorithm to Compute Head Reduction 83
3.3.2 Algorithm to Compute Gr？bner Bases 84
3.4 Detachability Computation 87
3.4.1 Expressing with the Gr？bner Basis 88
3.4.2 Detachability 92
3.5 Syzygy Computation 93
3.5.1 Syzygy of a Gr？bner Basis:Special Case 93
3.5.2 Syzygy of a Set:General Case 98
3.6 Hilbert's Basis Theorem:Revisited 102
3.7 Applications of Gr？bner Bases Algorithms 103
3.7.1 Membership 103
3.7.2 Congruence,Subideal and Ideal Equality 103
3.7.3 Sum and Product 104
3.7.4 Intersection 105
3.7.5 Quotient 106
Problems 108
Solutions to Selected Problems 118
Bibliographic Notes 130
4 Solving Systems of Polynomial Equations 133
4.1 Introduction 133
4.2 Triangular Set 134
4.3 Some Algebraic Geometry 138
4.3.1 Dimension of an Ideal 141
4.3.2 Solvability:Hilbert's Nullstellensatz 142
4.3.3 Finite Solvability 145
4.4 Finding the Zeros 149
Problems 152
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
Problems 189
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
7.4 Repeated Factors in Polynomials and Discriminants 238
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
7.7.1 Subresultants and Common Divisors 255
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 276
7.10.3 Subresultant Chain Theorem 279
Problems 283
Solutions to Selected Problems 291
Bibliographic Notes 296
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
8.6 Real Geometry 333
8.6.1 Real Algebraic Sets 337
8.6.2 Delineability 339
8.6.3 Tarski-Seidenberg Theorem 345
8.6.4 Representation and Decomposition of Semialgebraic Sets 347
8.6.5 Cylindrical Algebraic Decomposition 348
8.6.6 Tarski Geometry 354
Problems 361
Solutions to Selected Problems 372
Bibliographic Notes 381
Appendix A:Matrix Algebra 385
A.1 Matrices 385
A.2 Determinant 386
A.3 Linear Equations 388
Bibliography 391
Index 409