Solving Polynomial Equations: Foundations, Algorithms, and Applications

Not too long ago, I was discussing with one of my freshman students what it is that we mathematicians do for research. He was convinced that the only thing mathematicians do all day is sit around trying to find solutions to big ugly equations. I (hopefully) talked him out of this notion, and tried to convince him that mathematics was about more than just looking at polynomials. After that long conversation, I hope that the student doesn't stumble across the new book Solving Polynomial Equations: Foundations, Algorithms, and Applications. If he does, he will find nine chapters by sixteen different authors on topics which are all related to finding the solutions of systems of polynomial equations all of which convince the reader that attempts to solve polynomials are every bit as much cutting-edge research as they were in the days of Cardano and Tartaglia.

The chapters of the book are independent and for the most part attempt to be self-contained, but on the other hand they often refer back and forth to one another, and different chapters assume different levels of understanding of different prerequisites. The book is based on course notes from a summer school held in Buenos Aires in July 2003 and sponsored by the International Centre For Pure And Applied Mathematics (CIMPA). While the chapters vary somewhat in the quality of their exposition, most of them are quite good and interesting introductions to the subjects at hand. The full table of contents can be found here, but this reviewer found the following chapters to be particularly interesting and representative of the topics in the whole book:

• David A. Cox has an excellent chapter in which he looks at the quotient ring by the polynomials we wish to solve and — recognizing that the multiplication operations in this ring are linear — uses methods of linear algebra methods to study how these algebras relate to topics such as primary decomposition and Galois theory. Much of this study comes from the so-called 'Finiteness Theorem' which says that K[x₁,...x_n]/< f₁,...f_s> will be finite-dimensional over K if and only if the f_i have a finite number of solutions over the algebraic closure of K.
  
• Mohamed Elkadi and Bernard Mountain write a chapter which in part expands on the ideas that Cox writes about, but focuses more on the results one can obtain by looking at explicit numerical methods for computing the eigenvalues and eigenvectors. This chapter has a particularly interesting final section, in which the authors discuss applications of their work on solving systems of polynomial equations to fields such as auto-calibration of cameras and robotic vision, computational biology, and signal processing.
  
• Juan Sabia writes on issues of algebraic complexity and in particular the complexity of many of the algorithms dealt with in the other chapters in the book. He introduces an effective version of Hilbert's Nullstellensatz which will tell us how to find a linear combination of any set of simultaneously nonvanishing polynomials which is equal to one. These discussions involve topics such as dense encoding, the Newton-Hensel method, and geometric resolutions.
  
• There is a chapter entitled "Introduction To Numerical Algebraic Geometry" by Andrew Sommese, Jan Verschelde, and Charles Wampler which gives a nice introduction of this very interesting field. They are interested in finding the explicit solutions to systems of polynomial equations, and their research uses homotopy continuation methods to look at these solutions. They not only discuss the theory of how one would use these methods, but also show some very explicit examples, as well as discussing software packages and how they hold up to certain benchmark calculations. Even the most abstract and cohomology-minded of algebraic geometers would find this chapter to give interesting insight into one niche of our field.

There are five other chapters, and all of them give interesting discussions of the topics at hand. The editors of the book — Alicia Dickenstein and Ioannis Emiris — have done a very good job in collecting a set of expository lectures on a very interesting branch of mathematics. I imagine that this book will be of use to anyone working in the area, and would be a good introduction for a graduate student or someone wishing to start working in the field. And while it gives a very compelling argument that finding the solutions to systems of polynomial equations is a very difficult, very interesting, and extremely useful thing to be able to do, I would still rather you didn't show the book to my student.

---

Darren Glass (dglass@gettysburg.edu) is an Assistant Professor at Gettysburg College. His mathematical interests include Algebraic Geometry, Galois Theory, Number Theory, and Cryptography.