Report on G. Trujillo's thesis
Report on G. Trujillo's thesis
Efficient algorithms in Real Algebraic Geometry: Closed Formulae for Polynomial System Solving

L. Gonzalez-Vega (the thesis director)

Presented at the University of Cantabria (Spain)

February 1998

The thesis entitled ``Efficient algorithms in Real Algebraic Geometry: Closed Formulae for Polynomial System Solving" presents a collection of several methods and algorithms to solve polynomial system of equations especially when real solutions are looked for.

It is divided in four different parts. The first two parts are devoted to the zero dimensional case: the considered polynomial system of equations has a finite number of complex solutions. The second part analyzes the non-zero (real) dimensional case in the particular case of two unknowns and the third part presents some applications of the methods in the first two parts to the implicitation problem of parametric curves and surfaces and to the efficient manipulation of singularities.

The first part is devoted to show how to reduce any question about the solution of a polynomial system of equations with a finite number of complex solutions to a linear algebra question if a Groebner Basis of the considered polynomial system of equations (with respect to any monomial ordering) is available. For example several improvements of Hermite's Method (see [PRS] or [R96]) are introduced by presenting some useful ``factorization" of the Trace Matrix (the matrix whose rank and signature characterize the number of different complex and real solutions, respectively). In this way, and for the particular system

$$\matrix{ f_1 = 5y^2 + (3x + 7)y + 2x^2 + 5x - 11 \hfill \cr f_2 = y^3 + x^2y^2 + x^2y + 9x^2 - 12, \hfill}$$

Hermite's method gives the number of different complex and real solutions as the rank and signature of the matrix

$$\Phi_{J,1}=\pmatrix{ 8 & -{{109} \over {25}} & -{{29} \over ... ...ver {2441406250}} & {{2403054955973871} \over {152587890625}} }$$

while the algorithms introduced in this part give the number of different complex solutions as the rank of

$$P_{\bf Jac} = \pmatrix{ -{{1749} \over 2} & {{2485} \over 2}... ...1875}} & -{{56839} \over {750}} & {{44325837} \over {15625}} }$$

and the number of different real solutions as the signature of

$$P_{{\bf Jac}} \cdot {\rm Bez}_{J} = \pmatrix{ {{240319} \ove... ... {{25775} \over {18}} & {{8575} \over {18}} & {{5000} \over 9}}$$

To remark that these two matrices are ``smaller" than $\Phi_{J,1}$, that this behaviour is quite general but it is not always general.

The second part presents a family of methods allowing to reduce any question about the solutions of the considered polynomial system of equations to question about univariate polynomials. The main results of this part are a complete and general formulae to compute the number of real solutions inside a n-diemnsional rectangle, a new criteria to decide if a polynomial is or nor separating, a new presentation of the ``Generalized Shape Lemma" (see [ABRW] or [R96]), a new triangularization method by a ``well controlled" set of traces computations and the introduction of the notion of ``rectangular ideal" together with the study of its main properties related to polynomial system solving. For example, and for the particular system we are considering, the formulae introduced in this part show that the considered system is equivalent (same set of solutions) to:

$$\matrix{ {x \sp 8} + {{{29} \over {10}} \ {x \sp 7}} - {{{78... ...3}} - {{34800} \ {x \sp 2}} - {{535690} \ x} + {33735}}}\hfill}$$

The third part is to present how to use efficiently the computation of the topological degree to study polynomial systems of equations in the two unknowns case when the zero-dimensional hypothesis is no longer true (see [Ke]). For example the system

$$\matrix{ 9x^3 + 3x^2 + (2y^2 - 8y)x - 2y^2 + 8y -12 = 0 \hfi... ... (18y-45)x^2 + (24y-60)x + 4y^3 - 26y^2 + 64y - 60 = 0 \hfill }$$

is not zero-dimensional (an infinite number of complex solutions) but it has only one real solution (x=-5/3,y=2). This part contains algorithms to compute the topological degree, to isolate real solutions of systems as the previous one and the application of these tecniques to deal with the complex root counting problem for polygons.

The last part is devoted to two very important problems is Computer Aided Design for curves and surface: the implicitation problem for parametric curves and surfaces and the manipulation of singularities of algebraic curves and surfaces implicitly defined. The main tools used are the techniques introduced in the first two sections.

Most of the algorithms presented in this thesis have been implemented into the Computer Algebra Systems Maple and Axiom. They will be shortly available, together with the thesis postscript file (in spanish), from the www page http://frisco.matesco.unican.es/. English documentation containing some material from this thesis can be found at

• L. González-Vega and G. Trujillo: Using Symmetric Functions to Describe the Solution Set of a Zero Dimensional Ideal. Proceedings AAECC-11. Lectures Notes in Computer Science 948, 232-247, Springer-Verlag (1995).
• L. González-Vega and G. Trujillo: Implicitization of parametric curves and surfaces by using symmetric functions. Proceedings ISSAC'95, 180-186, ACM Press (1995).
• L. González-Vega and G. Trujillo: Multivariate Sturm-Habicht sequences: real root counting on n-rectangles and triangles. Revista Matemática de la Universidad Complutense de Madrid, Volume 10, 119-130 (1997).
• L. González-Vega, F. Rouillier, M.-F. Roy and G. Trujillo: Symbolic Recipes for real Solutions. Some ``Tapas" of Computer Algebra (to be published in 1998 by Springer-Verlag into the series ``Algorithms and Computations on Mathematics").