Solving systems of polynomial equations.

*(English)*Zbl 1101.13040
CBMS Regional Conference Series in Mathematics 97. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3251-4/pbk). viii, 152 p. (2002).

Finding effective methods for solving polynomial systems of equations defined over \(\mathbb{Q}\) is one of the topics which lies at the heart of computational commutative algebra. It is not just one of the historic roots of this area, but it has also immediate applications in science and engineering. Therefore it is not surprising that recently a number of monographs have taken up this subject: the various chapters of [A. Dickenstein and I. Z. Emiris, “Solving polynomial equations”, Alg. Comput. in Math. 14, Berlin: Springer 2005; Zbl 1061.12001], Chapter 3.8 of [M. Kreuzer and L. Robbiano, “Computational Commutative Algebra 1, Springer, Heidelberg (2000; Zbl 0956.13008)], Chapter 2 and 6 of [A. M. Cohen, H. Cuypers and H. Sterk, “Some tapas of computer algebra”, Alg. Comput. Math. 4, Springer (1999; Zbl 0924.13021)], and the book [H. J. Stetter, “Numerical polynomial algebra”, SIAM 472, (2004; Zbl 1058.65054)] all discuss various aspects of this topic.

The strength of the book under review is that it brings the different facets of the theory together in a clear and understandable way, and even supplements them with the latest developments in the field. After reviewing the classical methods for symbolic and numeric computation of roots of univariate polynomials in chapter 1, including real root counting and Puiseux series, Sturmfels explains the main Gröbner basis techniques for dealing with 0-dimensional polynomial ideals in the second chapter. Both the shape lemma and the Auzinger-Stetter method based on simultaneous eigenvalues of companion matrices are treated in detail. If the system is defined by \(n\) sparse polynomial equations in \(n\) indeterminates, Gröbner basis methods are frequently not the best choice. Chapter 4 introduces polyhedral techniques such as mixed subdivisions of Newton polytopes and Khovanskii’s theorem on fewnomials which count and compute the zeros of this kind of complete intersections. Further chapters treat methods using resultants and primary decompositions.

The second part of the book applies the methods discussed so far to several fields of interest. The first application deals with polynomial systems in economics, in particular with the equations defining Nash equilibria of finite \(n\)-person games. Other applications deal with semidefinite programming, global optimization of real polynomials, polynomial systems in statistics and polynomial solutions of linear partial differential equations with constant coefficients. A particulary interesting topic leading up to an active area of current research is introduced in the penultimate chapter: tropical algebraic geometry. Methods for solving systems of polynomial equations in the tropical semiring promise to have wide-ranging applications and have not been treated in monograph before. The book is written in an lively style with many examples, comments, computer algebra sessions and a generous dose of tempting exercises. It can be read with a reasonably good knowledge of basic algebra and is well suited for a lecture course on the graduate level. For the researcher who wants to get an accessible introduction to current techniques in polynomial system solving it can be highly recommended.

The strength of the book under review is that it brings the different facets of the theory together in a clear and understandable way, and even supplements them with the latest developments in the field. After reviewing the classical methods for symbolic and numeric computation of roots of univariate polynomials in chapter 1, including real root counting and Puiseux series, Sturmfels explains the main Gröbner basis techniques for dealing with 0-dimensional polynomial ideals in the second chapter. Both the shape lemma and the Auzinger-Stetter method based on simultaneous eigenvalues of companion matrices are treated in detail. If the system is defined by \(n\) sparse polynomial equations in \(n\) indeterminates, Gröbner basis methods are frequently not the best choice. Chapter 4 introduces polyhedral techniques such as mixed subdivisions of Newton polytopes and Khovanskii’s theorem on fewnomials which count and compute the zeros of this kind of complete intersections. Further chapters treat methods using resultants and primary decompositions.

The second part of the book applies the methods discussed so far to several fields of interest. The first application deals with polynomial systems in economics, in particular with the equations defining Nash equilibria of finite \(n\)-person games. Other applications deal with semidefinite programming, global optimization of real polynomials, polynomial systems in statistics and polynomial solutions of linear partial differential equations with constant coefficients. A particulary interesting topic leading up to an active area of current research is introduced in the penultimate chapter: tropical algebraic geometry. Methods for solving systems of polynomial equations in the tropical semiring promise to have wide-ranging applications and have not been treated in monograph before. The book is written in an lively style with many examples, comments, computer algebra sessions and a generous dose of tempting exercises. It can be read with a reasonably good knowledge of basic algebra and is well suited for a lecture course on the graduate level. For the researcher who wants to get an accessible introduction to current techniques in polynomial system solving it can be highly recommended.

Reviewer: Martin Kreuzer (Dortmund)

##### MSC:

13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |

14Q99 | Computational aspects in algebraic geometry |

65H10 | Numerical computation of solutions to systems of equations |

12D10 | Polynomials in real and complex fields: location of zeros (algebraic theorems) |

14P10 | Semialgebraic sets and related spaces |

52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |

35E20 | General theory of PDEs and systems of PDEs with constant coefficients |