From: "J. Maurice Rojas" Subject: Re: How many solutions does this system have? Date: Mon, 18 Oct 1999 11:31:42 +0800 Newsgroups: sci.math.research Dear Colleagues, In an earlier posting, Miroslav D Trajkovic asked for the number of solutions of the following system of equations. > Sum (a_ij*x^i*y^j) = 0 > Sum (b_ij*x^i*z^j) = 0 > Sum (c_ij*y^i*z^j) = 0 > > where all sums are over i and j, and i=0,1,2,3; j=0,1,2,3, and a,b,c are > real coefficients. Daniel Lichtblau and Bob Riley have since posted responses, using Grobner bases and Sylvester resultants, respectively. However, the number of real solutions seems to have been ignored. Here I post a direct solution in terms of mixed volumes, which form an important part of the theory of structured polynomial system solving. These techniques form an important alternative to Grobner basis algorithms, and have provably lower complexity bounds in many cases. Further details on the use of sparsity in polynomial system solving can be found in many sources, but for a brief glimpse, one can start with the the following three web-pages: http://www.cityu.edu.hk/ma/staff/rojas http://www-sop.inria.fr/saga/personnel/Ioannis.Emiris/index.html http://www-sop.inria.fr/saga/personnel/Bernard.Mourrain/index.html Implementations in C and Matlab can be found on these pages as well. To answer Mr. Trajkovic's question, recall a result of D. N. Bernshtein, published in the Russian journal Functional Analysis and its Applications in 1975: Theorem: The number of isolated complex solutions of a system of polynomial equations is at most the mixed volume of the Newton polytopes. Rather than give detailed definitions for all the terms above, let me first give the answer to Mr. Trajkovic's question. I will then illustrate the definitions above in the case of Mr. Trajkovic's example. I hope this helps. Best Wishes, Maurice --------------------------------------------------------------------- THE ANSWER: --------------------------------------------------------------------- The above system of equations has at most 54 isolated real solutions. Here, isolated means zero-dimensional as a component of the complex zero set. An upper bound of 54 (on the number of isolated complex solutions) follows immediately from Bernshtein's theorem above, and the mixed volume computation is detailed below. That this upper bound is actually attained for the number of real solutions follows easily from the following family of examples: f = (u1 + u2 x)(u3 + u4 x)(u5 + u6 x) (u7 + u8 y)(u9 + u10 y)(u11 + u12 y) g = (v1 + v2 x)(v3 + v4 x)(v5 + v6 x) (v7 + v8 z)(v9 + v10 z)(v11 + v12 z) h = (w1 + w2 y)(w3 + w4 y)(w5 + w6 y) (w7 + w8 z)(w9 + w10 z)(w11 + w12 z) The proof is also detailed below. ------------------------------------- THE DETAILS ------------------------------------- The Newton polytopes of Mr. Trajkovic's equations are simply the convex hulls of the sets of exponent vectors defined by the monomial terms. So the first equation gives us the rectangle [0,3] x [0,3] x {0} in R^3, which I've expressed as the product of two line segments and a point. Similarly, the other two equations have Newton polytopes [0,3] x {0} x [0,3] and {0} x [0,3] x [0,3]. As for the mixed volume in three dimensions, this function satisfies the following three properties: (1) M is symmetric, nonnegative, and (for polyhedra with integral vertices) integral. (2) If P and Q are parallel line segments, then M(P,Q,R)=0 for any three-dimensional polyhedron R. (3) M is multilinear with respect to scaling and Minkowski sum. The Minkowksi sum of two sets A and B is simply defined to be A+B:={ x+y | x in A, y in B}. In particular, each of our Newton polygons above is a scaled Minkowski sum of a point and two line segments of length one. So applying (3) to our example, we get M( [0,3] x [0,3] x {0} , [0,3] x {0} x [0,3] , [0,3] x [0,3] x {0} ) = 27 M( [0,1] x {0} x {0} , {0} x {0} x [0,1] , {0} x [0,1] x {0} ) + 27 M( {0} x [0,1] x {0} , [0,1] x {0} x {0} , {0} x {0} x [0,1] ) + ... where the other terms are mixed volumes of other triples of line segments. However, by property (2), the remaining terms are 0. So our upper bound is clear. As for why the family of examples stated above attains this upper bound, first note that for any constants {ui}, {vj}, {wk}, we get a polynomial system of the form specified by Mr. Trajkovic. Next, note that for any real {ui}, {vj}, {wk}, the family above has a solution if the product of ``x factors'' from f, the product of ``z factors'' from g, and the product of ``y factors'' from h, all vanish. This accounts for 27 roots. Also, the family above has a solution if the product of ``y factors'' from f, the product of ``x factors'' from g, and the product of ``z factors'' from h, all vanish. This accounts for another 27 roots. It is then easy to see that for GENERIC {ui}, {vj}, {wk}, NO other choice of vanishing products within f, g, and h leads to solutions. Indeed, any other combination of products leads to a degenerate linear system of equations. I should also point out that these sorts of product examples and product tricks were used by Tien Yien Li a few years ago in his papers on homotopy methods for solving polynomial systems. --------------------------------------------------------------------------- ============================================================================== From: Daniel Lichtblau Subject: Re: How many solutions does this system have? Date: Fri, 15 Oct 1999 19:32:40 +0000 Newsgroups: sci.math.num-analysis,sci.math.research,sci.math.symbolic Miroslav D Trajkovic wrote: > > Hi, > > I am trying to find oyt the number of solutions of the following system > with thre unknowns (x,y,z), > so far without any lack. Any help would be appreciated. > > Sum (a_ij*x^i*y^j) = 0 > Sum (b_ij*x^i*z^j) = 0 > Sum (c_ij*y^i*z^j) = 0 > > where all sums are over i and j, and i=0,1,2,3; j=0,1,2,3, and a,b,c are > real coefficients. > > Thanks a lot, > > Miroslav One way is to find the number of solutions for a "random" specialization, then invoke what is called the Shape Lemma or some variation thereof to assert that this is, with high probability, the generic number of roots (in C^3). We may do this using Mathematica as follows. In[1]:= polys = {Sum[a[i,j]*x^i*y^j, {i,0,3}, {j,0,3}], Sum[b[i,j]*y^i*z^j, {i,0,3}, {j,0,3}], Sum[c[i,j]*x^i*z^j, {i,0,3}, {j,0,3}]}; In[2]:= SeedRandom[1111]; In[3]:= InputForm[p2 = polys /. (a|b|c)[_,_] :> Random[Integer,{20,40}]] Out[3]//InputForm= {37 + 26*x + 34*x^2 + 23*x^3 + 39*y + 20*x*y + 21*x^2*y + 20*x^3*y + 38*y^2 + 26*x*y^2 + 21*x^2*y^2 + 20*x^3*y^2 + 38*y^3 + 31*x*y^3 + 20*x^2*y^3 + 30*x^3*y^3, 28 + 23*y + 40*y^2 + 30*y^3 + 21*z + 37*y*z + 37*y^2*z + 34*y^3*z + 36*z^2 + 23*y*z^2 + 30*y^2*z^2 + 33*y^3*z^2 + 26*z^3 + 33*y*z^3 + 24*y^2*z^3 + 31*y^3*z^3, 26 + 28*x + 25*x^2 + 22*x^3 + 22*z + 38*x*z + 24*x^2*z + 24*x^3*z + 29*z^2 + 25*x*z^2 + 35*x^2*z^2 + 26*x^3*z^2 + 38*z^3 + 35*x*z^3 + 34*x^2*z^3 + 32*x^3*z^3} In[4]:= Timing[solns = NSolve[p2, {x,y,z}];] Out[4]= {185.05 Second, Null} In[5]:= Length[solns] Out[5]= 54 One might not wish to trust a largely numerical algorithm for this task. Here is a second method (still subject to the probalistic Shape Lemma). We will form a Groebner basis for the specialized system and then find the size of the normal set. This gives the number of roots of the system (a good reference for the relevant theory is Cox, Little, and O'Shea, Using Algebraic Geometry). To do this we require all "head terms" from a Groebner basis computed with respect to any ordering. In[6]:= vars = {x,y,z}; In[7]:= torder = MonomialOrder->DegreeReverseLexicographic; In[8]:= Timing[gb = GroebnerBasis[p2, vars, torder];] Out[8]= {63.61 Second, Null} In[9]:= distpolys = First[Internal`DistributedTermsList[gb, vars, torder]]; In[10]:= InputForm[heds = Map[#[[1,1]]&, distpolys]] Out[10]//InputForm= {{4, 1, 0}, {5, 0, 0}, {0, 0, 6}, {0, 1, 5}, {1, 0, 5}, {0, 2, 4}, {1, 1, 4}, {2, 0, 4}, {0, 3, 3}, {1, 2, 3}, {2, 1, 3}, {3, 0, 3}, {0, 4, 2}, {1, 3, 2}, {2, 2, 2}, {3, 1, 2}, {4, 0, 2}, {0, 5, 1}, {1, 4, 1}, {2, 3, 1}, {3, 2, 1}, {0, 6, 0}, {1, 5, 0}, {2, 4, 0}, {3, 3, 0}} Now we get the "pure" terms, those in which only one nonzero exponent appears. We will use it to find those exponent vectors that are not reducible by the vectors of head terms shown above. I'll note that there are more efficient ways to do this but the code below is fairly concise and is adequate for the task at hand. In[11]:= pureterms = Select[heds, Max[#]===Apply[Plus,#]&] Out[11]= {{5, 0, 0}, {0, 0, 6}, {0, 6, 0}} In[12]:= maxes = Apply[Plus, pureterms]; In[13]:= nvars = Length[vars]; In[14]:= isUnder[t1_, t2_] := And[Evaluate[Apply[Sequence, Thread[t1<=t2]]]] In[15]:= noneBelow[tuple_, mixedexpons_] := Module[ {j, len=Length[mixedexpons]}, For[j=1, j<=len, j++, If [isUnder[mixedexpons[[j]], tuple], Return [False]]]; True ] In[16]:= normalSet[elist_List, maxes_, nvars_Integer] := Module[ {jj, indices, iterators, mixedexpons, heads}, mixedexpons = Select[elist, (Max[Apply[Sequence,#]]!=Plus[Apply[Sequence,#]])&]; indices = Array[jj, {nvars}]; iterators = Table[{indices[[j]], 0, maxes[[j]]-1}, {j, nvars}]; heads = Flatten[ Table[indices, Evaluate[Apply[Sequence,iterators]]], nvars-1]; Select[heads, noneBelow[#, mixedexpons]&] ] In[17]:= InputForm[nset = normalSet[heds, maxes, nvars]] Out[17]//InputForm= {{0, 0, 0}, {0, 0, 1}, {0, 0, 2}, {0, 0, 3}, {0, 0, 4}, {0, 0, 5}, {0, 1, 0}, {0, 1, 1}, {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 2, 0}, {0, 2, 1}, {0, 2, 2}, {0, 2, 3}, {0, 3, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 0}, {0, 4, 1}, {0, 5, 0}, {1, 0, 0}, {1, 0, 1}, {1, 0, 2}, {1, 0, 3}, {1, 0, 4}, {1, 1, 0}, {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 0}, {1, 2, 1}, {1, 2, 2}, {1, 3, 0}, {1, 3, 1}, {1, 4, 0}, {2, 0, 0}, {2, 0, 1}, {2, 0, 2}, {2, 0, 3}, {2, 1, 0}, {2, 1, 1}, {2, 1, 2}, {2, 2, 0}, {2, 2, 1}, {2, 3, 0}, {3, 0, 0}, {3, 0, 1}, {3, 0, 2}, {3, 1, 0}, {3, 1, 1}, {3, 2, 0}, {4, 0, 0}, {4, 0, 1}} In[19]:= Length[nset] Out[19]= 54 So again we get 54. Daniel Lichtblau Wolfram Research