Approximate Gr？bner Bases, Overdetermined Polynomial Systems, and Approximate GCDs

We discuss computation of Gr？bner bases using approximate arithmetic for coefficients. We show how certain considerations of tolerance, corresponding roughly to absolute and relative error from numeric computation, allow us to obtain good approximate solutions to problems that are overdetermined. We provide examples of solving overdetermined systems of polynomial equations. As a secondary feature we show handling of approximate polynomial GCD computations, using benchmarks from the literature. 1. Introduction Gr？bner bases provide a means for solving a myriad of problems in computational algebra. In its original form, the whole arithmetic was carried through exactly, on rational numbers. This was necessary in order to know when combinations of polynomial coefficients cancel. In 1993 Shirayanagi [1] indicated a means to use approximate arithmetic and still handle this “zero recognition” problem. Since that time several approaches have appeared that use approximate arithmetic [2–10]. The advantages of approximate arithmetic are several. First is that it avoids intermediate coefficient swell one often observes in exact Gr？bner basis computations. A second reason is that, in many problems, one works with approximate data and does not have access to exact values. Moreover, approximation by rationals might lead to intermediate swell and still not improve on a solution based on the original approximate input values. Work on numeric Gr？bner bases begins with [1, 8]. The method therein for controlling error is a bit similar to what we will describe in Section 2. It uses bookkeeping to measure loss of precision from arithmetic operations (similar ideas are discussed in [5]). The handling of coefficients can thus be viewed as an extension of floating point arithmetic. Traverso and Zanoni [11] describe use of both a modular image and a numeric approximation for coefficients. Only when both forms give zero (approximate, in the latter case) do we regard an apparent cancellation as truly zero. A drawback is that this requires either exact input or else an approximate system that is not overdetermined. Other approaches include extending the notion of Gr？bner bases to allow head terms with small coefficients to become nonhead terms [9, 12–14]. Of these, [12] is notable for allowing the use of an almost unaltered Gr？bner basis algorithm, with low rank variables added as needed during the course of the computation. This family of methods attempts to stabilize the set of head terms locally, that is, in a neighborhood of a set of coefficient values that give a “nongeneric”