Hans J. Stetter

Technical University Vienna

email: `stetter@uranus.tuwien.ac.at`

The concepts and algorithms of classical polynomial algebra assume exact data and exact computation; this restricts their computer implementation to coefficients from finite fields or the rationals (with finite extensions) and the operations to integer or rational arithmetic. On the other hand, many desirable results (like zeros of polynomial systems) are not rational for rational data so that they can only be computed approximately in any case; furthermore, in tasks modelling real-life problems, some data are usually known only with a limited (often low) accuracy. The tutorial will show how these facts can be accomodated in computer algebra.

To deal properly with approximate data and approximate computation, we introduce a rudimentary topology derived from that of the complex number field to which we will restrict our considerations. This will require a reconsideration of some classical concepts of computer algebra which depend discontinuously on their data (e.g. Gröbner bases). Furthermore, we will pay attention to the stability of our algorithms w.r.t. small intermediate perturbations. A stable algorithm for the approximate computation of results which are meaningful for data with limited accuracy can directly be executed in floating-point arithmetic without harm.

We will explicitly develop this principal approach (which parallels the well-known successful approach of numerical linear algebra) in connection with the task of computing the zeros of multivariate systems of polynomial equations with complex coefficients. Attendants of the tutorial should have some basic knowledge in computer algebra and in (numerical) linear algebra.