Algorithms for computer algebra. (English) Zbl 0805.68072

Geddes, Keith O.; Czapor, Stephen R.; Labahn, George

Dordrecht: Kluwer Academic Publishers Group. XVIII, 585 p. (1992).

Computer Algebra (CA) is the name given to the discipline of algebraic, rather than numerical, computation. There are a number of computer programs – Computer Algebra Systems (CASs) – available for doing this. The most widely used general-purpose systems that are currently available commercially are Axiom, Derive, Macsyma, Maple, Mathematica and REDUCE. The discipline of computer algebra began in the early 1960s and the first version of REDUCE appeared in 1968.
A large class of mathematical problems can be solved by using a CAS purely interactively, guided only by the user documentation. However, sophisticated use requires an understanding of the considerable amount of theory behind computer algebra, which in itself is an interesting area of constructive mathematics. For example, most systems provide some kind of programming language that allows the user to expand or modify the capabilities of the system.
This book is probably the most general introduction to the theory of computer algebra that is written as a textbook that develops the subject through a smooth progression of topics. It describes not only the algorithms but also the mathematics that underlies them. The book provides an excellent starting point for the reader new to the subject, and would make an excellent text for a postgraduate or advanced undergraduate course. It is probably desirable for the reader to have some background in abstract algebra, algorithms and programming at about second-year undergraduate level.
The book introduces the necessary mathematical background as it is required for the algorithms. The authors have avoided the temptation to pursue mathematics for its own sake, and it is all sharply focused on the task of performing algebraic computation. The algorithms are presented in a pseudo-language that resembles a cross between Maple and C. They provide a good basis for actual implementations although quite a lot of work would still be required in most cases. There are no code examples in any actual programming language except in the introduction.
The authors are all associated with the group that began the development of Maple. Hence, the book reflects the approach taken by Maple, but the majority of the discussion is completely independent of any actual system. The authors’ experience in implementing a practical CAS comes across clearly.
The book focuses on the core of computer algebra. The first chapter introduces the general concept and provides a very nice historical survey. The next three chapters discuss the fundamental topics – data structures, representations and the basic arithmetic of integers, rational numbers, multivariate polynomials and rational functions – on which the rest of the book is built.
A major technique in CA involves projection onto one or more homomorphic images, for which the ground ring is usually chosen to be a finite field. The image solution is lifted back to the original problem domain by means of the Chinese Remainder Theorem in the case of multiple homomorphic images, or the Hensel (\(p\)-adic or ideal-adic) construction in the case of a single image. The next two chapters are devoted to these techniques in a fairly general setting. The two subsequent chapters specialise them to GCD computation and factorisation for multivariate polynomials; the first of these chapters also discusses the important but difficult topic of subresultants.
The next two chapters describe the use of fraction-free Gaussian elimination, resultants and Gröbner Bases for manipulation and exact solution of linear and nonlinear polynomial equations. The two final chapters describe “classical” algorithms and the more recent Risch algorithm for symbolic indefinite integration, and provide an introduction to differential algebra.
The book does not consider more specialised problem areas such as symbolic summation, definite integration, differential equations, group theory or number theory. Nor does it consider more applied problem areas such as vectors, tensors, differential forms, special functions, geometry or statistics, even though Maple and other CASs provide facilities in all or many of these areas. It does not consider questions of CA programming language design, nor any of the important but non-algebraic facilities provided by current CASs such as their user interfaces, numerical and graphical facilities.
This is a long book (nearly 600 pages); it is generally very well presented and the three authors have merged their contributions seamlessly. I noticed very few typographical errors, and none of any consequence. I have only two complaints about the book. The typeface is too small, particularly for the relatively large line spacing used, and it is much too expensive, particularly for a book that would otherwise be an excellent student text. I recommend it highly to anyone who can affort it.

Reviewer: F.J.Wright (London)

MSC:

68W30	Symbolic computation and algebraic computation
13Pxx	Computational aspects and applications of commutative rings
68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
12Y05	Computational aspects of field theory and polynomials (MSC2010)

Keywords:

constructive mathematics; computer algebra; Maple; Chinese Remainder Theorem; GCD computation; factorisation; Gaussian elimination; resultants; Gröbner Bases; Risch algorithm; symbolic indefinite integration; differential algebra

Software:

AXIOM; MACSYMA; DERIVE; Maple; REDUCE; Mathematica