Normal projection: deterministic and probabilistic algorithms

Abstract

We consider the following problem: for a collection of points in an n-dimensional space, find a linear projection mapping the points to the ground field such that different points are mapped to different values. Such projections are called normal and are useful for making algebraic varieties into normal positions. The points may be given explicitly or implicitly and the coefficients of the projection come from a subset S of the ground field. If the subset S is small, this problem may be hard. This paper deals with relatively large S, a deterministic algorithm is given when the points are given explicitly, and a lower bound for success probability is given for a probabilistic algorithm from in the literature.

Keywords

Normal projection / primary decomposition of ideal / deterministic algorithm

References

[1] Adams W, Loustaunau P. An Introduction to Gröbner Bases. Graduate Studies in Mathematics 3. Providence: Amer Math Soc, 1994

[2] Becker T, Weispfenning V. Gröbner Bases—A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics, Vol 141. New York: Springer, 1993

[3] Buchberger B. Gröbner bases: An algorithmic method in polynomial ideal theory. In: Bose N K, ed. Recent Trends in Multidimensional Systems Theory. Dordrecht: Reidel D, 1985, Chapter 6

[4] Decker W, Greuel G-M, Pfister G. Primary decomposition: algorithms and comparisons. In: Matzat B H, Greuel G-M, Hiss G, eds. Algorithmic Algebra and Number Theory (Heidelberg, 1997). Berlin: Springer, 1999, 187-220

[5] Gao S. Factoring multivariate polynomials via partial differential equations. Math Comp, 2003, 72: 801-822

[6] Gao S, Wan D, Wang M. Primary decomposition of zero-dimensional ideals over finite fields. Math of Comp, 2009, 78: 509-521

[7] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. New York: W H Freeman, 1979

[8] Grabe H-G. Minimal primary decomposition and factorized Gröbner bases. Appl Algebra Engrg Comm Comput, 1997, 8: 265-278

[9] Greuel G-M, Pfister G. A Singular Introduction to Commutative Algebra. New York: Spinger-Verlag, 2002

[10] Liu J, Li D. The λ-Gröbner bases under polynomial composition. J Syst Sci Complex, 2007, 20: 610-613

[11] Liu J, Wang M. Homogeneous Gröbner bases under composition. J Algebra, 2006, 303: 668-676

[12] Liu J, Wang M. Further results on homogeneous Gröbner bases under composition. J Algebra, 2007, 315: 134-143

[13] Monico C. Computing the primary decomposition of zero-dimensional ideals. J Symbolic Comput, 2002, 34: 451-459

[14] Sausse A. A new approach to primary decomposition. J Symbolic Comput, 2001, 31: 243-257

[15] Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities. J ACM, 1980, 27: 701-717

[16] Steel A. Conquering inseparability:primary decomposition and multivariate factorization over algebraic function fields of positive characteristic. J Symbolic Comput, 2005, 40: 1053-1075

[17] Takayama N. An approach to the zero recognition problem by Buchberger algorithm. J Symbolic Comput, 1992, 14: 265-282

[18] Wang D. Decomposing algebraic varieties, Automated deduction in geometry (Beijing, 1998). In: Lecture Notes Comput Sci, Vol 1669. Berlin: Springer, 1999, 180-206

[19] Zippel R. Probabilistic algorithms for sparse polynomials. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. 1979, 216-226

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg