Stable Numerical Computation of Groebner Bases for Multivariate Polynomial Systems

Polynomials in several variables play an important role in many application areas (e.g. computer-aided design, robotics, chemical engineering, etc.). Groebner bases are the central tool for solving algorithmic problems related to systems of multivariate polynomials, in particular for the computation of the zeros of such a system. Current computer algebra systems contain codes for the computation of Groebner bases for specified systems; however, these codes must be run in rational arithmetic because they are potentially numerically unstable, which makes the computation considerably slower than necessary. This instability is due to intrinsic discontinuities in standard Groebner bases, which prohibits their use for systems with data of limited accuracy which are standard in application problems. The applicant has recently generalized the concept of Groebner bases slightly to make the local removal of these discontinuities possible. This has opened the way for the design of numerically stable algorithms for the computation of extended Groebner bases which can be used just like standard Groebner bases, e.g. for the computation of zeros. It is the aim of the proposed project to generate the complete design and an implementation of an algorithm for the following task: Given n polynomials in s variables, with coefficients which may have a (specified) limited accuracy, compute an approximation for the extended Groebner basis of these polynomials, for a given term order. The algorithm must permit execution in floating-point arithmetic without danger of instability. The accuracy of the computed approximation must relate to the accuracy ot the input data. The design of the algorithm will be based on the observation that the potential discon-tinuities of Groebner bases stem from the enforcing of a unique relation between polynomial ideals and normal sets. If a wider choice of normal sets is considered, it is possible to keep the normal set invariant in a full neighborhood of the specified system of polynomials. This leads to an extended Groebner basis which is continuous in this neighborhood. Computationally, the presence of a discontinuity is revealed by the occurrence of leading terms with very small coefficients in intermediate polynomials. In this case, a stabilized algorithm must deviate from the standard algorithmic path in certain ways. The details of this new algorithmic design and proofs for its feasibility will constitute the central task of the reaserch project.

An algorithm has been developed and implemented which permits the numerical computation of the extended Groebner Basis of a regular system of polynomial equations in floating-point arithmetic. Polynomials in several variables are important models in many application areas (e.g. computer aided design, computer vision, robotics, chemical engineering etc.). Groebner Bases are the central tool for the computational simulation of many related problems, in particular for the computation of zeros. Current codes for the computation of Groebner Bases use slow rational arithmetic and generate results which may be unsuitable for further processing. The algorithm deeloped in the project avoids near-degenerate situations in as far as possible; it can therefore be executed in fast floating-point arithmetic. Furthermore, it generates meaningful results also when the problem data are of limited accuracy. Thus it can be employed for the computational analysis of a great variety of nonlinear models in realistic technical-scientific tasks.