### 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.4.1, 2025, generated by texi2html.