Algorithmic Algebra

This book is based on a graduate computer science course entitled "Symbolic Computational Algebra" taught by the author at New York University. This book is meant for graduate students with training in theoretical computer science, who would like to do research in computational algebra or to understand the algorithms underlying currently available symbolic computational systems such as Mathematica, Maple or Axiom. The four main topics covered are Gröbner bases, characteristic sets, resultants and semialgebraic sets.

Contenu
1 Introduction.- 1.1 Prologue: Algebra and Algorithms.- 1.2 Motivations.- 1.3 Algorithmic Notations.- 1.4 Epilogue.- Bibliographic Notes.- 2 Algebraic Preliminaries.- 2.1 Introduction to Rings and Ideals.- 2.2 Polynomial Rings.- 2.3 Gröbner Bases.- 2.4 Modules and Syzygies.- 2.5 S-Polynomials.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 3 Computational Ideal Theory.- 3.1 Introduction.- 3.2 Strongly Computable Ring.- 3.3 Head Reductions and Gröbner Bases.- 3.4 Detachability Computation.- 3.5 Syzygy Computation.- 3.6 Hilbert's Basis Theorem: Revisited.- 3.7 Applications of Gröbner Bases Algorithms.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 4 Solving Systems of Polynomial Equations.- 4.1 Introduction.- 4.2 Triangular Set.- 4.3 Some Algebraic Geometry.- 4.4 Finding the Zeros.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 5 Characteristic Sets.- 5.1 Introduction.- 5.2 Pseudodivision and Successive Pseudodivision.- 5.3 Characteristic Sets.- 5.4 Properties of Characteristic Sets.- 5.5 Wu-Ritt Process.- 5.6 Computation.- 5.7 Geometric Theorem Proving.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 6 An Algebraic Interlude.- 6.1 Introduction.- 6.2 Unique Factorization Domain.- 6.3 Principal Ideal Domain.- 6.4 Euclidean Domain.- 6.5 Gauss Lemma.- 6.6 Strongly Computable Euclidean Domains.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 7 Resultants and Subresultants.- 7.1 Introduction.- 7.2 Resultants.- 7.3 Homomorphisms and Resultants.- 7.4 Repeated Factors in Polynomials and Discriminants.- 7.5 Determinant Polynomial.- 7.6 Polynomial Remainder Sequences.- 7.7 Subresultants.- 7.8 Homomorphisms and Subresultants.- 7.9 Subresultant Chain.- 7.10 Subresultant ChainTheorem.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- 8 Real Algebra.- 8.1 Introduction.- 8.2 Real Closed Fields.- 8.3 Bounds on the Roots.- 8.4 Sturm's Theorem.- 8.5 Real Algebraic Numbers.- 8.6 Real Geometry.- Problems.- Solutions to Selected Problems.- Bibliographic Notes.- Appendix A: Matrix Algebra.- A.1 Matrices.- A.2 Determinant.- A.3 Linear Equations.