##
**Polynomial algorithms in computer algebra.**
*(English)*
Zbl 0853.12003

This book surveys algorithms and results of Computer Algebra that are concerned with polynomials. It introduces algorithms from the bottom up, starting from very basic problems in computation over the integers, and finally leading to, e.g. advanced topics in factorization, solution of polynomial equations and constructive algebraic geometry. It is not based on a particular computer algebra program system.

After two introductory chapters, the book contains six chapters with the following respective topics: computation by homomorphic images, gcd computation, factorization and decomposition of polynomials, linear systems and Hankel systems, Gröbner bases. The last three chapters are concerned with applications of polynomial algorithms to higher level problems in computer algebra. In particular, a decision algorithm in the elementary theory of real closed fields, a description of Gosper’s algorithm for solving summation problems, and an algorithm for deciding whether an algebraic curve can be parametrized by rational functions (and if so for computing such a parametrization) is given. Along the way, the complexity of many of the algorithms is investigated. Each chapter ends with rich bibliographical notes.

The book was originally developed from course material. It can easily be used as a textbook on the topic. Most subsections contain exercises. Solutions of some of the exercises are provided.

After two introductory chapters, the book contains six chapters with the following respective topics: computation by homomorphic images, gcd computation, factorization and decomposition of polynomials, linear systems and Hankel systems, Gröbner bases. The last three chapters are concerned with applications of polynomial algorithms to higher level problems in computer algebra. In particular, a decision algorithm in the elementary theory of real closed fields, a description of Gosper’s algorithm for solving summation problems, and an algorithm for deciding whether an algebraic curve can be parametrized by rational functions (and if so for computing such a parametrization) is given. Along the way, the complexity of many of the algorithms is investigated. Each chapter ends with rich bibliographical notes.

The book was originally developed from course material. It can easily be used as a textbook on the topic. Most subsections contain exercises. Solutions of some of the exercises are provided.

Reviewer: J.Desel (Karlsruhe)

### MSC:

12Y05 | Computational aspects of field theory and polynomials (MSC2010) |

68W30 | Symbolic computation and algebraic computation |

68R99 | Discrete mathematics in relation to computer science |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

12-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to field theory |

13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |

14Q05 | Computational aspects of algebraic curves |

11Y16 | Number-theoretic algorithms; complexity |