Solving M-Homogeneous Polynomial Systems

Polynomial systems solving is one of the most basic problems in mathematics. In many areas including robot design, geometric modelling, game theory and computational economics, we need to solve all the solutions of polynomial systems.Homotopy continuation method is an efficient numerical algorithm for computing all isolated solutions of polynomial systems, e.g., Smale's global Newton methods. For we need to design a homotopy path for every solution, so the key of homotopy method is to estimate the number of the solutions. It's well known that Bezout theorem is a classic estimate. But, if we want to get the better estimate, we must concern the character of the systems. m-Homogeneous systems are encountered in several areas including the areas we mentioned above. So people start to construct the specific homotopy for m-homogeneous systems, e.g., Morgan and Sommese, Yu Bo and Jan Verschelde etc. have given kinds of m-homogeneous homotopy. They all use the the character that the m-homogeneous systems have less m-Bezout numbers and can decrease the number of the path.Wu's method has been known as the most efficient method for geometric theorem proving and the parameter systems solving. But, it's very hard to deal with the rapidly increasing degree of the polynomial in computing.Grobner bases w.r.t pure lex order can be used to solve the polynomial systems. But the upper bound degree is double exponential. Lazard can give Grobner bases w.r.t degree-reverse-lex order by resultant theory, and get the bases w.r.t lex order by FGML algorithms. Then, solutions is given by eliminating the variable one by one.For inspired by the results above, we consider to design more efficient method for solving m-homogeneous systems based on the construct algebra. And it can decrease the complexity of computation. e.g., the upper bound degree of the Grobner bases w.r.t. lex order of F(X₁,X₂) is O(d²ⁿ), which d is the degree of F and n is number of variables. But, if we think X₁ be parameters and F be a polynomial system of X₂, then the upper bound degree of Grobner bases is O(d₂²ⁿ², which d₂ is the degree of F about X₂ and n-2 is the variables' number about X-2.We always suppose that V(F^h) is a finite set. Notice that the m-homogeneous system is equivalent to m systems which has independent variables. e.g., the 2-homogeneous equations F(X₁,X₂) =0 about X₁ and X₂ can reduce to two equations F₁(X₁) = 0 and F₂(X₂) = 0, and their solutions are equivalent.In this paper we present the corresponding methods for m-homogeneous systems to construct the equivalent systems based on Wu's method and Lazard's resultant method, and then we can block-solve the systems.By Segre map we can divide the variables of F to m parts and use the m-Bezout theorem to get the m-Bezout number. But only when the system is m-homogeneous, its m-Bezout number is smaller than the Bezout number. Then we get the following principle:Principle: For given polynomial systems, we call it's m-homogeneous, if its m-Bezout number is smaller than the Bezout number for some variables' dividing.We can use the methods presented by Wampler, Tiejun Li, Fengshan Bai, Zhengjiang Lin and Cao Xiaofei etc. to get the better dividing of the variables in order to decrease the m-Bezout number as possible as we can. First, we consider Wu's method. We start by 2-homogeneous systems. We call A = {A₁, A₂}= {A₁₁,..., A_1r1,A₂₁,..., A_2r2} is a block-triangular series, if CLS(A_ij) = i and A₁₁(?)...(?) A_2r2. Let I_2j be leading coefficient of A_2j and I_A be the product of them.Definition 1 We call f is reduced w.r.t block-triangular series A, if LM(A_ij) is not a factor of the monomials about X_i of f for all A_ij∈A.Definition 2 We call a block-triangular series A be a block-ascending series, if A_ij is reduced w.r.t {A₁₁,...,A_ij} \ {A_ij} for all (i,j).Then we can get the following remainder formula.Proposition 1 Let f∈K[X] and A be block-ascending series, thenI₂₁^k1...I^2r2kr1 f = q₁₁A₁₁ + ... + q_2r2A_2r2 + Rwhich k_ij∈N₀, q_ij,R∈K[X], and R is reduced w.r.t A. We call R be the remainder of f w.r.t. A.We call the set consisting of the nonzero remainder of ail f∈F w.r.t A be the remainder set of F w.r.t. A, noted by bremset(.F, .A). Obviously, R is reduced w.r.t. A.Definition 3 We call be t-Macaulay polynomial systems of F^h (w.r.t. (?)), and F_t*^h be t-Macaulay polynomial systems of F (w.r.t. X ).Definition 4 Let F_2t be Macaulay polynomial systems of F w.r.t. X₂ and C be block-ascending series. We call C be t-block-characteristic sets of F (w.r.t. X₂), if bremset(F_2t,C,X) =(?) and Zero(F) (?) Zero(C).Definition 5 Let C be t-block-characteristic sets of F w.r.t. X₂, C₂ = C∩K[X₂], andC₁ = C\C₂. If Zero(C₁^h/I_c^h) (?)Ï€(Zero(F^h)), then call C be block-characteristic sets of F(w.r.t. X₂).Then we can get the theorem of zeros decomposition.Theorem 1 Let F be m-homogeneous, then there exists a block-characteristic sets C_j and C_j1 = C_j∩K[X₁] s.t.Zero(F) =∪_jZero(C_j/I_Cj),∪_jZero(C_j1^h/I_cj^h)(?)Ï€(Zero(F^h))We can block-solve every C_j. Thus, we can reduce the problem of product space Kⁿ¹Ã—Kⁿ² to some smaller problems in two subspaces.We combine factorizing the polynomials with the zeros decomposition theorem, then we get a new form of the above theorem.Theorem 2 Let F can not be factorized, then there exist block-ascending A_j which can not be factorized s.t.Zero(F) =∪_jZero(A_j/I_Aj),∪_jZero(A_j1^h/I_Aj^h)(?)Ï€(Zero(F^h))For enhancing the efficient of computation, we point out weak reduced. Only by substituting weak reduced and weak remainder for reduced and remainder, we can get zeros decomposition about weak block-ascending series.Theorem 3 Let F be 2-homogeneous, then there exists a set consisting of some weak block-ascending series C_j s.t.Zero(F) =∪_jZero(C_j/I_cj),∪_jZero(C_j1^h/I_cj^h (?)Ï€(Zero(F^h))For m-homogeneous systems, We can let F_i (?) K[X₁,..., X_i] be 2-homogeneous for every i, which variables can be divided to [X₁,... ,X_i-1] and X_i. Then we can get the zeros decomposition by using above zeros decomposition theorem iteratively.Theorem 4 Let F be m-homogeneous, then there exists a set consisting of block-characteristic sets C_j s.t.Zero(F) =∪_jZevo(C_j/I_cj), Zero(C_ji^h∪...∪C_j1^h/(I_cjm^h... I_cj2^h)) (?)Ï€_i(Zero(F^h))Secondly, we consider the Lazard's resultant method, and let m = 1 first. Definition 6 We call MS_t = {(?)^α:|α| = t} which monomials list according as decreasing order be t-monomials set of (?). Let F_<sup>h be t-Macaulay polynomial systems of F^h, we call the coefficient matrix M-t(F^h) of F_t^h under MS_t be t-Macaulay matrix of F^h. Let M_t' = GE(M_t(F^h)), then we call the polynomial systems H of M_t^' under MSt be t-reduced Macaulay polynomial systems of F^h.Lazard gives the upper bound degree of Grobner bases of F w.r.t degree-reverse-lex order, which is the Macaulay number D of F. Then, we can get the Grobner bases by well arranged bases.Theorem 5 Let G be D-reduced Macaulay polynomial systems of F, then G_* be Grobner bases of F w.r.t degree-reverse-lex order.But the bases is not triangular. We present a resultant elimination, which can block-triangularize the m-homogeneous systems.We start by 2-homogeneous. Let D—(D₂, D₁) be Macaulay number of F^h, H be D-reduced Macaulay polynomial systems of F^h, H_1*= H_*∩K[X₁] and H_2*=H_*\H_1*. Let have zeros at infinity } (?) Kⁿ¹Theorem 6 LetÏ€₁ : Kⁿ¹Ã—Kⁿ²â†’Kⁿ¹ be projective map, thenV(H_1*=V₁'∪V₂',V₁'-Ï€₁(V(F))Thus, we get the block-triangular polynomial systems H_*, and then we can get the values about X₁ of the zeros of F = 0 by solving H_1* = 0. Substituting the values to H_2*, then we get the corresponding values about X₂. Finally we get all the solutions of F = 0 by combining the two parts of values.We have the following estimate about D.Proposition 2 Let F (?) K[X] be 2-homogeneous and d_i = max{deg_i(f) : f∈F}, i = 1,2. ThenD₁=O((2e)ⁿ²d₁d₂^m2), D₂ =O(n₂d₂) Then the upper bound degree of Grobner bases w.r.t. lex order of H₁ and H₂ are O((2e)ⁿ²²ⁿ¹d₁²ⁿ¹d₂ⁿ²²ⁿ¹) and (d₂²ⁿ²). We know that the upper bound degree of Grobner bases of F w.r.t lex order is O((d₁+d₂)²ⁿ¹⁺ⁿ²). Obviousely, the complexity of reducing the systems to block-triangular system and computing the Grobner bases w.r.t. lex order respectively is fewer then directly computing the Grobner bases of F w.r.t. lex order.For m-homogeneous systems , we can suppose F_i (?) K[X₁,... ,X_i] be 2-homogeneous for each i, which variables can be divided to [X₁,..., X_i-1] and X_i. Then we can get a block-triangular systems H = {H₁, ... ,H_m} by using theorem 6 iteratively, which H_i(?)K[X₁..., X_i]. Let V_i = V(H₁∪...∪H_i) (?) Kⁿ¹Ã—...×Kⁿⁱ, i = 1,..., m - 1, andhave zeros at infinity}Theorem 7 LetÏ€_i: Kⁿ¹Ã—...×K^n_m→Kⁿ¹Ã—...×Kⁿⁱ be projective map, thenV_i=V_i,1∪V_i,2,V_i,1=Ï€_i(V(F))Thus, we can block-solve F = 0 though solving H₁= 0, ... , H_m = 0 one by one.