Structures of precision losses in computing approximate Groebner bases

摘要

In computing approximate Grobner bases, it is not easy to trace precision losses of floating-point coefficients of intermediate approximate polynomials. The measured precision losses are usually much larger than their genuine values. One reason causing this phenomenon is that most existing methods for tracing precision losses do not consider the dependence of such precision losses in any polynomial (as an equation). In this paper, we define an algebraic structure called PL-space (precision loss space) for a polynomial (as an equation) and set up a theory for it. We prove that any PL-space has a finite weak basis and a strong basis and show how they effect on tracing precision losses by an example. Based on the study of minimal strong bases, we propose the concept of dependence number which reveals the complexity of the dependence of precision losses in a polynomial.