The Rational Representation For Solving Polynomial Systems

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 varietiesIn 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₁,…,X_n}, and let K[X₁,…,X_n] be the polynomial ring over K. Denote byÏ€_k the projection:Ï€_k:Cⁿ→C^k,(α₁,…,a_n)→(α₁,…,α_k).Given a zero-dimensional ideal I=Id(f₁,…,f_s)(?)K[X],denote by A_K(I)=K[X]/I.Theorem 1. Let V (?) Cⁿ,#V=m.For 1≤i≤n,we suppose that t_i∈K[X₁,…,X_i] separatesÏ€_i(V),then there exists at least one element in (?)_i+1= {u_rⁱ⁺¹=t_i+rx_i+1 | 0≤r≤(m-1)m/2} which separatesÏ€_i+1(V).Theorem 2. Let P₁,P₂ 6 K[X],u_r = P₁ + rP₂,r∈K.We denote by m_ur^A_K(I) the multiplication map defined on A_K(I) associated to u_r,and X_ur= (?)α_i(r)T^D-i(α₀(r)=1) the characteristic polynomial of m_ur^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_ur) = 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_Xi(1K(I)) associated to a standard basis of A_K(I),the complexity of Algorithm 3.4.1 is in O(nD⁴) basic arithmetic operations in K.If K is the field of rational numbers, the complexity of Algorithm 3.4.1 is in O(nD⁴M(Dι) + D³M(D²Î¹)) 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 idealsIn 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₁,…,X_id} a maximally independent set moduloâ… ,V=X/U,and (?)_v be an arbitrary term order on T(V).Denote by V_K(I) (?) Kⁿ the zero-set of I in Kⁿ,and I^e the extension of I to K(U)[V].Suppose G={g₁,…,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∈(?) ={α₁X_id+1+…+a_n-dX_in | 0≠(α₁,…,α_n-d)∈K^n-d be a separating element of I^e.Suppose that {X_t,(?)_t(1,T),(?)_t(X_id+1,T),…,(?)_t(X_in,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_i1,…,X_id} 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_id+1,T),…, (?)_t(X_in,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ⁿ the zero-set of I inKⁿ.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 varietiesAs 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₁=I,U₁ be a maximally independent set modulo I₁,and I₁^e be the extension of I₁ to K(U₁)[X\U₁].Denote by J₁=I₁^ec; Let I₂=Id(I,F₁),U₂ be a maximally independent set modulo I₂,and I₂^e be the extension of I₂ to K(U₂)[X\U₂].Denote by J₂=I₂^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₁,V₂ be K-varieties, and assume that V₁ is irreducible. Letξbe a generic point of V₁,I(V₂) (?) K[X₁,…,X_n] be the annihilating ideal of V₂.Then V₁ (?) V₂ holds if and only if for any g∈I(V₂),g(ξ)=0. Theorem 7. Let W_1,1,…,W_1,S1 be all the irreducible components of V_K(J₁). Denote by W_i,1,…,W_i,Si the irreducible components of V_K(J_i) which are notincluded in arbitrary V_K(J_k),ki,j is the irreducibledecomposition of V_K(I).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.