Floating-Point Groebner Basis Computation with Ill-conditionedness Estimation

摘要

Computation of Grobner bases of polynomial systems with coefficients of floating-point numbers has been a serious problem in computer algebra for many years; the computation often becomes very unstable and people did not know how to remove the instability. Recently, the present authors clarified the origin of instability and presented a method to remove the instability. Unfortunately, the method is very time-consuming and not practical. In this paper, we first investigate the instability much more deeply than in the previous paper, then we give a theoretical analysis of the term cancellation which causes loss of accuracy in various cases. On the basis of this analysis, we propose a practical method for computing Grobner bases with coefficients of floating-point numbers. The method utilizes multiple precision floating-point numbers, and it removes the drawbacks of the previous method almost completely. Furthermore, we present a practical method of estimating the ill-conditionedness of the input system.