Contents

Preface


Introduction
     0.1 Fundamental Problem of Algebra
     0.2 Fundamental Problem of Classical Algebraic Geometry
     0.3 Fundamental Problem of Ideal Theory
     0.4 Representation and Size
     0.5 Computational Models
     0.6 Asymptotic Notations
     0.7 Complexity of Multiplication
     0.8 On Bit versus Algebraic Complexity
     0.9 Miscellany
     0.10 Computer Algebra Systems

1. Arithmetic
     1.1 The Discrete Fourier Transform
     1.2 Polynomial Multiplication
     1.3 Modular Fast Fourier transform
     1.4 Fast Integer Multiplication
     1.5 Matrix Multiplication

2. The Greatest Common Denominator
     2.1 Unique Factorization Domain
     2.2 Euclid's Algorithm
     2.3 Euclidean Ring
     2.4 The Half-GCD Problem
     2.5 Properties of the Norm
     2.6 Polynomial Half-GCD
     APPENDIX A: Integer Half-GCD

3. Subresultants
     3.1 Primitive Factorization
     3.2 Pseudoremainders and Polynomial Remainder Sequence
     3.3 Determinantal Polynomials
     3.4 Polynomial Pseudoquotient
     3.5 The Subresultant Polynomial Remainder Sequence
     3.6 Subresultants
     3.7 Pseudosubresultants
     3.8 Subresultant Theorem
     3.9 Correctness of the Subresultant PRS Algorithm

4. Modular Techniques
     4.1 Chinese Remainder Theorem
     4.2 Evaluation and Interpolation
     4.3 Finding Prime Moduli
     4.4 Lucky Homomorphisms for the GCD
     4.5 Coefficient Bounds for Factors
     4.6 A Modular Greatest Common Denominator Algorithm
     4.7 What Else in GCD Computation?

5. Fundamental Theorem of Algebra
     5.1 Elements of Field Theory
     5.2 Ordered Rings
     5.3 Formally Real Rings
     5.4 Constructible Extensions
     5.5 Real Closed Fields
     5.6 Fundamental Theorem of Algebra

6. Roots of Polynomials
     6.1 Elementary Properties of Polynomial Roots
     6.2 Root Bounds
     6.3 Algebraic Numbers
     6.4 Resultants
     6.5 Symmetric Functions
     6.6 Discriminant
     6.7 Root Separation
     6.8 A Generalized Hadamard Bound
     6.9 Isolating Intervals
     6.10 On Newton's Method
     6.11 Guaranteed Convergence of Newton Iteration

7. Sturm Theory
     7.1 Sturm Sequences from polynomial remainder sequences
     7.2 A Generalized Sturm Theorem
     7.3 Corollaries and Applications
     7.4 Integer and Complex Roots
     7.5 The Routh-Hurwitz Theorem
     7.6 Sign Encoding of Algebraic Numbers: Thom's Lemma
     7.7 Problem of Relative Sign Conditions
     7.8 The BKR algorithm

8. Gaussian Lattice Reduction
     8.1 Lattices
     8.2 Shortest vectors in planar lattices
     8.3 Coherent Remainder Sequences

9. Lattice Reduction and Applications
     9.1 Gram-Schmidt Orthogonalization
     9.2 Minkowski's Convex Body Theorem 
     9.3 Weakly Reduced Bases
     9.4 Reduced Bases and the LLL Algorithm
     9.5 Short Vectors
     9.6 Factorization via Reconstruction of Minimal Polynomials

10. Linear Systems
     10.1 Sylvester's Identity
     10.2 Fraction-free Determinant Computation
     10.3 Matrix Inversion
     10.4 Hermite Normal Form
     10.5 A Multiple GCD Bound and Algorithm
     10.6 Hermite Reduction Step
     10.7 Bachem-Kannan Algorithm
     10.8 Smith Normal Form
     10.9 Further Applications

11. Elimination Theory
     11.1 Hilbert Basis Theorem
     11.2 Hilbert Nullstellensatz
     11.3 Specializations
     11.4 Resultant Systems
     11.5 Sylvester Resultant Revisited
     11.6 Inertial Ideal
     11.7 The Macaulay Resultant
     11.8 UResultant
     11.9 Generalized Characteristic Polynomial
     11.10 Generalized U-resultant
     11.11 A Multivariate Root Bound
     APPENDIX A: Power Series
     APPENDIX B: Counting Irreducible Polynomials

12. Gr\"obner Bases
     12.1 Admissible Orderings
     12.2 Normal Form Algorithm
     12.3 Characterizations of Gr\"obner Bases
     12.4 Buchberger's Algorithm
     12.5 Uniqueness
     12.6 Elimination Properties
     12.7 Computing in Quotient Rings
     12.8 Syzygies

13. Bounds in Polynomial Ideal Theory
     13.1 Some Bounds in Polynomial Ideal Theory
     13.2 The Hilbert-Serre Theorem
     13.3 Homogeneous Sets
     13.4 Cone Decomposition
     13.5 Exact Decomposition of NF(I)
     13.6 Exact Decomposition of Ideals
     13.7 Bounding the Macaulay constants
     13.8 Term-Rewriting Systems
     13.9 A Quadratic Counter
     13.10 Uniqueness Property
     13.11 Lower Bounds
     APPENDIX A: Properties of S_0

14. Continued Fractions
     14.1 Introduction
     14.2 Extended Numbers
     14.3 General Terminology
     14.4 Ordinary Continued Fractions
     14.5 Continued Fractions as M\"obius Transformations
     14.6 Convergence Properties
     14.7 Real M\"obius Transformations
     14.8 Continued Fractions of Roots
     14.9 Arithmetic Operations

References
Index
Index to Symbols