The use of bad primes in rational reconstruction. (English) Zbl 1326.13018

Böhm, Janko; Decker, Wolfram; Fieker, Claus; Pfister, Gerhard

Math. Comput. 84, No. 296, 3013-3027 (2015).

In computational algebraic geometry, when one would like to compute over the rationals, one is often forced to compute over the the integers modulo a prime for performance reasons. When doing so, not all primes are equal. The bad primes are those where the reduction yields wrong results. This phenomenon appears in various different flavors, for example the modular reduction could yield divisions by zero, or more subtle changes in the result. The paper offers a classification into five types. Fortunately, in many situations there are only finitely many bad primes, so that repeated computation with many different primes eventually yields the correct result, provably, or at least with high probability.
In the present paper, the authors discuss algorithms for the reconstruction of a Gröbner basis of an a priori unknown ideal or module. The main challenge here is to develop algorithms that can deal with bad primes, not knowing that they are bad primes while the algorithm runs. The main idea is a majority voting scheme on intermediate results which builds on the assumption that bad primes are rare. The methods are illustrated with nice examples.

Reviewer: Thomas Kahle (Magdeburg)

MSC:

13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30	Symbolic computation and algebraic computation
52C05	Lattices and convex bodies in \(2\) dimensions (aspects of discrete geometry)
68W10	Parallel algorithms in computer science

Keywords:

rational reconstruction; Farey map; Gröbner bases; modular arithmetic

References:

[1]	Adams, William W.; Loustaunau, Philippe, An Introduction to Gr\"obner Bases, Graduate Studies in Mathematics 3, xiv+289 pp. (1994), American Mathematical Society, Providence, RI · Zbl 0803.13015
[2]	Arnold, Elizabeth A., Modular algorithms for computing Gr\"obner bases, J. Symbolic Comput., 35, 4, 403-419 (2003) · Zbl 1046.13018
[3]	B{\'”o}hm, Janko; Decker, Wolfram; Laplagne, Santiago; Pfister, Gerhard; Steenpa{\ss }, Andreas; Steidel, Stefan, Parallel algorithms for normalization, J. Symbolic Comput., 51, 99-114 (2013) · Zbl 1408.13072
[4]	[BDLSadj] J. B\"ohm, W. Decker, S. Laplagne, and G. Pfister, Local to global algorithms for the Gorenstein adjoint ideal of a curve. In preparation. · Zbl 1402.14076
[5]	Collins, George E.; Encarnaci{\'o}n, Mark J., Efficient rational number reconstruction, J. Symbolic Comput., 20, 3, 287-297 (1995) · Zbl 0851.68037
[6]	Encarnaci{\'o}n, Mark J., Computing GCDs of polynomials over algebraic number fields, J. Symbolic Comput., 20, 3, 299-313 (1995) · Zbl 0855.68046
[7]	Greuel, Gert-Martin; Laplagne, Santiago; Seelisch, Frank, Normalization of rings, J. Symbolic Comput., 45, 9, 887-901 (2010) · Zbl 1200.13015
[8]	Idrees, Nazeran; Pfister, Gerhard; Steidel, Stefan, Parallelization of modular algorithms, J. Symbolic Comput., 46, 6, 672-684 (2011) · Zbl 1229.13002
[9]	Nguyen, Phong Q.; Stehl{\'e}, Damien, Low-dimensional lattice basis reduction revisited, ACM Trans. Algorithms, 5, 4, Art. 46, 48 pp. (2009) · Zbl 1300.11133
[10]	Kornerup, Peter; Gregory, R. T., Mapping integers and Hensel codes onto Farey fractions, BIT, 23, 1, 9-20 (1983) · Zbl 0521.10007
[11]	[W81] P. S. Wang, A p-adic algorithm for univariate partial fractions. Proceedings SYMSAC ’81, 212-217 (1981).
[12]	[WGD] P. S. Wang, M. J. T. Guy, and J. H. Davenport, P-adic reconstruction of rational numbers. SIGSAM Bull, 2-3 (1982). · Zbl 0489.68032