Fundamental Problems of Algorithmic Algebra

O INTRODUCTION 1: Fundamental Problem of Algebra 2: Fundamental Problem of Classical Algebraic Geometry 3: Fundamental Problem of Ideal Theory 4: Representation and Size 5: Computational Models 6: Asymptotic Notations 7: Complexity of Multiplication 8: On Bit versus Algebraic Complexity 9: Miscellany 10: Computer Algebra Systems I ARITHMETIC 1: The Discrete Fourier Transform 2: Polynomial Multiplication 3: Modular FFT 4: Fast Integer Multiplication 5: Matrix Multiplication II THE GCD 1: Unique Factorization Domain 2: Euclid's Algorithm 3: Euclidean Ring 4: The Half-GCD problem 5: Properties of the Norm 6: Polynomial HGCD A: APPENDIX: Integer HGCD III SUBRESULTANTS 1: Primitive Factorization 2: Pseudo-remainders and PRS 3: Determinantal Polynomials 4: Polynomial Pseudo-Quotient 5: The Subresultant PRS 6: Subresultants 7: Pseudo-subresultants 8: Subresultant Theorem 9: Correctness of the Subresultant PRS Algorithm IV MODULAR TECHNIQUES 1: Chinese Remainder Theorem 2: Evaluation and Interpolation 3: Finiding Prime Moduli 4: Lucky homomorphisms for the GCD 5: Coefficient Bounds for Factors 6: A Modular GCD algorithm 7: What else in GCD computation? IV FUNDAMENTAL THEOREM OF ALGEBRA 1: Elements of Field Theory 2: Ordered Rings 3: Formally Real Rings 4: Constructible Extensions 5: Real Closed Fields 6: Fundamental Theorem of Algebra VI ROOTS OF POLYNOMIALS 1: Elementary Properties of Polynomial Roots 2: Root Bounds 3: Algebraic Numbers 4: Resultants 5: Symmetric Functions 6: Discriminant 7: Root Separation 8: A Generalized Hadamard Bound 9: Isolating Intervals 10: On Newton's Method 11: Guaranteed Convergence of Newton Iteration VII STURM THEORY 1: Sturm Sequences from PRS 2: A Generalized Sturm Theorem 3: Corollaries and Applications 4: Integer and Complex Roots 5: The Routh-Hurwitz Theorem 6: Sign Encoding of Algebraic Numbers: Thom's Lemma 7: Problem of Relative Sign Conditions 8: The BKR algorithm VIII GAUSSIAN LATTICE REDUCTION 1: Lattices 2: Shortest vectors in planar lattices 3: Coherent Remainder Sequences IX LATTICE REDUCTION AND APPLICATIONS 1: Gram-Schmidt Orthogonalization 2: Minkowski's Convex Body Theorem 3: Weakly Reduced Bases 4: Reduced Bases and the LLL-algorithm 5: Short Vectors 6: Factorization via Reconstruction of Minimal Polynomials X LINEAR SYSTEMS 1: Sylvester's Identity 2: Fraction-free Determinant Computation 3: Matrix Inversion 4: Hermite Normal Form 5: A Multiple GCD Bound and Algorithm 6: Hermite Reduction Step 7: Bachem-Kannan Algorithm 8: Smith Normal Form 9: Further Applications XI ELIMINATION THEORY 1: Hilbert Basis Theorem 2: Hilbert Nullstellensatz 3: Specializations 4: Resultant Systems 5: Sylvester Resultant Revisited 6: Interial Ideal 7: The Macaulay Resultant 8: U-Resultant 9: Generalized Characteristic Polynomial 10: Generalized U - resultant 11: A Multivariate Root Bound A: APPENDIX A: Power Series B: APPENDIX B: Counting Irreducible Polynomials XII GROBNER BASES 1: Admissible Orderings 2: Normal Form ALgorithm 3: Characterizations of Grobner Bases 4: Buchberger's Algorithm 5: Uniqueness 6: Elimination Properties 7: Computing in Quotient Rings 8: Syzygies XIII BOUNDS IN POLYNOMIAL IDEAL THEORY 1: Some Bounds in Polynomial Ideal Theory 2: The Hilbert-Sette Theorem 3: Homogeneous Sets 4: Cone Decomposition 5: Exact Decomposition of NF (I) 6: Exact Decomposition of Ideals 7: Bouding the Macaulay constants 8: Term Rewriting Systems 9: A Quadratic Counter 10: Uniqueness Property 11: Lower Bounds A: APPENDIX: Properties of So XIV CONTINUED FRACTIONS 1: Introductions 2: Extended Numbers 3: General Terminology 4: Ordinary Continued Fractions 5: Continued fractions as Mobius transformations 6: Convergence Properties 7: Real Mobius Transformations 8: Continued Fractions of Roots 9: Arithmetic Operations