Number 1, November 1996.
Number 1, November 1996.
Review by J. Rafael Sendra, University of Alcalá (Spain)
This book provides an exposition of the fundamental topics in Computer Algebra, with special emphasis on polynomial algorithms. The topics considered cover from the basic problems on arithmetic in the main computer algebra domains to advanced topics in factorization, solution of polynomial equations and constructive algebraic geometry.
The book is organized in eleven chapter, which can be classified in three
groups. The first one, formed by chapters 1,2,3, states the basic notions and
algorithms for the subsequent chapters. The second group contains chapters
4 to 8, and deals with the fundamental topics in computer algebra: ,
resultants, polynomial factorization, Gröbner basis. The last group,
covering chapters 9,10,11, applies the methods described to three
advanced topics: quantifier elimination in real closed fields, indefinite
summation, and parametrization of algebraic curves.
The presentation of the material in each chapter progresses gradually from introductory to more advanced, including examples and complexity analysis of the relevant algorithms. A list of exercises concludes each section, and each chapter ends with some helpful bibliographic notes.
The book starts out with a motivation to computer algebra (Chapter 1), where the fundamental characteristics of symbolic algebraic computation are commented, and some application problems in robotics and algebraic geometry are given. The author also includes, in this introductory chapter, a presentation of the program systems in computer algebra and the prerequisites for the area: algebraic perliminaries, algebraic data structures and basic notions on complexity.
Chapter 2 deals with the arithmetic in the basic domains used in the subsequent chapters: integers, multivariate polynomials over commutative rings, quotient fields of Euclidean domains, algebraic extension of fields and finite fields. For each of these algebraic structures the corresponding representation of their objects and the main algorithms performing the arithmetic are analyzed.
Chapter 3 focusses on the algorithmic techniques based on the computation
by homomorphic imagines. It begins with the study of the Chinese remainder
problem over Euclidean domains and its application to modular methods.
Then, the -adic method is studied, and
the fast Fourier transform is introduced and analyzed. The chapter
finishes with the application of FFT to derive the fastest known
multiplication algorithm for integers.
Once the basic domains and the fundamental algorithmic techniques are
introduced, the author addresses, in Chapters 4 and 5, the problems of
computing of polynomials and factoring polynomials. In Chapter 4,
subresultant algorithm and Brown's modular algorithm for determining the
and the resultant of two multivariate polynomials are studied. As
an application of these methods, the problem of computing squarefree
factorization of polynomials is considered. The Chapter finishes with
the computation of squarefree partial fraction decomposition of
rational functions, and the integration of rational function with rational
coefficient.
Chapter 5 describes Berlekamp-Hensel algorithm and the polynomial time
algorithm L for factoring polynomials, as well as the
algorithmic method, presented in wan der Warden's book on Modern Algebra and slightly improved by Trager in 1976, for factoring
polynomials over algebraic field extensions. Furthermore, the
computation of absolute factorizations is also considered.
The problem of decomposing polynomial essentially consists in deciding
whether a polynomial with coefficients over a computable field
can be expressed as
for some polynomials
.
In Chapter 6, Kozen and Landau's approach to the problem is studied.
The next chapter (Chapter 7) is devoted to symbolic methods in linear algebra. The chapter starts with the fraction free Gaussian elimination method of Bareiss, and then it focusses on the applications of Hankel matrices to computer algebra.
An introduction to Gröbner basis is given in Chapter 8. Göbner basis are defined for polynomial ideals over a field by means of Church-Rosser property. Later on Buchberger's algorithm is studied, and Gröbner basis are applied to some important problems in polynomial ideal theory and solution of systems of algebraic equations. In addition, a section devoted to speed-ups and complexity issues is included.
The last three chapters examine some advanced problems. Chapter 9
describes Collins's CAD approach to the problem of quantifier
elimination for the elementary theory of real closed fields. The problem
consist in: given a formula in the elementary theory of real
closed fields, in which the atomic formulas are all expressions of the
form
, where
, and
is a
predicate symbol, find a quantifier-free formula equivalent to
.
In Chapter 4, the problem of indefinite integration was analyzed. Now,
in Chapter 10, the discrete analogon is studied. In this
context, Gosper's algorithm for indefinite summation is described.
The last chapter examines the application of symbolic algorithm to
algebraic geometry; more precisely to the problem of parametrizing
algebraic plane curves. For this purpose, a brief overview of the
basic notions and results on plane algebraic curves is given, and afterward
the classical geometric approach (based on neighboring points),
to decide the rationality of an
algebraic plane curve, and to parametrize rational curves, is described.
Finally the book also includes the solution of some selected exercises and
a substantial bibliography.
Summarizing, this is, in my opinion, an excellent book. It is suitable for techning courses in computer algebra, and I recommed the book to anyone who intend to make research in this area.
Contents