### D.4.9 ffmodstd_lib

Library:
ffmodstd.lib
Purpose:
Groebner bases of ideals in polynomial rings over rational function fields
Authors:
D.K. Boku boku@mathematik.uni-kl.de
W. Decker decker@mathematik.uni-kl.dei
C. Fieker fieker@mathematik.uni-kl.de
A. Steenpass steenpass@mathematik.uni-kl.de

Overview:
A library for computing a Groebner basis of an ideal in a polynomial ring over an algebraic function field Q(T):=Q(t_1,...,t_m) using modular methods and sparse multivariate rational interpolation, where the t_i are transcendental over Q. The idea is as follows: Given an ideal I in Q(T)[X], we map I to J via the map sending T to Tz:=(t_1z+s_1,..., t_mz+s_m) for a suitable point s in Q^m\{(0,...,0)} and for some extra variable z so that J is an ideal in Q(Tz)[X]. For a suitable point b in Z^m\{(0,...,0)}, we map J to K via the map sending (T,z) to (b,z), where b:=(b_1,...,b_m) (usually the b_i's are distinct primes), so that K is an ideal in Q(z)[X]. For such a rational point b, we compute a Groebner basis G_b of K using modular algorithms [1], where prime numbers are replaced by maximal ideals of the form <z-z_i>, and univariate rational interpolation [2,7]. Note that since Q[z]/<z-z_i> = Q we also use (if required) modular algorithms [1] over Q. The procedure is repeated for many rational points b until their number is sufficiently large to recover the correct coefficients in Q(T). Once we have these points, we obtain a set of polynomials G by applying the sparse multivariate rational interpolation algorithm from [4] coefficient- wise to the list of Groebner bases G_b in Q(z)[X], where this algorithm makes use of the following algorithms: univariate polynomial interpolation [2], univariate rational function reconstruction [7], and multivariate polynomial interpolation [3]. The last algorithm uses the well-known Berlekamp/Massey algorithm [5] and its early termination version [6]. The set G is then a Groebner basis of I with high probability.

References:
[1] E. A. Arnold: Modular algorithms for computing Groebner bases. J. Symb. Comput. 35, 403-419 (2003).
[2] R. L. Burden and J. D. Faires: Numerical analysis. 9th ed. (1993). [3] M. Ben-Or and P. Tiwari: A deterministic algorithm for sparse multivariate polynomial interpolation. Proc. of the 20th Annual ACM Symposium on Theory of Computing, 301-309 (1988).
[4] A. Cuyt and W.-s. Lee: Sparse interpolation of multivariate rational functions. Theor. Comput. Sci. 412, 1445-1456 (2011).
[5] E. Kaltofen and W.-s. Lee: Early termination in sparse interpolation algorithms. J. Symb. Comput. 36, 365-400 (2003).
[6] E. Kaltofen, W.-s. Lee and A. A. Lobo: Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. Proc. ISSAC (ISSAC '00), 192-201 (2000).
[7] K. Sara and M. Monagan: Fast Rational Function Reconstruction. Proc. ISSAC (ISSAC '06), 184-190 (2006).

Procedures:

 D.4.9.1 fareypoly univariate rational function reconstruction D.4.9.2 polyInterpolation univariate polynomial interpolation D.4.9.3 modrationalInterpolation modular univariate rational interpolation D.4.9.4 BerlekampMassey Berlekamp/Massey algorithm D.4.9.5 modberlekampMassey modular Berlekamp/Massey algorithm D.4.9.6 sparseInterpolation sparse multivariate polynomial interpolation D.4.9.7 ffmodStd Groebner bases over algebraic function fields using modular methods and sparse multivariate rational interpolation

User manual for Singular version 4.3.1, 2022, generated by texi2html.