RESEARCH ARTICLE

Normal projection: deterministic and probabilistic algorithms

  • Dongmei LI 1 ,
  • Jinwang LIU 1 ,
  • Weijun LIU , 2
Expand
  • 1. Department of Mathematics and Computing Sciences, Hunan University of Science and Technology, Xiangtan 411201, China
  • 2. Department of Mathematics and Statistics, Central South University, Changsha 410083, China

Received date: 13 Jul 2013

Accepted date: 04 Dec 2013

Published date: 01 Feb 2014

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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.

Cite this article

Dongmei LI , Jinwang LIU , Weijun LIU . Normal projection: deterministic and probabilistic algorithms[J]. Frontiers of Mathematics in China, 2014 , 9(1) : 93 -99 . DOI: 10.1007/s11464-013-0349-z

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Options
Outlines

/