Primary decomposition of zero-dimensional ideals over finite fields

Gao, Shuhong; Wan, Daqing; Wang, Mingsheng

doi:10.1090/S0025-5718-08-02115-7

Primary decomposition of zero-dimensional ideals over finite fields
HTML articles powered by AMS MathViewer

by Shuhong Gao, Daqing Wan and Mingsheng Wang;

Math. Comp. 78 (2009), 509-521

DOI: https://doi.org/10.1090/S0025-5718-08-02115-7

Published electronically: May 1, 2008

PDF | Request permission

Abstract:

A new algorithm is presented for computing primary decomposition of zero-dimensional ideals over finite fields. Like Berlekamp’s algorithm for univariate polynomials, the new method is based on the invariant subspace of the Frobenius map acting on the quotient algebra. The dimension of the invariant subspace equals the number of primary components, and a basis of the invariant subspace yields a complete decomposition. Unlike previous approaches for decomposing multivariate polynomial systems, the new method does not need primality testing nor any generic projection, instead it reduces the general decomposition problem directly to root finding of univariate polynomials over the ground field. Also, it is shown how Gröbner basis structure can be used to get partial primary decomposition without any root finding.

References

Thomas Becker and Volker Weispfenning, Gröbner bases, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. A computational approach to commutative algebra; In cooperation with Heinz Kredel. MR 1213453, DOI 10.1007/978-1-4612-0913-3
E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Wolfram Decker, Gert-Martin Greuel, and Gerhard Pfister, Primary decomposition: algorithms and comparisons, Algorithmic algebra and number theory (Heidelberg, 1997) Springer, Berlin, 1999, pp. 187–220. MR 1672046
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
David Eisenbud, Craig Huneke, and Wolmer Vasconcelos, Direct methods for primary decomposition, Invent. Math. 110 (1992), no. 2, 207–235. MR 1185582, DOI 10.1007/BF01231331
J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329–344. MR 1263871, DOI 10.1006/jsco.1993.1051
Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Math. Comp. 72 (2003), no. 242, 801–822. MR 1954969, DOI 10.1090/S0025-5718-02-01428-X
S. Gao, Y. Guan and R. Heindl, “Factoring bivariate polynomials via Niederreiter’s differential equation”, in preparation.
S. Gao, V. M. Rodrigues and J. Stroomer, “Gröbner basis structure of finite sets of points”, preprint 2003.
Hans-Gert Gräbe, Minimal primary decomposition and factorized Gröbner bases, Appl. Algebra Engrg. Comm. Comput. 8 (1997), no. 4, 265–278. MR 1464788, DOI 10.1007/s002000050064
Patrizia Gianni, Barry Trager, and Gail Zacharias, Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput. 6 (1988), no. 2-3, 149–167. Computational aspects of commutative algebra. MR 988410, DOI 10.1016/S0747-7171(88)80040-3
Gert-Martin Greuel and Gerhard Pfister, A Singular introduction to commutative algebra, Springer-Verlag, Berlin, 2002. With contributions by Olaf Bachmann, Christoph Lossen and Hans Schönemann; With 1 CD-ROM (Windows, Macintosh, and UNIX). MR 1930604, DOI 10.1007/978-3-662-04963-1
Mark van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory 95 (2002), no. 2, 167–189. MR 1924096, DOI 10.1016/S0022-314X(01)92763-5
Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921–933. MR 2197000, DOI 10.1090/S0025-5718-06-01810-2
Chris Monico, Computing the primary decomposition of zero-dimensional ideals, J. Symbolic Comput. 34 (2002), no. 5, 451–459. MR 1937469, DOI 10.1006/jsco.2002.0571
Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262, DOI 10.1090/S0025-5718-1994-1216262-2
Joseph Fels Ritt, Differential algebra, Dover Publications, Inc., New York, 1966. MR 201431
Alain Sausse, A new approach to primary decomposition, J. Symbolic Comput. 31 (2001), no. 1-2, 243–257. Computational algebra and number theory (Milwaukee, WI, 1996). MR 1806219, DOI 10.1006/jsco.2000.1017
A. Seidenberg, On the Lasker-Noether decomposition theorem, Amer. J. Math. 106 (1984), no. 3, 611–638. MR 745143, DOI 10.2307/2374287
Takeshi Shimoyama and Kazuhiro Yokoyama, Localization and primary decomposition of polynomial ideals, J. Symbolic Comput. 22 (1996), no. 3, 247–277. MR 1427183, DOI 10.1006/jsco.1996.0052
Allan Steel, Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic, J. Symbolic Comput. 40 (2005), no. 3, 1053–1075. MR 2167699, DOI 10.1016/j.jsc.2005.03.002
Wolmer V. Vasconcelos, Computational methods in commutative algebra and algebraic geometry, Algorithms and Computation in Mathematics, vol. 2, Springer-Verlag, Berlin, 1998. With chapters by David Eisenbud, Daniel R. Grayson, Jürgen Herzog and Michael Stillman. MR 1484973, DOI 10.1007/978-3-642-58951-5
Daqing Wan, Computing zeta functions over finite fields, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997) Contemp. Math., vol. 225, Amer. Math. Soc., Providence, RI, 1999, pp. 131–141. MR 1650604, DOI 10.1090/conm/225/03215
Dongming Wang, Decomposing algebraic varieties, Automated deduction in geometry (Beijing, 1998) Lecture Notes in Comput. Sci., vol. 1669, Springer, Berlin, 1999, pp. 180–206. MR 1775951, DOI 10.1007/3-540-47997-X_{1}0
Wen Jun Wu, Basic principles of mechanical theorem proving in elementary geometries, J. Systems Sci. Math. Sci. 4 (1984), no. 3, 207–235 (English, with Chinese summary). MR 795000
Wen Tsün Wu, Mechanical theorem proving in geometries, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1994. Basic principles; Translated from the 1984 Chinese original by Xiao Fan Jin and Dong Ming Wang. MR 1284925, DOI 10.1007/978-3-7091-6639-0