Primary decomposition of zero-dimensional ideals over finite fields
HTML articles powered by AMS MathViewer
- by Shuhong Gao, Daqing Wan and Mingsheng Wang PDF
- Math. Comp. 78 (2009), 509-521 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 0201431
- 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
Additional Information
- Shuhong Gao
- Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975
- MR Author ID: 291308
- Email: sgao@math.clemson.edu
- Daqing Wan
- Affiliation: Department of Mathematics, University of California, Irvine, California 92697-3875
- MR Author ID: 195077
- Email: dwan@math.uci.edu
- Mingsheng Wang
- Affiliation: Information Security laboratory, Institute of Software, Chinese Academy of Sciences, Box 8718, Beijing 100080, People’s Republic of China
- Email: mingsheng\_wang@yahoo.com.cn
- Received by editor(s): December 1, 2006
- Received by editor(s) in revised form: October 29, 2007
- Published electronically: May 1, 2008
- Additional Notes: The work was done while the authors were visiting IMA at University of Minnesota in Fall 2006. Gao and Wan were supported in part by National Science Foundation (NSF), and Wang was partially supported by 973 Projects (2004CB318004) and NSFC (60573041).
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 78 (2009), 509-521
- MSC (2000): Primary 13P10, 68W30; Secondary 11Y16, 12Y05, 13P05
- DOI: https://doi.org/10.1090/S0025-5718-08-02115-7
- MathSciNet review: 2448718