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

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.

References

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).