Number 2, June 1997.
Number 2, June 1997.
P. Bürgisser, M. Clausen, M. Amin Shokrollahi
Grundlehren der mathematischen Wissenschaften, vol. 315,
Springer-Verlag, 1997, ISBN: 3-540-60582-7.
Review by Luis Miguel Pardo and Tomas Recio
Universidad de Cantabria, Santander, Spain
Emails: pardo@matsun1.matesco.unican.es, recio@matsun1.matesco.unican.es
The standard formalized model for the design and analysis of algorithms in the discrete setting is the Turing machine and its variants. When dealing with algebraically posed problems and with the design of symbolic algorithms to solve them, computer algebra practitioners are driven in a natural way to operating within a rather imprecise (and usually undefined in many papers) model of computation where basic arithmetic operations over a fixed ground field are assumed to be performed at unit cost. The formalization of the ``rather imprecise" model of computation yields, in fact, the most classical one in computer science: the algebraic complexity model (a concept that includes straight-line programs, computation trees, etc.).
Currently, Boolean complexity could be said to be more popular than algebraic complexity in the theoretical computer science curriculum. But the use of formal computation models in the complexity analysis of algorithmic problems arose in the algebraic theory. In the middle fifties, A.M. Ostrowski initiated a discussion on the optimality of Newton-Horner's rule for the evaluation of univariate polynomials. This was the birthday of a wide collection of techniques and results in algebraic complexity theory, that are now spread over forty years of mathematics and computer science literature. Even if one of the outstanding original motivations for this effort was the search for lower complexity bounds of classical algorithms, new interesting and efficient techniques for the manipulation of polynomials, matrices, power series and other algebraic entities have been developed in the frame of algebraic complexity theory, several of them with a certificate of optimality.
Unfortunately no systematic presentation of this mosaic of techniques and methods was available until now. In the middle seventies there was a first attempt, due to A. Borodin and I. Munro, to gather this information; but the approach in their book was not systematic, it had no continuation and, for the time being, its contents can be regarded rather as ``classical" than as useful. Of course, excellent surveys focusing on different parts of this theory have been published, but not aiming to present a panoramic viewpoint of the field. More than forty years after Ostrowski's paper, the present book sees the light as the first serious attempt to summarize, formalize and uniformize most of the contents of Algebraic Complexity Theory.
In our opinion, the book exceedingly accomplishes these goals. It is well-documented, very complete (except for subjects as uniform algebraic complexity, parallel complexity or connections with elimination theory; which are explicitly excluded), well-organized and formally correct. It can be used either as textbook for a graduate course (extracting some selected parts) or as a reference book for the professional. Concerning the first purpose, it must be remarked that this text includes a lot of examples, a collection of interesting exercises (ranging from direct applications to non trivial generalizations of previously introduced notions) and open problems. As a reference manual, the book provides sound introductions and motivations, reasonable discussions on alternatives and extensions, plus excellent bibliographical and historical notes for each chapter. It is, certainly, up to date.
On the negative side, we should say that the book seems less suitable for down-to-earth computer algebra users. That is, engineers or scientists that consider different sort of problems in their fields and that attempt to solve them via computer algebra tools. Is it reasonable to attack this problem in such way? What performance should I expect if I run this algorithm? What has complexity theory to advise me in these respects? The book is, perhaps, not the best reference for this purpose; although, probably, the answers to many such questions could be extracted from its contents .
Since the techniques in lower complexity bounds require many different mathematical topics, the book cannot be self-contained. However, the authors introduce the required mathematical notions and results with accurate references and comments, facilitating the task to those non familiar with a specific mathematical notion. In particular, the reviewers are in a position that allows them to enjoy the remarkable elegant presentation of some topics dealing with Computational Geometry and with Real Geometry. This effort yields a text which is both comprehensible and well-readable.
It is impossible to summarize with the desirable accuracy the contents of a book of this size. The following description does not intend to be exhaustive and will be, probably, misleading the reader in search of a concise recommendation. The book is organized as follows. There are five Parts, each divided into several Chapters.
Part I (Chapters 2-3) is devoted to some fundamental algorithms. Chapter 2 contains the design and analysis of algorithms that solve various problems concerning symbolic computation with polynomials and power series (manipulation, inversion, composition). Chapter 3 is devoted to branching programs with especial attention to the fast Knuth-Schnönhage computation of the greatest common divisor or to the theory of epsilon nets that shows how certain NP-complete problems can be solved in ``non-uniform polynomial time" (such as the Knapsack Problem or the Traveling Salesman Problem).
Part II (Chapters 4-7) is devoted to elementary lower bounds. In Chapter 4 the model of computation (straight-line programs and computation trees) is established. The remaining chapters deal with generic lower complexity bounds (transcendence degree, substitution techniques or the differential techniques concerning complexity of derivatives).
Part III (Chapters 8-12) concerns lower complexity bounds for high degree systems of polynomials. First, a systematic introduction to geometric degree lower bounds and to lower complexity bounds techniques for polynomials with algebraic and integer coefficients are presented. Then, the degree technique is applied to show lower complexity bounds for branching programs and computation trees. As for the real numbers framework, analogous results, based on connected components, is stated. Finally, the relation between real zeros of sparse systems and additive complexity is shown.
Part IV (Chapters 13-20) is devoted to lower complexity bounds of families of polynomials of low degree. Basically this concerns complexity of bilinear mappings. In this Part, more than 200 pages, key examples are discussed in detail. Let us highlight, among them, matrix multiplication, matrix-vector multiplication, the notable example of the discrete Fourier transform, and special types of matrices (Toeplitz, Hankel, Vandermonde). The chapters devoted to rank and complexity of algebras are of greatest interest.
Part V (Chapter 21) focuses on complete problems. The analogue of Cook's P=NP? Conjecture is Valiant's Hypothesis. This is well-introduced and discussed in this last Chapter.
In conclusion, this book belongs to the rising field of Computational Mathematics, a subject that lives between classical mathematics and computer science, taking the best from every field and generating, perhaps, a new branch of human knowledge. Of course, we claim that computer algebra is a part of this field. Because of the strong connections bounding up relevant parts of computer algebra and algebraic complexity theory, the book is a must for everyone interested in any of these two fields.
Contents