The virtual world as a real trap for the scientist

J. Heintz^{∗}

May 15, 1997

Keywords. Polynomial system solving, complexity, the rise and fall of the occident

Why this talk is just publicity

Even if you may not notice during my talk, my main concern is making publicity for certain ideas of collaboration and joint advancement on goals which computer science and mathematics have in common. In a first part I will give you my point of view of the current situation of science in general and based on that in a second part the reason why we are doing what we are doing.

1 The virtual world as a real trap for the scientist

• The virtual world is not the last creation of modern computer engineering, it is not fancy, not imagination, not science fiction, but the reality of science today.

• The virtual world was created, institutionalized and bureaucratized when the modern science factories were built after World War II, at the end of the forties.

• The virtual world was the dream, the utopia of science at that time, fifty years ago, the world of human aided artificial intelligence, “electronic brains”.

The aim was eternal peace, no human suffering anymore and work for everyone. The dream of the scientists was to be as good as King Arthur and as wise as Merlin at the same time and to constitute a platonian Academy ruling with wisdom and modesty blessfully over a potentially bad world, exactly as in the platonian state. With the time this virtual world of the scientific elite became more and more virtual and far apart from reality.

Today, we face a development towards a post-industrial society where more and more traditional factories are closing down. This process is also knocking at the doors of the science factories (universities and research institutes). Once a motor of progress, the scientific utopia has become a mental prison for the scientists living and working for it. They have become unable to see the reality - and to find a job.

∗with the collaboration of G. Blücher

Scientific production has degenerated to an uncontrolled paperwriting leaving as “applications of research results” only even more uncontrolled “colaborations” with war industries. Science today becomes more and more divided into “pure” or “fundamental” (meaning proper but useless) research activities and secular, materialist “applied” Research and Development (R & D) (accidentially dangerous and very efficient at killing the hen laying the golden eggs).

In this general view Argentina is not different from other countries of the world. However the crisis and struggle in Argentina reach unexpectedly deep layers of the society. Both government and scientific community are blind to the neccessary changes, being prisoners of their own lack of perspective and their overcome traditionalism.

• Education - and in particular higher and professional education - is practically the only and by far the most efficient lever which remains in the hands of the argentinian rump state (see Camdessus (1996)).

• Education is the last chance to fight against unemployment (and its social consequences) and technological dependence (and its economic consequences).

• Education is much cheaper and much more efficient that sophisticated economic politics and it is pity that the argentinian society is going to loose this last chance.

On the other hand the inadequacy of argentinian scientists (living in their virtual world) their unwillingness to learn new things, to change the teaching contents at the universities, their mental dependence on external recognition, their paperwriting-at-any-price makes the modernisation of the educational system practically impossible.

After this apocalyptic view of our social reality I want to adress a more technical subject: The place of argentinian science in the world of theory and software in symbolic computation. The emphasis of my talk will be on the hardest R&D problem the symbolic computation community faces: The development of computer aided techniques for the simplification and subsequent solution of polynomial (and algebrodifferential) equation systems.

My reasons for selecting precisely this subject are the following:

• I know something about the subject,

• it is the only subject I know something about, • I happen to do research in the field, therefore it surely must be important.

• Symbolic computation is the only discipline of applications where “poor” mathematics hopefully one day will be useful.

• The present society gives rise to problems (in form of polynomial and algebrodifferential equation systems) and needs solutions (i.e. procedures to solve these systems), instead of theorems talking about schemes, varieties, D-modules etc.

To establish such procedures is a vital task for the communities of mathematicians and theoretical computer scientists. Whether this task is accomplished or not will decide over success or failure of the science production factories within the next ten years.

• Mathematicians and computer scientists must cooperate to solve the problems addressed in this talk.

To overcome the enormous complexity problems arising from the algorithmic treatment of polynomial equation systems, both geometrical insights (semantics of the system) and skillful handling of the data structures (syntax of the system) are crucial.

• Doing so argentinian scientists (in this case mathematicians and computer scientists) are confronted with the real needs of computing in engineering (and natural sciences). They get in touch with real needs of the real society outside their virtual world.

• The research work done in Argentina in symbolic computation already influenced teaching in geometry (mainly analytic and algebraic but also semialgebraic and diophantine geometry) and in theoretical computer science (algebraic and boolean network complexity).

• the impact of the argentinian theory production on the mainstream of todays symbolic computation is recognized world-wide. Let us go on before they close the factory!

Fields already developed in Argentina received new impulses in teaching and research (number theory, global optimization). New enthusiasm was created amongst students, being really motivated by the challenge of symbolic computation. For a general view of new directions in theoretical computer science and in symbolic computation I refer to Aho et al (1996) and Odlyzko (1995).

Let me just say that what is coming now is not the history of computer science in Argentina (hopefully it will be one day part of it). Computer Science in Argentina has its roots in mathematical modelling, scientific computing, numerical analysis and computer linguistics.

It started in the early sixties with different working groups organized by M. Sadosky around a Mercury Ferrand computer (called “Clementina”) in the Centro de Cálculo of the Faculty of Sciences at the University of Buenos Aires. Important collaborators were (the list is not exhaustive) Jonas Paiuk (hardware), Durand (programming), M. Gradowczyk (continuum mechanics), O. Varsavsky (mathematical modelling), J. Araoz (mathematical modelling, later optimization). The most noteworthy fact is maybe that at that time Argentina was pioneer in computer linguistics (morphology and lexicology of slavic languages) by a team led by E. Fisher (see Jacovkis (1997))

Although the tradition of the former centro de cálculo continues today in the form of a computer center directed by P. Jacovkis at the same place, there was a rupture in the history during the dictatorship of Onganía. Modern computer science started in Argentina in the early eighties and my talk refers only to this more recent chapter of the history.

2 TERA

Since about 12 years there exists evidence that effective elimination in algebraic and semialgebraic geometry faces serious complexity problems in theory and practice. On one side it is known that general quantifier elimination procedures in algebraic and semialgebraic geometry intrinsically require doubly exponential time and singly exponential (memory) space (Heintz (1989); Weispfennig (1988); Davenport & Heintz (1988); Montaña & Pardo (1993)) and that typical algebraic problems in polynomial rings (as the membership problem for polynomial ideals) are complete in exponential space (Mayr & Meyer (1982); Demazure (1985); Bayer & Stillmann (1988); Yap (1991)). On the other hand previous work mainly done in Argentina shows that a long list of fundamental geometric (i.e. not algebraic) problems are algorithmically solvable in polynomial space (the corresponding time complexity is singly exponential in the number of variables. See e.g. Caniglia et al. (1988) and (1989), Dickenstein et al. (1991), Giusti & Heintz (1991), Heintz et al. (1989, 1990, 1994), Matera (1997), Matera & Turull (1997).

In Heintz & Morgenstern (1993) and Pardo (1995) there is given mathematical evidence that the singly exponential worst case behavior of the time complexity of geometric algorithms is unavoidable if the input is given by a straight–line program and if the only parameter measuring the size of the input is measured only by syntactical parameters. This evidence is presented in terms of (relative) structural complexity and in terms of ‘absolute” complexity (however in restricted computational models). With respect to structural complexity we can say that the assumption that algorithmic elimination can be performed in polynomial sequential time implies that the arithmetic time hierarchy collapses up to high degrees (in particular we deduce P = NP) and that the same happens with respect to nonuniform computation models (e.g. Valiant’s thesis would be wrong). See in this context also Blum et al.

(1996), Matera (1997), Koiran (1996).

With respect to “absolute” results we have still to make some restrictions on the form of the outputs or the form of the straight–line program which represents it, but also in this case negative evidence is overwhelming (e.g. Heintz & Matera & Wachenchauzer (1997) and Matera (1997)). Further research on lower complexity bounds is neccessary to close this gap definitively.

As a by-product of the mentioned work on polynomial space algorithms for elimination problems one finds algorithms of roughly optimal sequential time complexity if the dense coding of polynomials is consequently used. Typically these algorithms are of polynomial character in the size of the output (see also Chistov & Grigor’ev (1983) and for the real case Grigor’ev & Vorobjov (1988); Canny (1988); Heintz & Roy & Solernó (1989, 1990), Renegar (1992); Heintz & Roy & Solernó (1994). This means theoretically and practically that any general purpose procedure or program based on the sparse or dense coefficient representation of polynomials and the bit representation of rational numbers must have a characteristic time complexity of type d^{O(n^{2})}, where d is the maximal degree and n is the number of variables of the input polynomials of the problem under consideration. Unfortunately this is the typical complexity behavior of rewriting based (i.e. Groebner basis) algorithms even in their most efficient versions and implementations. Since this theoretial and practical complexity behavior of elimination procedures is inherent to a certain data structure (the simple representation of polynomials by their coefficiente vectors and the representation of numbers by writing down their bits in a list) and cannot be improved just by searching for more efficient algorithms, the question arises whether there exist better suited, i.e. more succinct data structures for the representation of the particular polynomials and numbers which typically appear in elimination procedures.

2.1 New Data Structures in Elimination Theory

The complexity problem addressed in the previous section leads to a new generation of elimination algorithms based on the abstract data type Directed Acyclic Graph, “DAG” for short (see Giusti& Heintz (1993), Giusti et al. (1993), Fitchas et al. (1995) , Krick & Pardo (1994, 1996); Puddu & Sabia (1997), Giusti et al. (1995, 1996, 1997a, 1997b); Bank et al. (1996)). The cornerstone of the new algorithms and their complexity relies on the observation that the polynomials appearing as intermediate results during the execution of any elimination process own typically a straight–line program encoding which is much shorter than their usual dense or sparse representation. Furthermore, if we consider these polynomials as being univariate with respect to some distinguished variable, the complexity of their interpolation is polynomial in their degree and their circuit size. The new algorithms use as far as possible circuit (straight–line program) encoding for the representation of polynomials and employ coefficient representation at most with respect to one single variable. These “univariate” polynomials which appear during our elimination procedures are eliminating forms and describe suitable projections of algebraic varieties produced by the algorithm. Being eliminating forms they have inherently ”small” circuit size (i.e. circuit size which is polynomial in their degree and the length of the input).

This observation allows the procedure to compress periodically the potentially expanding DAGs which codify the data. The resulting sequential time complexity of these elimination procedures is finally polynomial in all parameters which measure their behavior: the extrinsic parameters number of variables, degree of input equations and their circuit length and an intrinsic parameter, which is a suitably defined “degree of the input system” (see Giusti et al. (1995, 1996, 1997a, 1997b); Bank et al. (1996)). As far as arithmetic operations are counted only at unit costs this description of the complexity character of these algorithms is quite exact.

For bit complexity considerations one has to take into account the (logarithmic) height of the input polynomials and a suitable defined “height” or “arithmetic degree” of the input system. Again it turns out that the algorithms have a bit complexity which is polynomial in the afore mentioned parameters. These algorithms allow to distinguish between “well suited” and “ill posed” polynomial equation system. The well suited systems are those whose degree (and height) are “small” in comparision with the product of the degrees of the input polynomials (this quantity is called the “Bézout number” of the system). Ill posed systems are those having degree (and height) close to the Bézout number (combinatorial problems typically produce such systems).

As far as worst case complexity is concerned, for the first time elimination procedures which are polynomial in the Bézout number of the input system are obtained in this way. This was up to now impossible even for special systems (see Mourrain & Pan (1997) where such a result is intented, but not achieved for so called Pham systems).

In this context let us to remark that any system which has the property to be “well suited” in the above sense is provably difficult to tackle by pure numerical methods (this follows from an application of a suitable multivariate version of Liouville’s classical theorem on diophantine approximation, see Giusti et al. (1997a)).

To summarize, the complexity of this new generation of algorithms depends essentially on two groups of parameters, namely a group of syntactical ones which measure the (extrinsic) length of the input description and a group of semantical ones which measure the intrinsic geometric (and arithmetic) character of the input system. With respect to these two groups of parameters, the algebraic and the bit complexity of the new algorithms have polynomial character. In particular, there is no exponential (or hyperexpontial) dependence of the complexity of these algorithms on the number of variables occurring in the input equations, as this is the case in rewriting based procedures. Moreover the input systems may depend on symbolic parameters as this often happens in application problems in engineering, physics or chemistry. (By the way, symbolic parameters often modelize the dependence of the input system on ”numerically given real values”). The new algorithms accept as inputs straight–line programs and the length of this representation depends only linearly on the number of variables.

On the other hand, the degree of the input system is bounded by a function which is polynomial in the degree of the input equations and single exponential in the variables to be eliminated (namely the Bézout number of the system). At worst (and this is the generic case) this bound is reached, which makes the worst case complexity of the new algorithms exponential. Therefore they are infeasible for a generalistic treatment of all possible systems. Nevertheless the question remains open whether in many practical applications the geometric (and arithmetic) degree of the system remains “small” and in this case the new algorithms are able to take this particular circumstance into account (rewriting based algorithms generally can not do so).

A special feature of the new algorithms consists in the circumstance that their main subroutine (the compression of intermediate data) is based on an algorithmic flat deformation of a certain morphism of affine varieties occurring as intermediate result of the procedure. This subroutine can be isolated from this context and be used as an independent procedure transforming suitable special solutions of a given input system into a general solution. This allows in many cases (e.g. when a group of “symmetries” is acting on the solutions of the input system) a treatment of the input system by low degree polynomials even in presence of a high system degree. This brings modern Computer Algebra procedures back to the classic (but forgotten) viewpoint of Hilbert on “Invariantentheorie” (see Heintz (1997) and Waissbein (1997) for a list of examples and Kraft (1996) for a historical interpretation of Hilberts viewpoint). The question remains open whether there exists a possibility of finding algorithms whose complexity is independent of the degree of the input system and polynomial only in the length of the input given by a straight–line program or in sparse representation. As we have seen before, one has to expect a negative answer to this question.

Closest to the mentioned complexity results in symbolic computation comes in the numerical context the work of M. Shub and S. Smale about the complexity of finding approximate zeroes of polynomial equation systems (recall that an approximate zero is a starting point for Newton iteration). Recognizing the fact, that there does not exist a straightforward comparison between symbolic and numerical methods in polynomial equation solving, I content myself with pointing out two fundamental differences between the symbolic algorithms and those of M. Shub and S. Smale (see e.g. Shub & Smale (1994)). First of all, the bit complexity aspect of the computations and its relation to diophantine approximation is not considered in the work of M. Shub and S. Smale. Secondly the input must be given in dense representation and the best complexity behaviour is only obtained for generic systems (which makes the distinction between well suited special and ill posed generic systems obsolete). As a consequence they obtain interesting worst case bounds for the task of approximating zeroes of generic polynomial equation systems but they do not produce problem adapted algorithms for solving special polynomial equation systems as they occur in practical applications. Similar observations may be made with respect to another research direction which is oriented toward the development of fast algorithms for sparse systems (see e.g. Canny-Emiris (1993), Emiris (1996)).

The complexity analysis of the symbolic algorithms discussed before is primarily based on a theoretic (in fact “seminumeric”, “arithmetic” or “algebraic”) model which counts arithmetic operations at constant instead of “real life” bit costs. This complexity model was created in the fifties by A. M. Ostrowski and A. N. Kolmogorov and reflects quite well the computer science aspect of floating point arithmetics (disregarding however aspects of numeric stability). The theoretic complexity analysis in terms of this model would therefore suggest a numerical implementation of the new generation of symbolic algorithms making use of already existing packages with high performance floating point arithmetics. Numeric subroutines have the advantage that they can be very well combined with the abstract data type “straight–line program” (observe that the notion of “straight–line program” modelizes the compiled form of a FORTRAN program). The only theoretic (not pragmatic) argument which speaks against this symbolic/numeric hybridization is based on the mathematical theory of diophantine approximation. One of the key results of this theory is the theorem of Liouville mentioned above (in fact it was the starting point of this field in the 19-th century) saying that the solutions of polynomial equation systems are hard to approximate (because they are typically algebraic numbers). This result implies that we will never dispose of a satisfactory mathematical theory which justifies theoretically what we are practically doing when combining floating point arithmetics with the symbolic algorithms discussed before. I think that it is worth to test the pragmatic value of this hybridization disregarding the lack of theoretic foundation in the hope that the “worst case” which corresponds to Liouville’s estimate is practically less relevant.

2.2 The implementation of a theory

A way out from this dilemma between pragmatics and theory consists in the following cornerstone of the research and implementation work which is going on in Argentina, Spain and France at this moment: the theoretic algorithms discussed before all admit an easy and efficient modularization by not too big random integers. One obtains in this way efficient random algorithms whose error probability can be explicitely bounded by means of a suitable application of the Prime Number Theorem. This randomization allows the transfer of the arithmetic complexity model to its boolean counterpart which is the only relevant in “real life” computer science. It is unavoidable that elimination procedures produce extremely big integers but these integers are very special: they have typically a “short” straight–line program codification. This codification can be easily translated to the setting of boolean circuits by means of the modularization mentioned before and a suitable random choice of moduli allows a “remote control” of the original big numbers. First and promising theoretical results in this direction have been obtained in Hägele & Montaña (1996) and an ad hoc implementation (M. Aldaz (1996)) of these results has already proved the high practical performance of this new approach.

The fact that the computer algebra community now disposes of procedures which are able to distinguish between “well suited” and “ill posed” polynomial equation systems is a strong motivation for tackling an implementation activity which profits from the theoretical algorithmic advances. Such work requires a new programming philosophy because we have to represent and to simulate circuits in a computer (which is nothing else than a big but limited circuit). This programing philosophy was applied first in San Luis (Argentina) by the working group formed by A. Grosso, N. Herrera, M. E. Stefanoni and J. M. Turull. Starting with an implementation adapted application of Borodin’s transformation of any log^{2} -space uniform NC^{2} circuit into a log^{2}−space sequential program (cf. Borodin (1977)) to the arithmetic NC^{2} circuit underlying Berkowitz algorithm (Berkowitz (1984)) for the computation of the characteristic polynomial of a given matrix (compare Matera & Turull (1997)) this group developed a C-program which in principle is able to solve linear equation systems with rational entries in memory space log^{2} of the size of the input (see A. Grosso et al. (1996)). We say “in principle” because in the low technology conditions in which this group has to work, only parts (however substantial ones) of the program could be tested. The syntactical form of the program represents for the first time a rigourous proof of the often claimed but never shown fact that the boolean circuits underlying linear algebra routines can be generated in log^{2} space. Applied to the new generation of elimination algorithms this implies the existence of algorithms for symbolically solving polynomial equation systems which are not substantially slower than those implemented in current commercial software having the additional property that they run in polynomial memory space (see Matera & Turull (1997); Matera (1997)). In view of the existing user experience with symbolic software packages, the practical impact of this theoretical result cannot be underestimated but the way one still has to go is extremely long. For the moment we can only conclude that it is feasible to write programs which are greedy with memory space but there is still no evidence that such programs are feasible to run on “real world computers”. In order to settle this question theoretical research on time-space trade-offs was intensified within the community (Aldaz et al. (1996); Aldaz et al. (1997).

An outstanding aspect of the program developed in San Luis is the fact that this program generates the boolean circuits which are evaluated during the procedure.

This poses subtle questions on the choice and the manipulation of the underlying data structures. Nevertheless the program is skillfully modularized and stable. It represents a valuable experimental tool for further research on the mentioned question of time-space trade-offs.

In the same year as the team in San Luis, namely in 1994, another working group belonging to the same community started programming based on the abstract data type DAG. This group works under the direction of J. Llovet at the Universities of Alcala de Henares and Ingenieros Industriales (Madrid) and their members are (apart from J. Llovet) B. Castaño (Alcala) and R. Martinez (Escuela Politecnica de Madrid). The programming activities of this group have a more pragmatic orientation toward the production of a first, although possibly coarse prototype to furnish further evidence for the relevance of the DAG data type for polynomial equation solving. The circuit representation of polynomials and integers was implemented and the program (which for the moment is written in PASCAL) manipulates and evaluates this data structure. The program accepts polynomials in sparse form as inputs and converts them into a suitable arithmetic circuit. This circuit may for example represent a square matrix. The program is able to compute the coefficients of the characteristic polynomial of this matrix (or its determinant). The output is given as an arithmetic circuit (straight–line program). This simple idea can be used to write a highly efficient routine for the computation of the greatest common divisor (gcd) of two multivariate polynomials in circuit representation. In order to obtain a practically executable program circuits are not generated (as in the implementation of the San Luis group) but fully displayed in the memory storage of the computer during the running of the procedure.

First experimentation with this program (called “TERA”) gave impressive comparative results (see Castaño et al. (1996)). The following data might give a flavor of this: the program was tested computing the characteristic polynomial of a test suite of square matrices with polynomial entries. These entries were random polynomials of degree 3 in 8 variables having 10 terms in sparse representation. Whereas the standard MAPLE procedure for this task was unable to process matrices of this kind having size larger than 3 × 3 the program “TERA” ran fast and successfully on inputs representing up to 11 × 11 matrices. The program is stable and despite of the unsuitable programming language used (the memory management of PASCAL is not very well qualified for our aim) the advantages of the circuit data structure for the representation of polynomials is clearly visible.

Let us also mention that the program “TERA” contains as a second application a routine computing the gcd of two multivariate polynomials given by straight–line programs. Even though MAPLE is very efficient for the computation of polynomial greatest common divisors, first experiments show that the program “TERA” gains at least a speedup of factor 10 (see Castaño et al. for a description of the program).

A C++ version of the “TERA” program with algorithms having a more problem adapted time–space tradeoff is planned. The same programming philosophy as in Alcala was applied by M. Aldaz in Pamplona (Universidad Pública de Navarra) who wrote a special purpose C++ program for the treatment of large numbers given by arithmetic circuits. As mentioned before his work relies on the theoretical results of Hägele & Montaña (1996). The program is able to generate and manipulate rational numbers in circuit representation and to check equality between them. The program is stable and well modularized. The inclusion of an efficient routine which is able to convert a given circuit representation for a rational number of small logarithmic height in the bit representation of the corresponding reduced fraction is planned.

Although the commercial version of MAPLE is not able to handle large matrices whose entries are polynomials in many variables, this software package is flexible enough to support a radical change towards the abstract data type called straight– line program or DAG. It happens that MAPLE was based from its very beginning on the basic data structure DAG, which is just hidden for the common user (but not for the specialist). MAPLE is able to handle DAG’s and to evaluate them. Unfortunately the DAG philosophy is not consequently applied in MAPLE and identity between polynomials is not checked by a simple evaluation test, such as Heintz & Schnorr (1982) in combination with Hägele & Montaña (1996) or the so called Zippel–Schwartz test (see Schwartz (1980); Zippel (1990)) in combination with Schönhage (1979) or Ibarra& Moran (1983). For the test of identity between polynomials stored as a DAG (e.g. when running the Gauss algorithm on a matrix with polynomial entries) MAPLE converts the given DAG representation in a (sparse or dense) coefficient representation of the polynomials under consideration. The result of this conversion is an object which is often too large to be handled by the program. Mutatis mutandi the same thing can be said about the representation of rational numbers and integers in MAPLE. This small difference between our fragmentary programs and the MAPLE software has the already mentioned big consequences when running a procedure. Not the quality of the algorithms or the skillfulness of the programming work makes that difference but the consequent use of the same, problem adapted data structure. This explanation makes clear that MAPLE is flexible enough to be used for the prototyping of our new algorithms which are based on the abstract data type DAG. This fact was pointed out to me by B. Salvy (INRIA, Rocquencourt) and J. Marchand (École Polytechnique, Palaiseau). They started prototyping a couple of “critical” routines in MAPLE (namely the Berkowitz algorithm for the computation of the characteristic polynomial of a matrix with polynomial entries and the computation of a Noether position of a given projective variety).

This work was continued by K. Hägele (Universidad de Cantabria) and G. Lecerf (École Normale Supérieure, Paris and École Polytechnique, Palaiseau) and is the subject of a contributed paper at this conference (Hägele & Lecerf (1997)). In this context let me also mention that based on the C++ classlib of the LEDA team in Saarbrücken a prototype for straight–line programs was developed by K. Hägele (Universidad de Cantabria) (1996) and a guide listing the software engineering problems of our project was tackled in (Hägele & Matera (1996)). Although we have only in mind the development of a “presentable” prototype for our algorithms solving elimination problems using the abstract data type DAG, the software engineering problems one has to expect should not be underestimated.

This observation led to the constitution of a team considering the before mentioned programming problems from the point of software engineering. This group works under the direction of R. Wachenchauzer (University of Buenos Aires) and G. Matera (University of Buenos Aires, University of Gral. Sarmiento) with the advice of V. Braberman (University of Buenos Aires) and the collaboration of a group of students coming from the departments of Computer Science and Mathematics of the University of Buenos Aires (S. Cerrutti, S. Cesaratto, T.-J. Fu, P. Fritzsche, L. E. Notarfrancesco, A. Waissbein).

2.3 And now the publicity: the TERA project

All this scattered activity, theoretical advances, development of algorithms, suitable abstract data types and their computer implementation is going on within a loosely organized community firming under the name of the project group TERA (Turbo Evaluation and Rapid Algorithms). This project group is spread over four countries (Argentina, Spain, France, Germany) and includes eight universities and research institutions. More than thirty collaborators make up this group, the resarch and development activities being organized around two main tasks, a theoretical and a practical one.

The practical task consists in the development of a program library which aims to represent a tool for tackling selected parametric polynomial and algebro–differential equation systems occuring in natural science applications and engineering. So there is the claim to produce some useful software at an advanced stage of the TERA project.

The theoretical task however, which can be even misunderstood as counter-productive to any generalistic approach, is the search for a satisfactory definitive proof (i.e. a proof independent of any open conjectures in mathematics or theoretical computer science) of our hypothesis, that only very exceptional, “well suited”, equation systems allow an efficient treatment.

This amounts to giving a rigorous proof of the impossibility to construct a general purpose software solving any generic polynomial or algebro-differential equation system in a reasonable amount of time and memory space.

Let us mention – by the way – that solving any one of these tasks is also subject of an award, the “Jacques Morgenstern Challenge”, set up by the University of Cantabria with the collaboration of a large number of other scientific organizations. For more

information, consult http://matsun1.matesco.unican.es/CAG/

The resolution of this double task requires a well organized interdisciplinary work between so distant (or so close) fields as: algebraic, semialgebraic and diophantine geometry, singularity theory, differential topology, commutative and differential algebra, theory of invariants, diophantine approximation and transcendence theory representing the aspect of pure mathematics, numerical analysis and approximation theory representing the aspect of applied mathematics and complexity theory, computer algebra, seminumerical algorithms, data structures, programming languages and software engineering representing the aspect of theoretical and practical computer science.

These fields, at first glance unrelated, are subject to a unified view through our project oriented approach. Most of them are represented by at least one specialist in the working group. For more detailed information you may want to look at our

World-Wide-Web Homepage at http://hilbert.matesco.unican.es/tera/.

At this moment not too much can be said whether the practical task of the TERA project can be brought to a good end. Experimental evidence says us only that we are touching a sensitive point with our skepticism toward the traditional data structures in symbolic computation.

Nevertheless one may make three serious objections to our generally positive message:

• First objection: it is not clear at all that our notion of “well suited” polynomial equation system corresponds to anything what occurs in “real life”. Solving just one “real task” by our method would be already a major breakthrough (and a candidate to be awarded by the Jacques Morgenstern Challenge).

• Second objection: our coarse theoretical methods may be “blind” (and in fact they are) for crucial algorithmic problems which will probably appear during the implementation of our method. It is unthinkable that our abstract algorithmic model takes into account all aspects which are relevant in practice. Possibly just at the end of all this immense programming work we have to undertake may appear a problem which represents an intrinsic obstruction to the practical efficiency of our algorithms. Whereas these two objections concern the risk of any serious R&D work the following third one represents a concrete thread to our project.

• Third and last objection: the loosely organized voluntary TERA community will possibly not bring together enough profesionalism, discipline and technical means to finish the rather complex programming work implied in the creation of a fully functional prototype of our basic elimination algorithm, even though the development of the theoretical basis would in principle suffice for such a task. In fact the lack of professional management and of modern software engineering knowledge represents a major weakness in our organization. Communication between people programming exists only at a very low level and common programming standards are completely absent.

2.4 Other DAG-based implementation work in Computer Algebra

Based on his own work on gcd computation and factorization of multivariate polinomials given in circuit representation (see e.g. Kaltofen (1988)), E. Kaltofen and his collaborators developped a couple of years ago their own Macsyma LISP library for the manipulation of DAG’s, namely the DAGWOOD library (Freeman et al. (1988)). In a similar, informatically more modest attempt Canny and his collaborators developped a toolkit for real elimination (Canny & Rege (1995)). Both implementations face serious problems with administration of memory space during their execution. This phenomenon is due to the particularity of straight line programs that they never “forget their history”. In order to make efficient a program which manipulates DAG’s it is unavoidable to implement procedures which are able to compress from time to time the DAG’s which appear during the execution of the program. In general this is impossible. However, as shown in Giusti et al. (1996) and (1997a), elimination procedures have the particularity that they allow such compressions. We hope that our implementations can profit from this circumstance. If this is case, we obtain a scientific proof that the bad human qualities on which our algorithms are based, bring – just as in real life – more profit than the honestity of our collegues and competitors. These bad qualities are lazyness and undecisiveness (our algorithms store as far as possible all appearing data in DAG’s which are only evaluated – if ever – in order to be subsequently discarded), our algorithms are greedy and don’t take previsions for the future (no extra space is wasted in view of a possible worst case until it really occurs) and they borrow trying not to pay their debts. In other words, they are a real product of the Third World.

References

[1] A. V. Aho et al, Theory of Computing: goals and directions. Manuscript, 1996.

[2] M. Aldaz, Implementación de números racionales mediante la estructura de datos straight–line program, TERA’96, Santander, Spain 1996.

[3] M. Aldaz, J. Heintz, G. Matera, J. L. Montaña & L.M. Pardo, Time– space tradeoffs in polynomial evaluation procedures. preprint, University of Cantabria, Spain, 1996.

[4] M. Aldaz, J. Heintz, G. Matera, J. L. Montaña & L.M. Pardo, Time–space tradeoffs in polynomial evaluation procedures. WAIT’97, Buenos Aires, Argentina, 1997.

[5] B. Bank, M. Giusti, J. Heintz & G. Mbakop, Polar Varieties, Real Equation Solving and Data-Structures : The Hypersurface Case. To appear in J. of Complexity, 1996.

[6] D. Bayer, M. Stillmann , On the complexity of computing syzygies. J. Symbol.Comput. 6, 1988,135–147,

[7] S.J. Berkowitz, On computing the determinant in small parallel time using a small number of processors. Inf. Proc. Letters 18, 1984, 147–150.

[8] L. Blum, F. Cucker, M. Shub, & S. Smale, Algebraic settings for the Problem ”P≠NP. To appear in Lectures In Applied Mathematics, 1996.

[9] A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6, 1977, 733–744.

[10] L. Caniglia, A. Galligo and J. Heintz, Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque. C.R. Acad. Sci. Paris, Série I, Math. 307, 1988, 255–258.

[11] B. Castaño, J. Heintz, J. Llovet, R. Martínez, On the data structure straight– line program and its implementation in symbolic computation, Manuscript, 1997

[12] M. Camdessus, L’Argentine: croupion d’état ou état des croupions? IMF Press, New York, 1996.

[13] L. Caniglia, A. Galligo and J. Heintz, Some new effectivity bounds in computational geometry. In Proc. AAECC–6, ed. T. Mora, Lecture Notes in Computer Science 357, Springer Verlag, 1989, 131–152.

[14] J. Canny, Some algebraic and geometric computations in PSPACE. In Proc. 20th Ann. ACM STOC’88, 1988, 46–467.

[15] J. Canny & I. Z. Emiris, Efficient algorithms for the sparse resultant and the mixed volume, Preprint (1993).

[16] J. Canny & A. Rege, A Toolkit for Algebra and Geometry. Preprint, 1995.

[17] A.L. Chistov & D. Yu. Grigor’ev, Subexponential–time solving systems of algebraic equations, LOMI Preprints E-g-83, E-10-83, Leningrad (1983).

[18] J.H. Davenport & J. Heintz, Real quantifier elimination is doubly exponential. J. Symbolic Computation 5, 1988, 29 – 35.

[19] M. Demazure, Le Theoreme de Complexite de Mayr-Meyer, Notes Informelles de Calcul Formel IV, Ecole Polytechnique (1985).

[20] A. Dickenstein, N. Fitchas, M. Giusti, C. Sessa, The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Appl. Math. 33, 1991, 73–94, Special issue 7th Intern. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC–7, Toulouse 1989.

[21] I. Z. Emiris, On the complexity of sparse elimination. To appear in J. of Complexity (1996).

[22] N. Fitchas and A. Galligo, Nullstellensatz effective et conjecture de Serre (théorème de Quillen–Suslin) pour le calcul Formal. Math. Nachrichten 149, 1990, 231–253.

[23] N. Fitchas, M. Giusti and G. Smietanski, Sur la complexité du théoreme des zéros. In Approximation and Optimization 8, ed. J. Guddat et al., Peter Lange Verlag, Frankfurt am Main, 1995, 274–329.

[24] T. S. Freeman, G. M. Imirzian, E. Kaltofen & L. Yagati, DAGWOOD - A System for Manipulating Polynomials Given by Straight–Line Programs. ACM Transactions on Mathematical Software 3, 1988, 218–240.

[25] M. Giusti & J. Heintz, Un algorithme — disons “rapide” — pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles. In Proc. MEGA’90, ed. T. Mora and Carlo Traverso, Birkhäuser Progress in Mathematics vol. 94, 1991, 169 – 194.

[26] M. Giusti & J. Heintz, La détermination de la dimension et des points isolés d’une variété algébrique peut se faire en temps polynomial. In Computational Algebraic Geomtry and Commutative Algebra Symposia Mathematica, vol. 34, Istituto de Alta Matematica Francesco Severi and Cambridge University Press, Cambridge , 1993, 216–256.

[27] M. Giusti, J. Heintz & J. Sabia, On the efficiency of effective Nullstellensätze. Computational Complexity 3, 1993, 56–95.

[28] M. Giusti, J. Heintz, J. E. Morais and L. M. Pardo, When polynomial equation systems can be ’solved’ fast?. In Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, Proc. AAECC–11, eds. G. Cohen, M. Giusti and T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 205–231.

[29] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern and L. M. Pardo, Straight– line programs in geometric elimination theory. To appear in J. of Pure and Appl. Algebra, 1996.

[30] M. Giusti, K. Hägele, J. Heintz, J. L. Montaña, J. E. Morais and L. M. Pardo, Lower Bounds for Diophantine Approximation. To appear in J. of Pure and Appl. Algebra, 1997a.

[31] M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, Le rôle des estructures de données en Théorie de l’Elimination. Preprint, 1997b.

[32] D. Yu. Grigor’ev & N. Vorobjov, Solving Systems of Polynomial Inequalities in Subexponential Time. J. of Symb. Comp. 5, 1988, 37–64.

[33] A. Grosso, N. Herrera, G. Matera, M.E. Stefanoni & J.M. Turull Torres, A PSPACE implementation of the effective Nullstellensatz. In Proc. JAIIO, Buenos Aires, 1996.

[34] K. Hägele, A prototype for straight–line programs, (slp– a C++ classlib) . Preprint, 1996.

[35] K. Hägele & G. Lecerf, Computing the dimension of a projective variety. WAIT’97, Buenos Aires, 1997.

[36] K. Hägele & G. Matera, Preparatory Note for the Draft for Design and Implementation. Manuscript, 1996.

[37] K. Hägele & J.L. Montaña, Polynomial random test for the equivalence problem of integers given by straight–line programs. Preprint University of Cantabria, 1996.

[38] J. Heintz, G. Matera, L. M. Pardo, R. Wachenchauzer, About the intrinsic complexity of elimination, WAIT’97, Buenos Aires, 1997.

[39] J. Heintz, Fast quantifier elimination over algebraically closed fields. Theoret. Comput. Sci. 24, 1983, 239–277.

[40] J. Heintz, On the computational complexity of polynomials and bilinear mappings. In Proc. AAECC–5, eds. L. Huguet and A. Poli. Lecture Notes in Computer Science 356, Springer Verlag, 1989, 269–300.

[41] J. Heintz, Deformation techniques for efficient polynomial equation solving. Manuscript, Universidad de Cantabria, Spain, 1997.

[42] J. Heintz and J. Morgenstern, On the intrinsic complexity of elimination theory. J. of Complexity 9, 1993, 471–498.

[43] J. Heintz, M. F. Roy and P. Solernó, On the complexity of semialgebraic sets. Proc. Information Processing (IFIP’89), San Francisco, G. X. Ritter ed., North Holland, Amsterdam (1989) 293–298.

[44] J. Heintz, M. F. Roy and P. Solernó, Sur la Complexité du Principe de Tarski– Seidenberg. Bull. Soc. math. France 118, 1990, 101–126.

[45] J. Heintz, M. F. Roy and P. Solernó, Description of the connected components of a semialgebraic set in simply exponential time.Discrete and Computational Geometry 11, 1994, 121–140.

[46] J. Heintz & C.P. Schnorr, Testing Polynomials wich are easy to compute. In Logic and Algorithmic (an International Symposium in honour of Ernst Specker), Monographie n. 30 de l’Enseignement Mathématique, 1982, 237– 254.

[47] O.H. Ibarra & S. Moran, Equivalence of Straight–Line Programs. J. of the ACM 30, 1983, 217–228.

[48] P. Jacovkis, Personal communication, 1997.

[49] E. Kaltofen, Greatest common divisor of polynomials given by straight–line programs. J. A. C. M 35 (1) (1988) 234–264.

[50] P. Koiran, The Hilbert Nullstellensatz is in the Polynomial Hierarchy. Preprint, 1996.

[51] Kraft, Talk given at MEGA’96, Eindhoven, Netherlands. 1996.

[52] T. Krick and L. M. Pardo, Une approche informatique pour l’approximation diophantienne. C. R. Acad. Sci. Paris 318, Série I, no. 5, 1994, 407–412.

[53] T. Krick and L. M. Pardo, A Computational Method for Diophantine Approximation. In Algorithms in Algebraic Geometry and Applications, Proc. MEGA’94, eds. L. Gonzalez–Vega and T. Recio. Progress in Mathematics 143, Birkhäuser Verlag, 1996, 193–254.

[54] G. Matera. Sobre la complejidad en espacio y tiempo de la eliminación geométrica, Univ. of Buenos Aires, 1997.

[55] G. Matera & J.M. Turull Torres, The space complexity of elimination theory. Proc. Foundations of Computational Mathematics FOCM’97, F. Cucker, M. Smale, eds. Springer Verlag (1997) 267-276

[56] E. Mayr and A. Meyer, The complexity of the word problem for commutative semigroups. Advances in Math. 46, 1982, 305–329.

[57] J. L. Montaña and L. M. Pardo, Lower bounds for Arithmetic Networks. Appl. Alg. Eng. Comm. Comp. 4, No. 1, 1993, 1–24.

[58] B. Mourrain, V. Pan, Solving special polynomial systems by using structural matrices and algebraic residues. Proc. Foundations of Computational Mathematics FOCM’97, F. Cucker, M. Smale, eds. Springer Verlag (1997) 287-304.

[59] A. Odlyzko, Computer Algebra and its applications: where are we going? Manuscript, 1995.

[60] L. M. Pardo, How Lower and Upper Complexity Bounds meet in Elimination Theory. In Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, Proc. AAECC–11, eds. G. Cohen, M.Giusti & T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 33–69.

[61] S. Puddu & J. Sabia, An effective algorithm for quantifier elimination over algebraicay closed fields using straight -line programs. To appear in J. of Pure and Appl. Algebra, 1997.

[62] J. Renegar, On the computational Complexity and Geometry of the First– order Theory of the reals. (Part I: Introduction. Preliminaires. The Geometry of Semi–algebraic sets. The Decision Problem for the Existencial Theory of the Reals.) J. of Symb. Computation 13, 1992, 255–301. (also Part II and Part III in the same issue).

[63] J.T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. of the ACM 27, 1980, 701–717.

[64] A. Schönhage, On the Power of Random Acces Machines. In Proceedings of ICALP 6, Lect. Notes Comp. Sci. 71, Springer, 1979.

[65] M. Shub, S. Smale, Complexity of Bezout’s theorem V: Polynomial time, Theoretical Comp. Sci. 133 (1994)

[66] M. Sombra, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nulstellensatz. To appear in J. Pure Appl. Algebra, 1997.

[67] A. Waissbein, Master’s Thesis, University of Buenos Aires, Argentina. In preparation 1997.

[68] V. Weispfennig,The complexity of linear problems in fields. J. of Symb. Comp. 5, 1988, 3–27.

[69] C.K. Yap, A New Lower Bound Construction for Commutative Thue Systems with Applications. J. of Symb. Comp. 12, 1991, 1–27.

[70] R. Zippel, Interpolating Polynomials from their Values. J. Symbol. Comput., 9, 1990, 375–403