## ffmodstd

swMATH ID: | 27228 |

Software Authors: | D.K. Boku; W. Decker; C. Fieker |

Description: | SINGULAR Library ffmodstd.lib: Groebner bases of ideals in polynomial rings over rational function fields. 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] and univariate rational interpolation [2,7]. The procedure is repeated for many rational points b until their number is sufficiently large to recover the correct coeffcients 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. |

Homepage: | https://www.singular.uni-kl.de/Manual/latest/sing_2374.htm#SEC2450 |

Dependencies: | SINGULAR |

Related Software: | FOXBOX; Dagwood; modstd.lib; modwalk; Macaulay2; CoCoA |

Referenced in: | 5 Publications |

all
top 5

### Referenced by 7 Authors

3 | Lee, Wen-shin |

2 | Kaltofen, Erich L. |

1 | Arnold, Elizabeth A. |

1 | Cuyt, Annie A. M. |

1 | Khodadad, Sara |

1 | Lobo, Austin A. |

1 | Monagan, Michael B. |

### Referenced in 2 Serials

2 | Journal of Symbolic Computation |

1 | Theoretical Computer Science |

### Referenced in 5 Fields

4 | Computer science (68-XX) |

2 | Commutative algebra (13-XX) |

1 | Number theory (11-XX) |

1 | Approximations and expansions (41-XX) |

1 | Numerical analysis (65-XX) |