×

zbMATH — the first resource for mathematics

Ideals modulo a prime. (English) Zbl 1472.13043
The present paper deals with the problem of reducing an ideal modulo \(p\), i.e. relating an ideal \(I\) in the polynomial ring \(\mathbb{Q}[x_1,\dots,x_n]\) to a corresponding ideal in \(\mathbb{F}_p[x_1,\dots,x_n]\) where \(p\) is a prime number.
The authors define a notion of \(\sigma\)-good prime, where \(\sigma\) is a term ordering and relate it to other similar notions in the literature. Furthermore, the paper introduces a new invariant called universal denominator, which is independent of the term ordering and allows to show that all but finitely many primes are good for \(I\) (see Definiton 2.4).
The methods in the paper make it easy to detect bad primes, a key feature in modular methods (Theorem 4.1 and Corollary 4.2).
The paper includes practical applications to modular computations of Gröbner bases and also includes examples of computations using the computer algebra systems CoCoA and SINGULAR.
MSC:
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
13-04 Software, source code, etc. for problems pertaining to commutative algebra
14Q10 Computational aspects of algebraic surfaces
68W30 Symbolic computation and algebraic computation
Software:
CoCoALib; gmp; CoCoA; SINGULAR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, J., Fault-tolerant modular reconstruction of rational numbers, J. Symbolic Comput.80 (2017) 707-718. · Zbl 1403.11083
[2] J. Abbott and A. M. Bigatti, CoCoALib: A \(\text{C}++\) library for doing computations in commutative algebra (2019), http://cocoa.dima.unige.it/cocoalib.
[3] Abbott, J., Bigatti, A. M., Palezzato, E. and Robbiano, L., Computing and using minimal polynomials, J. Symbolic Comput. (2019), https://doi.org/10.1016/j.jsc.2019.07.022. · Zbl 1468.13063
[4] Abbott, J., Bigatti, A. M. and Robbiano, L., Implicitization of hypersurfaces, J. Symbolic Comput.81 (2017) 20-40. · Zbl 1390.13080
[5] J. Abbott, A. M. Bigatti and L. Robbiano, CoCoA: A system for doing computations in commutative algebra (2019), http://cocoa.dima.unige.it.
[6] Adams, W. W. and Loustaunau, P., An Introduction to Gröbner Bases (American Mathematical Society, 1994). · Zbl 0803.13015
[7] Aoyama, T. and Noro, M., Modular algorithms for computing minimal associated primes and radicals of polynomial ideals, in Proc. Int. Symp. Symbolic and Algebraic Computation (New York, USA, 2018), pp. 31-38. · Zbl 1467.13041
[8] Arnold, E. A., Modular algorithms for computing Gröbner bases, J. Symbolic Comput.35 (2003) 403-419. · Zbl 1046.13018
[9] J. Böhm, W. Decker, C. Fieker, S. Laplagne and G. Pfister, Bad primes in computational algebraic geometry, preprint (2017), arXiv:1702.06920v1. · Zbl 1437.14059
[10] W. Decker, G.-M. Greuel, G. Pfister and H. Schönemann, Singular, A computer algebra system for polynomial computations (2019), http://www.singular.uni-kl.de/. · Zbl 1344.13002
[11] T. Granlund and the GMP development team, GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.2 edn. (2016), http://gmplib.org/.
[12] Idrees, N., Pfister, G. and Steidel, S., Parallelization of modular algorithms, J. Symbolic Comput.46 (2011) 672-684. · Zbl 1229.13002
[13] Kreuzer, M. and Robbiano, L., Computational Commutative Algebra \(1\) (Springer, Heidelberg, 2000), 2nd edn. 2008. · Zbl 0956.13008
[14] Kreuzer, M. and Robbiano, L., Computational Commutative Algebra \(2\) (Springer, Heidelberg, 2005). · Zbl 1090.13021
[15] Kreuzer, M. and Robbiano, L., Computational Linear and Commutative Algebra (Springer, Heidelberg, 2016). · Zbl 1360.13001
[16] Monagan, M., Maximal quotient rational reconstruction: An almost optimal algorithm for rational reconstruction, in Proc. Int. Symp. Symbolic and Algebraic Computation, ACM, 2004, pp. 243-249. · Zbl 1134.68602
[17] Mora, T. and Robbiano, L., The Gröbner fan of an ideal, J. Symbolic Comput.15 (1993) 199-209. · Zbl 0668.13017
[18] Noro, M., An efficient modular algorithm for computing the global \(b\)-function, in Proc. First Cong. Mathematical Software, eds. Cohen, A. M., Gao, X. S. and Takayama, N. (Beijing, China, 2002), pp. 147-157. · Zbl 1057.68149
[19] Noro, M. and Yokoyama, K., A modular method to compute the rational univariate representation of zero-dimensional ideals, J. Symbolic Comput.28 (1999) 243-263. · Zbl 0945.13010
[20] Noro, M. and Yokoyama, K., Implementation of prime decomposition of polynomial ideals over small finite fields, J. Symbolic Comput.38 (2004) 1227-1246. · Zbl 1137.13318
[21] Noro, M. and Yokoyama, K., Usage of modular techniques for efficient computation of ideal operations, Math. Comput. Sci.12 (2018) 1-32. · Zbl 1402.13026
[22] Pauer, F., Gröbner bases with coefficients in rings, J. Symbolic Comput.42 (2007) 1003-1011. · Zbl 1127.13024
[23] Winkler, F., A \(p\)-adic approach to the computation of Gröbner bases, J. Symbolic Comput.6 (1988) 287-304. · Zbl 0669.13009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.