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 http://hilbert.matesco.unican.es/tera/). 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:

- The mathematical design of the algorithms described in
[4] and [1] has to be
reviewed. A detailed description of all the necessary ingredients
has to be written.
- The underlying linear algebra has to be redesigned for the specific
mathematical structures appearing during the algorithms, taking into
account the data-structures used for the representation of the theoretical
concept of
*straight--line programs*. - As the idea of using
*straight--line programs*corresponds in a natural way to a compression of the appearing objects by a functional encoding of the algorithm necessary for its evaluation, one of the main concerns is the analysis and design of suitable Pebble Games (Evaluation schemes for arithmetic circuits) for these specific algorithms. - The implementation of the resulting algorithms for the construction
of a working prototype requires the development of a programming
environment and associated tools for
*straight--line programs*. This corresponds to the design and efficient implementation of an abstract data type of*straight--line programs*, be it in`C++`or a functional programming language. - Finally, but not the least demanding, will be the
software-engineering tasks and realization of the practical computer
science aspects such as Machine Environment, Multi Processing and
Distributed Computing, Coding Standards and Reuse of Standard Software.

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.

**1**-
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. **2**-
T. DUBÉ:
*The structure of polynomial ideals and Gröbner basis*. SIAM Journal of Computing**19**(1990) 750--773. **3**-
M. GIUSTI:
*Complexity of standard basis in projective dimension zero*. Lecture Notes in Comp. Science**378**, Springer (1989) 333--335. **4**-
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. **5**-
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). **6**-
J. HEINTZ, G. MATERA, L.M. PARDO, R. WACHENCHAUZER:
*About the intrinsic complexity of parametric elimination procedures*. WAIT'97, Buenos Aires, Argentina (1997). **7**-
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. **8**-
E. MAYR, A. MEYER:
*The complexity of the word problem for commutative semigroups and polynomial ideals*. Adv. in Math.**46**(1982).