Normal projection: deterministic and probabilistic algorithms

doi:10.1007/s11464-013-0349-z

Front Math Chin

2014, Vol. 9

Issue (1) : 93-99 https://doi.org/10.1007/s11464-013-0349-z

RESEARCH ARTICLE

Normal projection: deterministic and probabilistic algorithms

Dongmei LI¹, Jinwang LIU¹, Weijun LIU²(

)

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

Download: PDF(85 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): LIU Weijun,Email:wjliu@csu.edu.cn

Issue Date: 01 February 2014

Cite this article:

Dongmei LI,Jinwang LIU,Weijun LIU. Normal projection: deterministic and probabilistic algorithms[J]. Front Math Chin, 2014, 9(1): 93-99.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-013-0349-z
https://academic.hep.com.cn/fmc/EN/Y2014/V9/I1/93

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: 10.1007/978-3-642-59932-3_10
5	Gao S. Factoring multivariate polynomials via partial differential equations. Math Comp , 2003, 72: 801-822 doi: 10.1090/S0025-5718-02-01428-X
6	Gao S, Wan D, Wang M. Primary decomposition of zero-dimensional ideals over finite fields. Math of Comp , 2009, 78: 509-521 doi: 10.1090/S0025-5718-08-02115-7
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: 10.1007/s002000050064
9	Greuel G-M, Pfister G. A Singular Introduction to Commutative Algebra. New York: Spinger-Verlag, 2002 doi: 10.1007/978-3-662-04963-1
10	Liu J, Li D. The λ-Gr?bner bases under polynomial composition. J Syst Sci Complex , 2007, 20: 610-613 doi: 10.1007/s11424-007-9059-5
11	Liu J, Wang M. Homogeneous Gr?bner bases under composition. J Algebra , 2006, 303: 668-676 doi: 10.1016/j.jalgebra.2005.08.037
12	Liu J, Wang M. Further results on homogeneous Gr?bner bases under composition. J Algebra , 2007, 315: 134-143 doi: 10.1016/j.jalgebra.2007.05.023
13	Monico C. Computing the primary decomposition of zero-dimensional ideals. J Symbolic Comput , 2002, 34: 451-459 doi: 10.1006/jsco.2002.0571
14	Sausse A. A new approach to primary decomposition. J Symbolic Comput , 2001, 31: 243-257 doi: 10.1006/jsco.2000.1017
15	Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities. J ACM , 1980, 27: 701-717 doi: 10.1145/322217.322225
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: 10.1016/j.jsc.2005.03.002
17	Takayama N. An approach to the zero recognition problem by Buchberger algorithm. J Symbolic Comput , 1992, 14: 265-282 doi: 10.1016/0747-7171(92)90039-7
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: 10.1007/3-540-09519-5_73

Viewed

Full text

Abstract

Cited

Shared

Discussed