Catálogo de publicaciones - libros

This chapter is an expanded version of the lecture notes prepared by the second-named author for her introductory course at the CIMPA Graduate School on Systems of Polynomial Equations held in Buenos Aires, Argentina, in July 2003. We present an elementary introduction to residues and resultants and outline some of their multivariate generalizations. Throughout we emphasize the application of these ideas to polynomial system solving.

This chapter studies algebras obtained as the quotient of a polynomial ring by an ideal of finite codimension. These algebras have a rich supply of interesting linear maps whose eigenvalues, eigenvectors, and characteristic polynomials can be used to solve systems of polynomial equations. We will also discuss applications to resultants, factorization, primary decomposition, and Galois theory.

This tutorial gives an introductory presentation of algebraic and geometric methods to solve a polynomial system = ⋯ = = 0. The algebraic methods are based on the study of the quotient algebra of the polynomial ring modulo the ideal = (ƒ,..., ƒ). We show how to deduce the geometry of solutions from the structure of and in particular, how solving polynomial equations reduces to eigenvalue and eigenvector computations of multiplication operators in . We give two approaches for computing the normal form of elements in , used to obtain a representation of multiplication operators. We also present the duality theory and its application to solving systems of algebraic equations. The geometric methods are based on projection operations which are closely related to resultant theory. We present different constructions of resultants and different methods for solving systems of polynomial equations based on these formulations. Finally, we illustrate these tools on problems coming from applications in computer-aided geometric design, computer vision, robotics, computational biology and signal processing.

This chapter is devoted to laying the algebraic foundations for border bases of ideals. Using an order ideal , we describe a zero-dimensional ideal . The first and higher borders of can be used to measure the distance of a term from and to define -border bases. We study their existence and uniqueness, their relation to Gröbner bases, and their characterization in terms of commuting matrices. Finally, we use border bases to solve a problem coming from statistics.

This tutorial gives an introductory presentation of algebraic and geometric methods to solve a polynomial system = ⋯ = = 0. The algebraic methods are based on the study of the quotient algebra of the polynomial ring modulo the ideal = (ƒ,..., ƒ). We show how to deduce the geometry of solutions from the structure of and in particular, how solving polynomial equations reduces to eigenvalue and eigenvector computations of multiplication operators in . We give two approaches for computing the normal form of elements in , used to obtain a representation of multiplication operators. We also present the duality theory and its application to solving systems of algebraic equations. The geometric methods are based on projection operations which are closely related to resultant theory. We present different constructions of resultants and different methods for solving systems of polynomial equations based on these formulations. Finally, we illustrate these tools on problems coming from applications in computer-aided geometric design, computer vision, robotics, computational biology and signal processing.

This chapter is intended as a brief survey of the different notions and results that arise when we try to compute the algebraic complexity of algorithms solving polynomial equation systems. Although it is essentially self-contained, many of the definitions, problems and results we deal with also appear in many other chapters of this book. We start by considering algorithms which use the dense representation of multivariate polynomials. Some results about the algebraic complexities of the effective Nullstellensatz, of quantifier elimination processes over algebraically closed fields and of the decomposition of algebraic varieties when considering this model are stated. Then, it is shown that these complexities are essentially optimal in the dense representation model. This is the reason why a change in the encoding of polynomials is needed to get better upper bounds for the complexities of new algorithms solving the already mentioned tasks. The straight-line program representation for multivariate polynomials is defined and briefly discussed. Some complexity results for algorithms in the straight-line program representation model are mentioned (an effective Nullstellensatz and quantifier elimination procedures, for instance). A description of the Newton-Hensel method to approximate roots of a system of parametric polynomial equations is made. Finally, we mention some new trends to avoid large complexities when trying to solve polynomial equation systems.

Toric (or sparse) elimination theory uses combinatorial and discrete geometry to exploit the structure of a given system of algebraic equations. The basic objects are the Newton polytope of a polynomial, the Minkowski sum of a set of convex polytopes, and a mixed polyhedral subdivision of such a Minkowski sum. Different matrices expressing the toric resultant shall be discussed, and effective methods for their construction will be described based on discrete geometric operations, namely the subdivision-based methods and the incremental algorithm. The former allows us to produce Macaulay-type formulae of the toric resultant by determining a matrix minor that divides the determinant in order to yield the precise resultant. Toric resultant matrices exhibit a quasi-Toeplitz structure, which may reduce complexity by almost one order of magnitude in terms of matrix dimension.

We discuss perturbation methods to avoid the vanishing of the matrix determinant, or of the toric resultant itself, when the coefficients, which are initially viewed as generic, take specialized values. This is applied to the problem of implicitizing parametric (hyper)surfaces in the presence of base points. Another important application from geometric modelling concerns the prediction of the support of the implicit equation, based on toric elimination techniques.

Toric resultant matrices reduce the numeric approximation of all common roots of a polynomial system to a problem in numerical linear algebra. In addition to a survey of recent results, this chapter points to open questions regarding the theory and practice of toric elimination methods.

In a 1996 paper, Andrew Sommese and Charles Wampler began developing a new area, “Numerical Algebraic Geometry”, which would bear the same relation to “Algebraic Geometry” that “Numerical Linear Algebra” bears to “Linear Algebra”.

To approximate all isolated solutions of polynomial systems, numerical path following techniques have been proven reliable and efficient during the past two decades. In the nineties, homotopy methods were developed to exploit special structures of the polynomial system, in particular its sparsity. For sparse systems, the roots are counted by the mixed volume of the Newton polytopes and computed by means of polyhedral homotopies.

In Numerical Algebraic Geometry we apply and integrate homotopy continuation methods to describe solution components of polynomial systems. In particular, our algorithms extend beyond just finding isolated solutions to also find all positive dimensional solution sets of polynomial systems and to decompose these into irreducible components. These methods can be considered as symbolic-numeric, or perhaps rather as numeric-symbolic, since numerical methods are applied to find integer results, such as the dimension and degree of solution components, and via interpolation, to produce symbolic results in the form of equations describing the irreducible components.

Applications from mechanical engineering motivated the development of Numerical Algebraic Geometry. The performance of our software on several test problems illustrates the effectiveness of the new methods.

Polynomial factorization is one of the main chapters of Computer Algebra. Recently, significant progress was made on absolute factorization (i.e., over the complex field) of a multivariate polynomial with rational coefficients, with two families of algorithms proposing two different strategies of computation. One is represented by Gao’s algorithm and is explained in Lecture 2. The other is represented by the Galligo-Rupprecht-Chèze algorithm, presented in Lectures 4 and 5. The latter relies on an original use of the monodromy map attached to a generic projection of a plane curve on a line. It also involves zero-sums relations (introduced by Sasaki and his collaborators) with efficient semi-numerical computations to produce a certified exact result.