Selecting lengths of floats for the computation of approximate Gröbner bases (Q1946964): Difference between revisions

The difficulty in computing a Gröbner basis for a system of non-linear polynomials with real coefficients is in determining when a coefficient in a derived polynomial is, in fact, zero. While this determination is essential to the computation, different methods of determination may yield wildly different Gröbner bases. The question is: what precision is necessary to yield a meaningful result. In this paper, the author assumes one will need to compute Gröbner bases for a family of non-overdetermined polynomial systems, all sharing the same support, and thus that one can spend some energy on determining the proper precision. Further, the author assumes one desires an actual Gröbner basis, as opposed to, say, the approximate roots of the system. The author gives a method for determining the required arithmetic accuracy \(l\) in terms of the supports of the various input polynomials, and the desired probability that the computation will not result in the erroneous declaration that the coefficient of a leading term is zero. The method proceeds by Monte Carlo, generating uniformly random polynomial systems with the same support as the family and converting these to integral systems with maximum coefficient size ``large enough'' (in practice, the author says integers with 10 decimal digits is generally large enough). These systems are solved using an exact algorithm, keeping track of the number of leading coefficients that are of a certain size (in terms of the size of the largest coefficient in that polynomial). A parameter \(\mu\) is chosen so that the number of ``small'' leading coefficients is as infrequent as desired, and from this the necessary length of the floating-point numbers for the entire family of systems is quickly determined. As the number of samples required to get an accurate length can be quite large, the author gives a way to asymptotically estimate the result, thus making the algorithm more practical. The author concludes with multiple experiments on benchmarks and dense polynomial systems, demonstrating that the method produces reliable and reasonably large lengths of floats for most of the tested benchmarks.