求解多项式系统的有理表示
|
摘要
本文基于求解零维多项式系统的有理单变量表示方法做了如下几项工作:改进了Rouillier的选取零维代数簇可分元的算法,改进后的算法使得相应的有理单变量表示中整系数的长度明显缩短;将有理单变量表示方法推广到高维情形,提出了求解高维多项式系统的有理表示方法,从而将方程组的零点集表示为若干个“有理表示集”的并集,对于每个有理表示集,若固定无关变量的值,则相应解的其他坐标分量可表示为有理函数在一个单变量多项式零点处的值;讨论了有理表示方法对于代数簇不可约分支的一般点的可计算问题,证明了通过计算有理表示可以求得代数簇所有不可约分支的一般点,并提出了计算方案.
Polynomial systems solving is one of the most basic problems in mathematics.In many areas such as robot design, geometric modelling, game theory and computational economics, we need to solve all the solutions of polynomial systems. Based on the Rational Univariate Representation (RUR) for solving zero-dimensional systems, we studied the representation for the solutions of any polynomial systems. What we have done is as follows:
Ⅰ. Separating element computation for the Rational Univariate Representation with short coefficients in zero-dimensional algebraic varieties
In 1999, Rouillier introduced the Rational Univariate Representation for solving zero-dimensional systems, which gives the coordinates of the solutions as rational functions at zeros of an univariate polynomial. This representation of zeros is always used in many problems, for instance, we usually need to do some arithmetical operations over the arithmetical expressions of the solutions of coordinates. It is necessary to shorten the size of the coefficients of the polynomials in the RUR because the symbolic computations often cause intermediate swells. The RUR for a zero-dimensional ideal only depends on it's separating element. But we notice that the algorithm of finding the separating element presented by Rouillier has two shortcomings which make the coefficients in the RUR too long. The first shortcoming is that the coefficients of the elements to be selected are too long. The second one is that a lot of unnecessary computations are repeated while verifying the separating elements. For this, we present an improved algorithm for finding separating elements in this paper, which is implemented by confirming the separating element of the coordinates step by step.
Let K be a field of characteristic zero contained in C, X={X_1,…,X_n}, and let K[X_1,…,X_n] be the polynomial ring over K. Denote byπ_k the projection:π_k:C~n→C~k,(α_1,…,a_n)→(α_1,…,α_k).Given a zero-dimensional ideal I=Id(f_1,…,f_s)(?)K[X],denote by A_K(I)=K[X]/I.
Theorem 1. Let V (?) C~n,#V=m.For 1≤i≤n,we suppose that t_i∈K[X_1,…,X_i] separatesπ_i(V),then there exists at least one element in (?)_(i+1)= {u_r~(i+1)=t_i+rx_(i+1) | 0≤r≤(m-1)m/2} which separatesπ_(i+1)(V).
Theorem 2. Let P_1,P_2 6 K[X],u_r = P_1 + rP_2,r∈K.We denote by m_(u_r)~(A_K(I)) the multiplication map defined on A_K(I) associated to u_r,and X_(u_r)= (?)α_i(r)T~(D-i)(α_0(r)=1) the characteristic polynomial of m_(u_r)~(A_K(I)) Viewing r asαvariable,thenα_i(r) is a polynomial in K[r] whose degree does not exceed i. Moreover,the following equation holds:where N_j(X_(u_r)) = Trace(?) =(?)Trace(?)r~k.
Applying the above theorems, we improve the algorithm of finding a separating element presented by Rouillier. The improved algorithm is described in Algorithm 3.4.1,which implemented by finding the separating element ofπ_i(V_C(I)) step by step. The complexity of Algorithm 3.4.1 is as follows:
Theorem 3. Let I (?) K[X] be a zero-dimensional ideal, dimA_K(I)=D. Given the multiplication table M_(X_i)(1 If K is the field of rational numbers, the complexity of Algorithm 3.4.1 is in O(nD~4M(Dι) + D~3M(D~2ι)) bit-operations, whereιdenotes the binary size of the coefficients that appear in the matrix of multiplication by one variable in A_K(I) and M(ι) the complexity of the multiplication of two integers of lengthι. Moreover, the binary size of the coefficients in RUR is in O(Dι).
Ⅱ.Rational Representation for zeros of the high-dimensional ideals
In order to represent the solutions of any polynomial systems in such way as to allow any arithmetical operations over the arithmetical expressions of its coordinates, we give the so-called Rational Representation for describing all the solutions of a high-dimensional polynomial system based on the RUR for solving zero-dimensional systems.
Let now K be an algebraically closed field, / be an ideal of K[X],U= {X_(i_1,…,X_(i_d)} a maximally independent set moduloⅠ,V=X/U,and (?)_v be an arbitrary term order on T(V).Denote by V_K(I) (?) K~n the zero-set of I in K~n,and I~e the extension of I to K(U)[V].Suppose G={g_1,…,g_m} (?) I and I=Id(G) such that G is a Gr(o|¨)bner basis w.r.t.(?)_V of I~e.Set F = LCM{LC(g_i) |1≤i≤m},where LC(g_i)∈K[U] is taken of g_i as an element of K(U)[V].
Theorem 4.Let p∈K~d,and t∈(?) ={α_1X_(i_(d+1))+…+a_(n-d)X_(i_n) | 0≠(α_1,…,α_(n-d))∈K~(n-d) be a separating element of I~e.Suppose that {X_t,(?)_t(1,T),(?)_t(X_(i_(d+1)),T),…,(?)_t(X_(i_n),T)} is the RUR of I~e associated to t. Denote byΔ_t∈K[U] the numerator of the resultant of (?)_t(T) and its derivative (?)'_t(T) w.r.t.the variable T, and by (?)(T) = (?)_t(h,T)|_p for any h∈K[U][V].If FΔ_t does not vanish at p,then t separates V_k(I_p) and {X_t|_p,(?)(T),(?)(T),…, (?)(T)} is the RUR of I_p associated to t.
Define the following set:Definition 1.Let I be an ideal of K[X],U={X_(i_1),…,X_(i_d)} be a maximally independent set modulo I, and I~e the extension of I to K(U)[X\U].Suppose that t∈(?) is a separating element of I~e,and {X_t,(?)_t(1,T),(?)_t(X_(i_(d+1)),T),…, (?)_t(X_(i_n),T)} is the RUR of I~e associated to t. The setis called a Rational-representation Set of I associated to U and t. Moreover,we say that the set W_t~U is represented by R_t~U.
In particular, if dimI=0,then we call the RUR of I associated to its any separating element a Rational-representation Set.
Theorem 5. Let I be an ideal of K[X) and V_K(I) (?) K~n the zero-set of I inK~n.Then there exists a decomposition V(I)=(?)W_j such that W_j can berepresented by a Rational-representation Set R_j.We call (?)R_j a RationalRepresentation of V_K(I).
According to the above theorems, we give the Algorithm 4.4.5 for computing the Rational Representation of any polynomial systems. By this way all the solutions of any high-dimensional polynomial system can be represented by a set of so-called Rational-representation Sets. The solutions represented by a Rational-representation Set are defined as: specializing the independent variables at a point which is not a root of some polynomial in the Rational-representation Set, then the other coordinates of the corresponding solution can be expressed as rational functions at the zeros of an univariate polynomial.
Ⅲ.Representing the generic points of the irreducible components of algebraic varieties
As we know, any variety can be decomposed into several irreducible components and each irreducible component can be represented by a generic point. Based on the Rational Representation, we discussed how to compute the generic points of all the irreducible components of any algebraic variety.
Following Algorithm 4.4.5, let I_1=I,U_1 be a maximally independent set modulo I_1,and I_1~e be the extension of I_1 to K(U_1)[X\U_1].Denote by J_1=I_1~(ec); Let I_2=Id(I,F_1),U_2 be a maximally independent set modulo I_2,and I_2~e be the extension of I_2 to K(U_2)[X\U_2].Denote by J_2=I_2~(ec);Continue this process and suppose that we finally get the decomposition:where dimI_S=0.From the equation (1) we deduce that all the irreducible components of V_K(I) are included in the irreducible components of V_K(J_k) and V_K(I_S).As we know, the irreducible components of V_k(J_k) are completely identified by the zeros of I~e.In other words, all the irreducible components of V_K(J_k) can be represented by the RUR of I~e.
Proposition 6. Let V_1,V_2 be K-varieties, and assume that V_1 is irreducible. Letξbe a generic point of V_1,I(V_2) (?) K[X_1,…,X_n] be the annihilating ideal of V_2.Then V_1 (?) V_2 holds if and only if for any g∈I(V_2),g(ξ)=0.
Theorem 7. Let W_(1,1),…,W_(1,S_1) be all the irreducible components of V_K(J_1). Denote by W_(i,1),…,W_(i,S_i) the irreducible components of V_K(J_i) which are notincluded in arbitrary V_K(J_k),k Through computing the RUR of the extended ideals we can get the representation of the generic points of the irreducible components of V_K( J_k).By this and Theorem 7 we can minimize the irreducible components we obtained. The details is described in Algorithm 5.2.2.
Polynomial systems solving is one of the most basic problems in mathematics.In many areas such as robot design, geometric modelling, game theory and computational economics, we need to solve all the solutions of polynomial systems. Based on the Rational Univariate Representation (RUR) for solving zero-dimensional systems, we studied the representation for the solutions of any polynomial systems. What we have done is as follows:
Ⅰ. Separating element computation for the Rational Univariate Representation with short coefficients in zero-dimensional algebraic varieties
In 1999, Rouillier introduced the Rational Univariate Representation for solving zero-dimensional systems, which gives the coordinates of the solutions as rational functions at zeros of an univariate polynomial. This representation of zeros is always used in many problems, for instance, we usually need to do some arithmetical operations over the arithmetical expressions of the solutions of coordinates. It is necessary to shorten the size of the coefficients of the polynomials in the RUR because the symbolic computations often cause intermediate swells. The RUR for a zero-dimensional ideal only depends on it's separating element. But we notice that the algorithm of finding the separating element presented by Rouillier has two shortcomings which make the coefficients in the RUR too long. The first shortcoming is that the coefficients of the elements to be selected are too long. The second one is that a lot of unnecessary computations are repeated while verifying the separating elements. For this, we present an improved algorithm for finding separating elements in this paper, which is implemented by confirming the separating element of the coordinates step by step.
Let K be a field of characteristic zero contained in C, X={X_1,…,X_n}, and let K[X_1,…,X_n] be the polynomial ring over K. Denote byπ_k the projection:π_k:C~n→C~k,(α_1,…,a_n)→(α_1,…,α_k).Given a zero-dimensional ideal I=Id(f_1,…,f_s)(?)K[X],denote by A_K(I)=K[X]/I.
Theorem 1. Let V (?) C~n,#V=m.For 1≤i≤n,we suppose that t_i∈K[X_1,…,X_i] separatesπ_i(V),then there exists at least one element in (?)_(i+1)= {u_r~(i+1)=t_i+rx_(i+1) | 0≤r≤(m-1)m/2} which separatesπ_(i+1)(V).
Theorem 2. Let P_1,P_2 6 K[X],u_r = P_1 + rP_2,r∈K.We denote by m_(u_r)~(A_K(I)) the multiplication map defined on A_K(I) associated to u_r,and X_(u_r)= (?)α_i(r)T~(D-i)(α_0(r)=1) the characteristic polynomial of m_(u_r)~(A_K(I)) Viewing r asαvariable,thenα_i(r) is a polynomial in K[r] whose degree does not exceed i. Moreover,the following equation holds:where N_j(X_(u_r)) = Trace(?) =(?)Trace(?)r~k.
Applying the above theorems, we improve the algorithm of finding a separating element presented by Rouillier. The improved algorithm is described in Algorithm 3.4.1,which implemented by finding the separating element ofπ_i(V_C(I)) step by step. The complexity of Algorithm 3.4.1 is as follows:
Theorem 3. Let I (?) K[X] be a zero-dimensional ideal, dimA_K(I)=D. Given the multiplication table M_(X_i)(1
Ⅱ.Rational Representation for zeros of the high-dimensional ideals
In order to represent the solutions of any polynomial systems in such way as to allow any arithmetical operations over the arithmetical expressions of its coordinates, we give the so-called Rational Representation for describing all the solutions of a high-dimensional polynomial system based on the RUR for solving zero-dimensional systems.
Let now K be an algebraically closed field, / be an ideal of K[X],U= {X_(i_1,…,X_(i_d)} a maximally independent set moduloⅠ,V=X/U,and (?)_v be an arbitrary term order on T(V).Denote by V_K(I) (?) K~n the zero-set of I in K~n,and I~e the extension of I to K(U)[V].Suppose G={g_1,…,g_m} (?) I and I=Id(G) such that G is a Gr(o|¨)bner basis w.r.t.(?)_V of I~e.Set F = LCM{LC(g_i) |1≤i≤m},where LC(g_i)∈K[U] is taken of g_i as an element of K(U)[V].
Theorem 4.Let p∈K~d,and t∈(?) ={α_1X_(i_(d+1))+…+a_(n-d)X_(i_n) | 0≠(α_1,…,α_(n-d))∈K~(n-d) be a separating element of I~e.Suppose that {X_t,(?)_t(1,T),(?)_t(X_(i_(d+1)),T),…,(?)_t(X_(i_n),T)} is the RUR of I~e associated to t. Denote byΔ_t∈K[U] the numerator of the resultant of (?)_t(T) and its derivative (?)'_t(T) w.r.t.the variable T, and by (?)(T) = (?)_t(h,T)|_p for any h∈K[U][V].If FΔ_t does not vanish at p,then t separates V_k(I_p) and {X_t|_p,(?)(T),(?)(T),…, (?)(T)} is the RUR of I_p associated to t.
Define the following set:Definition 1.Let I be an ideal of K[X],U={X_(i_1),…,X_(i_d)} be a maximally independent set modulo I, and I~e the extension of I to K(U)[X\U].Suppose that t∈(?) is a separating element of I~e,and {X_t,(?)_t(1,T),(?)_t(X_(i_(d+1)),T),…, (?)_t(X_(i_n),T)} is the RUR of I~e associated to t. The setis called a Rational-representation Set of I associated to U and t. Moreover,we say that the set W_t~U is represented by R_t~U.
In particular, if dimI=0,then we call the RUR of I associated to its any separating element a Rational-representation Set.
Theorem 5. Let I be an ideal of K[X) and V_K(I) (?) K~n the zero-set of I inK~n.Then there exists a decomposition V(I)=(?)W_j such that W_j can berepresented by a Rational-representation Set R_j.We call (?)R_j a RationalRepresentation of V_K(I).
According to the above theorems, we give the Algorithm 4.4.5 for computing the Rational Representation of any polynomial systems. By this way all the solutions of any high-dimensional polynomial system can be represented by a set of so-called Rational-representation Sets. The solutions represented by a Rational-representation Set are defined as: specializing the independent variables at a point which is not a root of some polynomial in the Rational-representation Set, then the other coordinates of the corresponding solution can be expressed as rational functions at the zeros of an univariate polynomial.
Ⅲ.Representing the generic points of the irreducible components of algebraic varieties
As we know, any variety can be decomposed into several irreducible components and each irreducible component can be represented by a generic point. Based on the Rational Representation, we discussed how to compute the generic points of all the irreducible components of any algebraic variety.
Following Algorithm 4.4.5, let I_1=I,U_1 be a maximally independent set modulo I_1,and I_1~e be the extension of I_1 to K(U_1)[X\U_1].Denote by J_1=I_1~(ec); Let I_2=Id(I,F_1),U_2 be a maximally independent set modulo I_2,and I_2~e be the extension of I_2 to K(U_2)[X\U_2].Denote by J_2=I_2~(ec);Continue this process and suppose that we finally get the decomposition:where dimI_S=0.From the equation (1) we deduce that all the irreducible components of V_K(I) are included in the irreducible components of V_K(J_k) and V_K(I_S).As we know, the irreducible components of V_k(J_k) are completely identified by the zeros of I~e.In other words, all the irreducible components of V_K(J_k) can be represented by the RUR of I~e.
Proposition 6. Let V_1,V_2 be K-varieties, and assume that V_1 is irreducible. Letξbe a generic point of V_1,I(V_2) (?) K[X_1,…,X_n] be the annihilating ideal of V_2.Then V_1 (?) V_2 holds if and only if for any g∈I(V_2),g(ξ)=0.
Theorem 7. Let W_(1,1),…,W_(1,S_1) be all the irreducible components of V_K(J_1). Denote by W_(i,1),…,W_(i,S_i) the irreducible components of V_K(J_i) which are notincluded in arbitrary V_K(J_k),k
引文
[1] 浪川辛彦等,菲尔兹奖获得者森重文访问记,数学译林,12(2)(1993),129-132.
[2] B. Mourrain,The 40 "generic" positions of a parallel robot, Proc.ACM ISSAC,(1993),173-182.
[3] E. Chionh, R.N. Goldman and M. Zhang. Hybrid dixon resultants, In R.Cripps, editor, Proc. Sth IMS Conf. Math,of Surfaces, (1998), 193-212.
[4] T. Saxcna, Efficient Variable Elimination using Resultants, PhD thesis,Comp.Science Dept., State Univ. of NY, Albany, New York, 1997.
[5] M. Zhang, Topics in Resultants and Implicitization, PhD thesis, Dept. Computer Science, Rice U. , Houston, Texas. 2000.
[6] R.D. McKelvey and A. McLennan, The maximal number of regular totally mixed nash equilibria, J. Economic Theory, 72 (1997), 411-425.
[7] Smale, S. , A convergent process of price adjustment and global Newton method, J. Math. Econ. , 3(1976),1-14.
[8] D. Castro, K. Hagele,J.E.Morais and L.M. Pardo, Kronecker's and Newton's approaches to solving: a first comparison, J. Complexity,17(1)(2001). 212-303.
[9] Kellogg R. B. , Li, T. Y. and Yorke J.A. , A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer.Anal.,13(1976), 473-483.
[10] Chow, S. N. , Mallet-Paret, J. and Yorke, J. Z. , Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Comput.,32(1978), 887-899.
[11] Feng, G. C. and Yu,B.,Combined homotopy interior point method for nonlinear programming problems, Lecture Notes in Num. Anal. , 14(1995),9-16.
[12] Lin, Z., Yu, B. and Feng, G. C., A combined homotopy interior point method for convex programming problem, Appl.Math. Comput.,84 (1997), 193-211.
[13] Wu Wen-Ts(u|¨)n, On the decision problem and the mechanization of theorem proving in elementary geometry, Scientia Sinica,21 (1978), 157-179.
[14] Wu Wen-Ts(u|¨)n, Basic principles of mechanical theorem proving in geometries,J. Sys. Sci. and Math. Sci. , 4(3) (1984), 207-235.
[15] Wu Wen-Ts(u|¨)n, Some recent advances in mechanical theorem-proving of geometrise, volume 29 of Automated Theorem Proving: After 25 Years, Contemporary Mathematics, 235-242. American Mathematical Society, 1984.
[16] 杨路,不等式机器证明的降维算法与通用程序,高技术通讯,8(7)(1998),20-25.
[17] 吴文俊,王者之路,湖南科学技术出版社,1999.
[18] 于波,多项式方程组和多参数特征值问题的同伦算法,吉林大学博士学位论文,1992.
[19] D. Lazard, R(?)solution des syst(?)mes d'(?)quations alg(?)briques, Theor. Comput.Sci.,15(1)(1981), 77-110.
[20] D. Lazard, Gr(o|¨)ber Bases, Gaussian elimination and resolution of systems of algebraic equations, In Computer Algebra (London, 1983), LNCS, 162(1983),146-156, Springer, Berlin.
[21] D. Cox, J. Little and D. O'Shea, Using Algebraic Geometry, Springer-Verlag,New York, 1998.
[22] B. van der Waeden, Moderne Algebra, Volume Ⅱ, Springer-Verleg, Berlin,1931.
[23] Buchberger, B. , Ein algorithmisches Kriterium f(u|¨)r die Losbarkeit eines algebraischen Gleischunssystem, Aeq. Math. , 4(1970), 374-383.
[24] Kobayashi, H. , Moritsugu, S. and Hogan, R. W. , On solving systems of algebraic equations, In Proceedings of the ISSAC'88, LNCS 358(1988), Springer,139-149.
[25] Lazard D., Solving zero-dimensional algebraic systems, J. Symbolic Comput,13 (1992), 117-132.
[26] J. Faugere, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero-dimensional Grobner bases by change of ordering, J. Symbolic Comput,16(1993), 329-344.
[27] 杨路,张景中,侯晓荣,非线性代数方程组与定理机器证明,上海科技教育出版社,1996.
[28] Chionh E. , Base Points, Resultants, And the Implicit Representation of Rational Surfaces, Ph. D. thesis, Dept. Comp.Sci. , Univ. of Waterloo, 1990.
[29] Assigner , W. and Stetter, H. J. , A Study of Numerical Elimination for the Multivariate Polynomial System, Preprint.
[30] Assigner , W. and Stetter, H. J. , An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Inter.,Series of Numer. Math., 86 (1988),11-30.
[31] Stetter, H. J. , Matrix eigenproblem are at the heart of polynomial system solving, ACM SIGSAM Bull.,30(4) (1996), 27-36.
[32] Huang Yu-Zhen and Wu Wen-da, A modified version of an algorithm for solving multivariate polynomial system, M. M. Research preprints, 5 (1990),23-29.
[33] Feng Guo-chen and Zhang Shu-gong, Reducing the multivariate polynomial system to eigenvalue problem, Northeast Math. J. , 8(8) (1992), 253-256.
[34] Feng Guo-chen, Wu Wen-da and Zhang Shu-gong, The eigenvalue problem equivalent to multivariete polynomial system, Northeast Math. J.,9(1)(1993),5-8.
[35] Feng Guo-chen, Wu Wen-da and Huang Kai, The computation of eigenvalue problem equivalent to multivariate polynomial system and the Grobner basis,Adv. Math,(in China) , 22(3) (1993), 282-284.
[36] 张传林,特征值方法在高维代数簇计算中的应用,吉林大学博士论文,1995.
[37] R. M.Corless.,Grobner bases and matrix eigenproblems, ACM SIGSAM Bulletin, 30(4)(1996), 26-32.
[38] Kaltofen, E. , Corless, R. M. and Jeffrey, D. J. , Challenges of symbolic computation: my favorite open problems, J. Symbolic Comput. , 29(6)(2000),891-919.
[39] Marinari, M. G. , Moller, H. M. and Mora, T., On multiplicities in polynomial system solving, Trans Am Math Soc , 348(8) (1996), 283-321.
[40] Fabrice Rouillier, Solving zero-Dimensional systems through the rational univariate representation, AAECC, 9 (1999), 433-461.
[41] D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms,Springer-Verlag, New York, 1997.
[42] 张树功,雷娜,刘停战,计算机代数基础,科学出版社,2005.
[43] E. Kunz, Introduction to Commutative Algebra and Algebraic Geometry,Birkhauser, Boston, 1985.
[44] T. Becker and V.Weispfenning, Gr(o|¨)bner Bases, Springer-Verlag, New York,1993.
[45] Becker, E. , Marinari, M. G. , Mora, T. and Traverso, C. , The shape of the Shape Lemma, In Proceedings of the ISSAC'94, ACM, 129-133.
[46] W. V. Hodge and D. Peode, Methods of Algebraic Geometry, Cambridge University Press, 1968.
[47] Becker, E. and W(o|¨)rmann, T. , Radical computation of a zero-dimensional ideal and real root counting, Mathematics and Computers in Simulation, 42(4-6)(1996), 561-569.
[48] Gianni, P. and Mora, T. , Algebraic solution of systems of polynomial equations using Grobner bases, In Proceedings of the AAECC-5,LNCS 356(1989),Springer, 247-257.
[49] Faug(?)re, J.-C. , Gianni, P. , Lazard, D. and Mora, T. , Efficient computation of zero-dimensional Grobner bases by change of ordering, J. Symb.Comput.,16(1993), 329-344.
[50] Alonso, M.-E.,Becker, E. and Roy, M.-F. , Zeros, multiplicities and idempotents for zero dimensional systems, In Algorithms in Algebraic Geometry and Applications, Birkha(u|¨)ser, Basel, 1996,1-15.
[51] Gonzalez-Vega, L., Rouillier, F., Roy, M.-F. , Symbolic recipes for polynomial system solving, In Some Tapas of Compute Algebra, Springer-Verlag, New York, 1999, 34-66.
[52] Rouillier. F. , On the rational univariate representation, In ICPSS, 2004, 75-79.
[53] Masayuki Noro and Kazuhiro Yokoyama,A modular method to compute the rational univariate representation of zero-dimensional ideals, J. Symb. Cornput. , 28(1999), 243-263.
[54] Alin Bostan, Bruno Salvy, and (?)ric Schost, Fast algorithm for zero-dimensional polynomial systems using duality, AAECC, 14(2003), 239-272.
[55] Shoup, V.,Fast construction of irreducible polynomials over finite fields, J.Symb. Comput. ,17(5)(1994), 371-391.
[56] A.L. Chistov, Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic, J. Symb. Comput. , 22(1)(1996),1-25.
[57] Fabrice Rouillier, Resolution des Sysi(?)mes Zero-dimensionnels, PhD thesis,University of Rennes Ⅰ, France.
[58] Marinari, M. G., Moller, H. M. and Mora, T., On multiplicities in polynomial system solving, Thins Am Math Soc,348(8)(1996), 283-321.
[59] Heinz Kredel and Volker Weispfenning, Computing dimension and independent sets for polynomial ideals, J. Symb. comp. , 6(1988), 231-247.
[60] 张传林,冯果忱,模多项式理想无关变元组的判定,高等学校计算数学学报,1(1998),16-22.
[61] 张树功,特征值方法的理论及算法实现,吉林大学博士论文,1993.
[62] A.L. Chistov, Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic, J. Pure Appl.Algebra,117-118(1997),1-25.
[63] M. Elkadi and B. Mourrain, A new algorithm for the geometric decomposition of a variety, In Proceedings of ISSAC99, ACM, New York, 1999.
[64] G. Lecerf, Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In Proceedings of ISSAC'2000,ACM,New York, 2000, 209-216.
[2] B. Mourrain,The 40 "generic" positions of a parallel robot, Proc.ACM ISSAC,(1993),173-182.
[3] E. Chionh, R.N. Goldman and M. Zhang. Hybrid dixon resultants, In R.Cripps, editor, Proc. Sth IMS Conf. Math,of Surfaces, (1998), 193-212.
[4] T. Saxcna, Efficient Variable Elimination using Resultants, PhD thesis,Comp.Science Dept., State Univ. of NY, Albany, New York, 1997.
[5] M. Zhang, Topics in Resultants and Implicitization, PhD thesis, Dept. Computer Science, Rice U. , Houston, Texas. 2000.
[6] R.D. McKelvey and A. McLennan, The maximal number of regular totally mixed nash equilibria, J. Economic Theory, 72 (1997), 411-425.
[7] Smale, S. , A convergent process of price adjustment and global Newton method, J. Math. Econ. , 3(1976),1-14.
[8] D. Castro, K. Hagele,J.E.Morais and L.M. Pardo, Kronecker's and Newton's approaches to solving: a first comparison, J. Complexity,17(1)(2001). 212-303.
[9] Kellogg R. B. , Li, T. Y. and Yorke J.A. , A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer.Anal.,13(1976), 473-483.
[10] Chow, S. N. , Mallet-Paret, J. and Yorke, J. Z. , Finding zeros of maps: Homotopy methods that are constructive with probability one, Math. Comput.,32(1978), 887-899.
[11] Feng, G. C. and Yu,B.,Combined homotopy interior point method for nonlinear programming problems, Lecture Notes in Num. Anal. , 14(1995),9-16.
[12] Lin, Z., Yu, B. and Feng, G. C., A combined homotopy interior point method for convex programming problem, Appl.Math. Comput.,84 (1997), 193-211.
[13] Wu Wen-Ts(u|¨)n, On the decision problem and the mechanization of theorem proving in elementary geometry, Scientia Sinica,21 (1978), 157-179.
[14] Wu Wen-Ts(u|¨)n, Basic principles of mechanical theorem proving in geometries,J. Sys. Sci. and Math. Sci. , 4(3) (1984), 207-235.
[15] Wu Wen-Ts(u|¨)n, Some recent advances in mechanical theorem-proving of geometrise, volume 29 of Automated Theorem Proving: After 25 Years, Contemporary Mathematics, 235-242. American Mathematical Society, 1984.
[16] 杨路,不等式机器证明的降维算法与通用程序,高技术通讯,8(7)(1998),20-25.
[17] 吴文俊,王者之路,湖南科学技术出版社,1999.
[18] 于波,多项式方程组和多参数特征值问题的同伦算法,吉林大学博士学位论文,1992.
[19] D. Lazard, R(?)solution des syst(?)mes d'(?)quations alg(?)briques, Theor. Comput.Sci.,15(1)(1981), 77-110.
[20] D. Lazard, Gr(o|¨)ber Bases, Gaussian elimination and resolution of systems of algebraic equations, In Computer Algebra (London, 1983), LNCS, 162(1983),146-156, Springer, Berlin.
[21] D. Cox, J. Little and D. O'Shea, Using Algebraic Geometry, Springer-Verlag,New York, 1998.
[22] B. van der Waeden, Moderne Algebra, Volume Ⅱ, Springer-Verleg, Berlin,1931.
[23] Buchberger, B. , Ein algorithmisches Kriterium f(u|¨)r die Losbarkeit eines algebraischen Gleischunssystem, Aeq. Math. , 4(1970), 374-383.
[24] Kobayashi, H. , Moritsugu, S. and Hogan, R. W. , On solving systems of algebraic equations, In Proceedings of the ISSAC'88, LNCS 358(1988), Springer,139-149.
[25] Lazard D., Solving zero-dimensional algebraic systems, J. Symbolic Comput,13 (1992), 117-132.
[26] J. Faugere, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero-dimensional Grobner bases by change of ordering, J. Symbolic Comput,16(1993), 329-344.
[27] 杨路,张景中,侯晓荣,非线性代数方程组与定理机器证明,上海科技教育出版社,1996.
[28] Chionh E. , Base Points, Resultants, And the Implicit Representation of Rational Surfaces, Ph. D. thesis, Dept. Comp.Sci. , Univ. of Waterloo, 1990.
[29] Assigner , W. and Stetter, H. J. , A Study of Numerical Elimination for the Multivariate Polynomial System, Preprint.
[30] Assigner , W. and Stetter, H. J. , An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Inter.,Series of Numer. Math., 86 (1988),11-30.
[31] Stetter, H. J. , Matrix eigenproblem are at the heart of polynomial system solving, ACM SIGSAM Bull.,30(4) (1996), 27-36.
[32] Huang Yu-Zhen and Wu Wen-da, A modified version of an algorithm for solving multivariate polynomial system, M. M. Research preprints, 5 (1990),23-29.
[33] Feng Guo-chen and Zhang Shu-gong, Reducing the multivariate polynomial system to eigenvalue problem, Northeast Math. J. , 8(8) (1992), 253-256.
[34] Feng Guo-chen, Wu Wen-da and Zhang Shu-gong, The eigenvalue problem equivalent to multivariete polynomial system, Northeast Math. J.,9(1)(1993),5-8.
[35] Feng Guo-chen, Wu Wen-da and Huang Kai, The computation of eigenvalue problem equivalent to multivariate polynomial system and the Grobner basis,Adv. Math,(in China) , 22(3) (1993), 282-284.
[36] 张传林,特征值方法在高维代数簇计算中的应用,吉林大学博士论文,1995.
[37] R. M.Corless.,Grobner bases and matrix eigenproblems, ACM SIGSAM Bulletin, 30(4)(1996), 26-32.
[38] Kaltofen, E. , Corless, R. M. and Jeffrey, D. J. , Challenges of symbolic computation: my favorite open problems, J. Symbolic Comput. , 29(6)(2000),891-919.
[39] Marinari, M. G. , Moller, H. M. and Mora, T., On multiplicities in polynomial system solving, Trans Am Math Soc , 348(8) (1996), 283-321.
[40] Fabrice Rouillier, Solving zero-Dimensional systems through the rational univariate representation, AAECC, 9 (1999), 433-461.
[41] D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms,Springer-Verlag, New York, 1997.
[42] 张树功,雷娜,刘停战,计算机代数基础,科学出版社,2005.
[43] E. Kunz, Introduction to Commutative Algebra and Algebraic Geometry,Birkhauser, Boston, 1985.
[44] T. Becker and V.Weispfenning, Gr(o|¨)bner Bases, Springer-Verlag, New York,1993.
[45] Becker, E. , Marinari, M. G. , Mora, T. and Traverso, C. , The shape of the Shape Lemma, In Proceedings of the ISSAC'94, ACM, 129-133.
[46] W. V. Hodge and D. Peode, Methods of Algebraic Geometry, Cambridge University Press, 1968.
[47] Becker, E. and W(o|¨)rmann, T. , Radical computation of a zero-dimensional ideal and real root counting, Mathematics and Computers in Simulation, 42(4-6)(1996), 561-569.
[48] Gianni, P. and Mora, T. , Algebraic solution of systems of polynomial equations using Grobner bases, In Proceedings of the AAECC-5,LNCS 356(1989),Springer, 247-257.
[49] Faug(?)re, J.-C. , Gianni, P. , Lazard, D. and Mora, T. , Efficient computation of zero-dimensional Grobner bases by change of ordering, J. Symb.Comput.,16(1993), 329-344.
[50] Alonso, M.-E.,Becker, E. and Roy, M.-F. , Zeros, multiplicities and idempotents for zero dimensional systems, In Algorithms in Algebraic Geometry and Applications, Birkha(u|¨)ser, Basel, 1996,1-15.
[51] Gonzalez-Vega, L., Rouillier, F., Roy, M.-F. , Symbolic recipes for polynomial system solving, In Some Tapas of Compute Algebra, Springer-Verlag, New York, 1999, 34-66.
[52] Rouillier. F. , On the rational univariate representation, In ICPSS, 2004, 75-79.
[53] Masayuki Noro and Kazuhiro Yokoyama,A modular method to compute the rational univariate representation of zero-dimensional ideals, J. Symb. Cornput. , 28(1999), 243-263.
[54] Alin Bostan, Bruno Salvy, and (?)ric Schost, Fast algorithm for zero-dimensional polynomial systems using duality, AAECC, 14(2003), 239-272.
[55] Shoup, V.,Fast construction of irreducible polynomials over finite fields, J.Symb. Comput. ,17(5)(1994), 371-391.
[56] A.L. Chistov, Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic, J. Symb. Comput. , 22(1)(1996),1-25.
[57] Fabrice Rouillier, Resolution des Sysi(?)mes Zero-dimensionnels, PhD thesis,University of Rennes Ⅰ, France.
[58] Marinari, M. G., Moller, H. M. and Mora, T., On multiplicities in polynomial system solving, Thins Am Math Soc,348(8)(1996), 283-321.
[59] Heinz Kredel and Volker Weispfenning, Computing dimension and independent sets for polynomial ideals, J. Symb. comp. , 6(1988), 231-247.
[60] 张传林,冯果忱,模多项式理想无关变元组的判定,高等学校计算数学学报,1(1998),16-22.
[61] 张树功,特征值方法的理论及算法实现,吉林大学博士论文,1993.
[62] A.L. Chistov, Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic, J. Pure Appl.Algebra,117-118(1997),1-25.
[63] M. Elkadi and B. Mourrain, A new algorithm for the geometric decomposition of a variety, In Proceedings of ISSAC99, ACM, New York, 1999.
[64] G. Lecerf, Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions. In Proceedings of ISSAC'2000,ACM,New York, 2000, 209-216.