×
Noro, Masayuki; Yokoyama, Kazuhiro

Implementation of prime decomposition of polynomial ideals over small finite fields. (English) Zbl 1137.13318

J. Symb. Comput. 38, No. 4, 1227-1246 (2004).
Summary: An algorithm for the prime decomposition of polynomial ideals over small finite fields is proposed and implemented on the basis of previous work of the second author. To achieve better performance, several improvements are added to the existing algorithm, with strategies for computational flow proposed, based on experimental results. The practicality of the algorithm is examined by testing the implementation experimentally, which also reveals information about the quality of the implementation.

Cited in 5 Documents

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13F20 Polynomial rings and ideals; rings of integer-valued polynomials

Software:

OpenXM
PDF BibTeX XML Cite
\textit{M. Noro} and \textit{K. Yokoyama}, J. Symb. Comput. 38, No. 4, 1227--1246 (2005; Zbl 1137.13318)
Full Text: DOI

References:

[1] Adams, W. W.; Loustaunau, P., An Introduction to Gröbner Bases, Graduate Studies in Mathematics, vol. 3 (1994), American Mathematical Society · Zbl 0811.13020
[2] Anai, H.; Noro, M.; Yokoyama, K., Computation of the splitting fields and the Galois groups of polynomials, (Algorithms in Algebraic Geometry and Applications (1996), Birkhäuser: Birkhäuser Basel), 29-50 · Zbl 0867.12006
[3] Becker, T.; Weispfenning, V., Gröbner Bases (1993), Springer-Verlag: Springer-Verlag New York
[4] Bernardin, L.; Monagan, M. B., Efficient multivariate factorization over finite fields, (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-12). Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-12), Lecture Notes in Computer Science, vol. 1255 (1997)), 15-28 · Zbl 1039.68934
[5] Caboara, M.; Conti, P.; Traverso, C., Yet another ideal decomposition algorithm, (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-12). Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-12), Lecture Notes in Computer Science, vol. 1255 (1997)), 39-54 · Zbl 1042.13500
[6] Decker, D.; Greuel, G.-M.; Pfister, P., Primary decomposition: algorithms and comparisons, (Algorithmic Algebra and Number Theory (1999), Springer), 187-220 · Zbl 0932.13019
[7] de Jong, T., An algorithm for computing the integral closure, J. Symbolic Comput., 26, 273-277 (1998) · Zbl 0932.13021
[8] Eisenbud, D.; Huneke, C.; Vasconcelos, W. V., Direct methods for primary decomposition, Invent. Math., 110, 207-235 (1992) · Zbl 0770.13018
[9] Faugère, J.-C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput., 16, 329-344 (1993) · Zbl 0805.13007
[10] Fortuna, E.; Gianni, P.; Trager, B., Derivations and radicals of polynomial ideals over fields of arbitrary characteristic, J. Symbolic Comput., 33, 609-625 (2002) · Zbl 1059.13014
[11] Gianni, P.; Trager, B., Square-free algorithms in positive characteristic, Appl. Algebra Engrg. Comm. Comput., 7, 1-14 (1996) · Zbl 0874.12009
[12] Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput., 6, 149-167 (1988) · Zbl 0667.13008
[13] Kalkbrener, M., Prime decomposition of radicals in polynomial rings, J. Symbolic Comput., 18, 365-372 (1994) · Zbl 0832.13020
[14] Kemper, G., The calculation of radical ideals in positive characteristic, J. Symbolic Comput., 34, 229-238 (2002) · Zbl 1010.13001
[15] Kemper, G.; Mattig, E., Generic polynomials with few parameters, J. Symbolic Comput., 30, 843-858 (2000) · Zbl 0974.12004
[16] Maekawa, M.; Noro, M.; Ohara, K.; Takayama, N.; Tamura, Y., The design and implementation of OpenXM-RFC 100 and 101, (Proceedings of ASCM2001 (2001), World Scientific), 102-111 · Zbl 1010.68220
[17] Matsumoto, R., Computing the radical of an ideal in positive characteristic, J. Symbolic Comput., 32, 263-271 (2001) · Zbl 1028.13010
[18] Noro, M.; Yokoyama, K., A modular method to compute rational univariate representation of zero-dimensional ideals, J. Symbolic Comput., 28, 243-263 (1999) · Zbl 0945.13010
[19] Noro, M.; Yokoyama, K., Yet another practical implementation of polynomial factorization over finite fields, (Proceedings of ISSAC’02 (2002), ACM Press), 200-206 · Zbl 1072.68690
[20] Seidenberg, A., Constructions in algebra, Trans. Amer. Math. Soc., 197, 272-313 (1974) · Zbl 0356.13007
[21] Shimoyama, T.; Yokoyama, K., Localization and primary decomposition of polynomial ideals, J. Symbolic Comput., 22, 247-277 (1996) · Zbl 0874.13022
[22] Wu, W.-T., Basic principles of mechanical theorem proving in elementary geometry, J. Systems Sci. Math. Sci., 4, 207-235 (1984)
[23] Yokoyama, K., Prime decomposition of polynomial ideals over finite fields, (Mathematical Software (Proceedings of ICMS2002) (2002), World Scientific), 217-227 · Zbl 1050.13014
[24] Yokoyama, K.; Noro, M.; Takeshima, T., Solution of systems of algebraic equations and linear maps on residue class rings, J. Symbolic Comput., 14, 399-417 (1992) · Zbl 0757.13013
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.