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.


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


Full Text: DOI