Solving systems of polynomial equations stands as one of the great challenges of computer algebra. Rewriting a polynomial in a simpler form using a set of polynomial equations is an important and closely related problem. This paper addresses the challenge of solving a system by developing a better way to simplify a polynomial with respect to that system.

The authors generalize the standard technique of simplification with respect to a monomial term ordering to create a framework of reducing families, reduction operators, and choice functions that leads to a generalized normal form for polynomials. Their generalization of term ordering builds on the Macaulay resultant and holds the potential for better numerical stability properties. They apply this framework to systems of polynomial equations with finitely many solutions where they use conventional numerical linear algebra techniques to compute the solution. The greater freedom in simplification afforded by this framework holds significant promise for improving our ability to solve systems of polynomial equations.

Solving systems of polynomial equations is a fundamental problem in computational algebraic geometry with applications throughout science and mathematics. Computer scientists seek to quantify how difficult it is to solve a system of equations, however until now, no one has succeeded in bounding the difficulty (or complexity) by anything better than pessimistic exponential bounds, except in a special case where all the coordinates of the solutions are polynomials in one distinguished coordinate (a so-called primitive element).

Dahan and Schost have achieved something remarkable: they broke through the exponential barrier of complexity in the general case and obtained the polynomial bounds that were known previously only in the special case. Reducing a system of polynomial equations to triangular form allows its solutions to be computed more easily. However, the equations in the triangular form might be significantly larger than the original equations, perhaps exponentially larger. They showed that the size of the equations in a triangular form is at worst a quadratic function, and sometimes a linear function (if quotients of polynomials are permitted), of the size of the solution set of the original equations. This breakthrough enhances our understanding of this important problem by showing that the triangular form is in general smaller and less complicated than previously thought and therefore easier to compute and solve. In fact, such a bound directly yields better modular algorithms for computing triangular forms.

Solving systems of linear equations is the fundamental problem of scientific computation. Over 2000 years ago, an early Chinese book on mathematics described algorithms to solve this problem. In our time, computer simulations of physical processes require solving sparse linear systems with huge numbers of unknowns. Researchers developed specialized algorithms based on methods of Krylov to solve these systems.

More recently, huge sparse systems of linear equations over finite fields have appeared in algorithms for factoring integers or for computing discrete logarithms. Krylov-based algorithms have been generalized to handle these systems. The security of modern cryptographic protocols that secure Internet communications and commerce rest their security partly on the difficulty of solving such linear systems, which increases our need to better understand such computations.

Experiments have suggested that a heuristic modification of Krylov-based algorithms improves performance in practice, but no theoretical analysis has been able to justify the experimental results or to prove the reliability of the heuristic. In his work, Eberly provides for the first time a theoretical justification for the observed experimental results, and he proves that we may rely on randomized Krylov-based algorithms without sacrificing performance. He provides new tight bounds for both the expected amount of look-ahead required when applying a randomized Lanczos algorithm, and the expected length of a sequence of zero-discrepancies that would be encountered when using a simple randomized version of Wiedemann's algorithm.

Finding roots of polynomials has a long and rich history in scientific computation. In most practical applications, measuring the coefficients of the polynomials involved can lead to errors that affect the accuracy and stability of algorithms that find roots of these polynomials. While we know excellent algorithms for finding single roots, accurately computing multiple roots of polynomials remains a challenge. Using for the first time the pejorative manifold introduced by Kahan, Zeng developed an algorithm that efficiently approximates multiple roots of polynomials, even ones with inexact coefficients, without resorting to slow calculations involving arbitrary precision software floating point numbers. He has also provided an efficient implementation that performs well in experiments, thereby advancing the state of knowledge in this field.

Solving systems of polynomial equations is a significant challenge that lies at the heart of computer algebra and symbolic computation. Dickenstein and Emiris have made a substantial contribution towards the understanding of formulas, called resultants, that solve systems of polynomial equations efficiently. They have demonstrated how to explicitly compute such formulas in an important special case and have described conditions when such formulas are the best that can be attained. In this special case of multihomogeneous resultants, they have shown how a combinatorial construction can be made intrinsic.

Since the nineteenth century, mathematicians have studied matrices whose entries are numbers or polynomials in one variable. Both mathematicians and computer scientists are interested in solving equations involving matrices and in finding natural ways to discover the structure of matrices by converting them into certain ``normal forms''. Storjohann has made a substantial contribution towards the development of symbolic matrix algorithms that efficiently solve equations and find normal forms of matrices of polynomials. His method of ``High-Order Lifting'' allows larger, complicated operations to be broken down into smaller steps that rely primarily on the simple yet efficient multiplication of matrices for the bulk of the work. His method improves theoretical estimates and practical performance of algorithms for these two problems as well as other applications.