Existing commercial software
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&Dwork 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 professionalism, 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 every low level and common programming standards are completely absent. However we count since the beginning of this year with the advise of two specialists in software engineering and functional programming (R. Wachenchauzer and V. Braberman, Departamento de Computación, Universidad de Buenos Aires) and own efforts too already produced some results in this direction.
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.
Based on his own work on gcd computation and factorization of multivariate polynomials 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 colleagues 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 and mentioning Oblomov is really too euphemistic in this context.....
Existing commercial software
The Project TERA
References