Algorithmic Refinement of an Approximate Basis of a Zero-dimensional Polynomial Ideal

Approximate (floating-point) basis computation for the ideal generated by a multivariate polynomial system Q, where Q is a complete intersection, suffers from the following drawback: For s variables where s>1, ideal bases (e.g. Groebner bases) generally have more than s elements; a generic perturbation of the coefficients as in an approximate computation makes the basis inconsistent. While this does not critically affect some tasks (e.g. computation of approximate zeros), it is a principal obstacle in others.

We explain a floating-point algorithm which refines the coefficients of an inconsistent approximate border basis with an associated normal set (e.g. a Groebner basis) into the exact border basis of , except for linearization and round-off effects. (If necessary, these can be made arbitrarily small by iteration and sufficient precision resp.) This algorithm opens the way for a more wide-spread use of approximate computation in polynomial algebra.

A crucial ingredient of the algorithm which is intesting and important on its own, is the determination of a minimal basis for the syzygies of a border basis.