The TERA Development Group as an interface between mathematicians and computer scientists

This is a note appearing in the Proceedings of TERA'97.

It is well known that the currently available software for polynomial equation system solving does not live up to the expectations of their potential users when it comes to the computation of realistically sized problems. The typical symptoms are out-of-memory errors or non-terminating programs.

There is strong theoretical evidence that elimination procedures face major complexity problems, for example it has been shown that algebraic elimination problems are typically EXSPACE-complete problems [8]. Algorithms based on Standard or Gröbner bases (using a dense representation of the multivariate polynomials) have necessarily exponential time complexity lower bounds (see for example [3], [7]), [2]). Note that this is also the case for geometric elimination procedures in the sense of [5], when the output is required to be given in dense representation. Considerations of a minimum numerical stability necessary for the correct production of solutions with a general purpose solver lead to the demonstration of exponential time complexity lower bounds in [6].

A fundamental conclusion to be drawn from these results is twofold: on the one hand, it is impossible to avoid the exponential time complexity of elimination algorithms while insisting on a dense representation, and on the other hand, one has to give up the idea of building general purpose solvers, ignoring thus any geometric or other intrinsic properties of the input systems.

Based on these observations, the theoretical work within the TERA Project and other scientists (mainly based on the use of alternative, problem-adapted data structures, called straight--line programs) have produced many interesting results during the last few years (see e.g. the TERA WWW pages at This work resulted in two papers [4] and [1], exhibiting an algorithm for the solution of geometric elimination problems. The time and space complexity is polynomial in the syntactic parameters and a suitably defined geometric degree of the input system.

As a consequence, it becomes now necessary to verify whether these algorithms are suitable for the real world. The TERA Development Group was organized to provide a first working prototype for experimental purposes.

This implies working on many different aspects at the same time:

Facing these tasks, the TERA Development Group is currently composed of members of the TERA project as well as other members from the Departments of Mathematics and Computer Science of the School of Science of the University of Buenos Aires, and the School of Mathematics, Astronomy and Physics of the University of Córdoba, Argentina.


B. BANK, M. GIUSTI, J. HEINTZ, M. MANDEL, G. MBAKOP: Polar varieties and efficient real equation solving: the hypersurface case. Journal of Complexity 13(1) (1997) 5--27.

T. DUBÉ: The structure of polynomial ideals and Gröbner basis. SIAM Journal of Computing 19 (1990) 750--773.

M. GIUSTI: Complexity of standard basis in projective dimension zero. Lecture Notes in Comp. Science 378, Springer (1989) 333--335.

M. GIUSTI, K. HäGELE, J. HEINTZ, J.E. MORAIS, J.L. MONTAñA, L.M. PARDO: Lower Bounds for Diophantine Approximation. Proceedings of MEGA'96, Journal of Pure and Applied Algebra 117 & 118 (1997) 277--317.

M. GIUSTI, J. HEINTZ, J.E. MORAIS, J. MORGENSTERN, L.M. PARDO: Straight--Line Programs In Geometric Elimination Theory. To appear in J. of Pure and App. Algebra (1997).

J. HEINTZ, G. MATERA, L.M. PARDO, R. WACHENCHAUZER: About the intrinsic complexity of parametric elimination procedures. WAIT'97, Buenos Aires, Argentina (1997).

T. KRICK, A. LOGAR: Membership problems, Representation problems and the computation of the radical for one--dimensional ideals. Progress in Mathematics 94, Birkhäuser (1991) 203--216.

E. MAYR, A. MEYER: The complexity of the word problem for commutative semigroups and polynomial ideals. Adv. in Math. 46 (1982).