Polynomial Algorithms in Computer Algebra

1 Introduction.- 1.1 What is computer algebra?.- 1.2 Program systems in computer algebra.- 1.3 Algebraic preliminaries.- 1.4 Representation of algebraic structures.- 1.5 Measuring the complexity of algorithms.- 1.6 Bibliographic notes.- 2 Arithmetic in basic domains.- 2.1 Integers.- 2.2 Polynomials.- 2.3 Quotient fields.- 2.4 Algebraic extension fields.- 2.5 Finite fields.- 2.6 Bibliographic notes.- 3 Computing by homomorphic images.- 3.1 The Chinese remainder problem and the modular method.- 3.2 p-adic approximation.- 3.3 The fast Fourier transform.- 3.4 Bibliographic notes.- 4 Greatest common divisors of polynomials.- 4.1 Polynomial remainder sequences.- 4.2 A modular gcd algorithm.- 4.3 Computation of resultants.- 4.4 Squarefree factorization.- 4.5 Squarefree partial fraction decomposition.- 4.6 Integration of rational functions.- 4.7 Bibliographic notes.- 5 Factorization of polynomials.- 5.1 Factorization over finite fields.- 5.2 Factorization over the integers.- 5.3 A polynomial-time factorization algorithm over the integers.- 5.4 Factorization over algebraic extension fields.- 5.5 Factorization over an algebraically closed field.- 5.6 Bibliographic notes.- 6 Decomposition of polynomials.- 6.1 A polynomial-time algorithm for decomposition.- 6.2 Bibliographic notes.- 7 Linear algebra-solving linear systems.- 7.1 Bareiss's algorithm.- 7.2 Hankel matrices.- 7.3 Application of Hankel matrices to polynomial problems.- 7.4 Bibliographic notes.- 8 The method of Gröbner bases.- 8.1 Reduction relations.- 8.2 Polynomial reduction and Gröbner bases.- 8.3 Computation of Gröbner bases.- 8.4 Applications of Gröbner bases.- 8.5 Speed-ups and complexity considerations.- 8.6 Bibliographic notes.- 9 Quantifier elimination in real closed fields.- 9.1 The problem of quantifierelimination.- 9.2 Cylindrical algebraic decomposition.- 9.3 Bibliographic notes.- 10 Indefinite summation.- 10.1 Gosper's algorithm.- 10.2 Bibliographic notes.- 11 Parametrization of algebraic curves.- 11.1 Plane algebraic curves.- 11.2 A parametrization algorithm.- 11.3 Bibliographic notes.- Solutions of selected exercises.- References.