Re: Solving overdetermined equations

From: Daniel Lichtblau (danl_at_wolfram.com)
Date: 10/08/04 

Date: 8 Oct 2004 08:07:21 -0700

Martin Rubey <mrstatex@yahoo.de> wrote in message news:<87is9mzamj.fsf@univie.ac.at>...
> This looks interesting. So here you go, two examples. Please excuse the format,
> but I don't know how to do it better.
>
> The first one does not have a (nontrivial) solution, I suppose that the second
> one doesn't have one either, but I did not check.
>
> I don't understand the aproach of ALIAS well enough, is there a compilation
> process for every instance of a problem, or does it compile once, so that I can
> test some 20 families of three polynomials each then?
>
> Thanks again,
>
> Martin
> [...]

I rewrote the polynomials in syntax that most math programs will
accept (caret instead of double-asterisk for exponents). Also I
replaced 'A' by 'a2' for no reason in particular.

polys = {-30*a2^10 + 96*a2^11 - 108*a2^12 + 48*a2^13 - 6*a2^14 +
  (1200*a2^9 - 3648*a2^10 + 4104*a2^11 - 1920*a2^12 + 264*a2^13)*a21 +
  (-21450*a2^8 + 61920*a2^9 - 70308*a2^10 + 35040*a2^11 -
5346*a2^12)*a21^2 +
  (225660*a2^7 - 619392*a2^8 + 718416*a2^9 - 386496*a2^10 +
66036*a2^11)*a21^3 +
  (-1547490*a2^6 + 4055424*a2^7 - 4879332*a2^8 + 2875824*a2^9 -
555882*a2^10)*
   a21^4 + (7228920*a2^5 - 18243072*a2^6 + 23219784*a2^7 -
15248448*a2^8 +
    3373344*a2^9)*a21^5 + (-23299110*a2^4 + 57524736*a2^5 -
79438428*a2^6 +
    59292096*a2^7 - 15218958*a2^8)*a21^6 +
  (51166620*a2^3 - 127150080*a2^4 + 196982496*a2^5 - 171232512*a2^6 +
    51856836*a2^7)*a21^7 + (-73282320*a2^2 + 193112064*a2^3 -
351587952*a2^4 +
    367367424*a2^5 - 134108352*a2^6)*a21^8 +
  (61819200*a2 - 192012288*a2^2 + 440774784*a2^3 - 578423808*a2^4 +
    261963744*a2^5)*a21^9 + (-23328000 + 112558080*a2 - 368629056*a2^2
+
    649810944*a2^3 - 380496864*a2^4)*a21^10 +
  (-29491200 + 184757760*a2 - 493350912*a2^2 + 398525760*a2^3)*a21^11
+
  (-41990400 + 226934784*a2 - 284560128*a2^2)*a21^12 +
  (-47775744 + 124001280*a2)*a21^13 - 24883200*a21^14,
 -60*a2^10 + 240*a2^12 - 360*a2^13 + 180*a2^14 - 24*a2^15 +
  (2400*a2^9 - 8160*a2^11 + 12240*a2^12 - 6480*a2^13 + 960*a2^14)*a21
+
  (-42900*a2^8 + 121920*a2^10 - 185040*a2^11 + 105300*a2^12 -
17520*a2^13)*a21^2 +
  (451320*a2^7 - 1054080*a2^9 + 1644480*a2^10 - 1022760*a2^11 +
193248*a2^12)*
   a21^3 + (-3094980*a2^6 + 5847840*a2^8 - 9572760*a2^9 +
6625800*a2^10 -
    1438632*a2^11)*a21^4 + (14457840*a2^5 - 21844800*a2^7 +
38500560*a2^8 -
    30248640*a2^9 + 7644960*a2^10)*a21^5 +
  (-46598220*a2^4 + 56180160*a2^6 - 109980000*a2^7 + 100231560*a2^8 -
    29911968*a2^9)*a21^6 + (102333240*a2^3 - 100149120*a2^5 +
225872640*a2^6 -
    244626480*a2^7 + 87615936*a2^8)*a21^7 +
  (-146564640*a2^2 + 123047280*a2^4 - 333670680*a2^5 + 441555300*a2^6
-
    193452264*a2^7)*a21^8 + (123638400*a2 - 102006240*a2^3 +
350613360*a2^4 -
    586419120*a2^5 + 321637632*a2^6)*a21^9 +
  (-46656000 + 54418560*a2^2 - 255214800*a2^3 + 564234660*a2^4 -
399148656*a2^5)*
   a21^10 + (-16857600*a2 + 122160960*a2^2 - 381727080*a2^3 +
363048288*a2^4)*
   a21^11 + (2304000 - 34554600*a2 + 171888480*a2^2 -
234380376*a2^3)*a21^12 +
  (4374000 - 46189440*a2 + 101484576*a2^2)*a21^13 +
  (5598720 - 26386560*a2)*a21^14 + 3110400*a21^15,
 -66*a2^10 + 480*a2^13 - 810*a2^14 + 432*a2^15 - 60*a2^16 +
  (2640*a2^9 - 13440*a2^12 + 22680*a2^13 - 12960*a2^14 +
2040*a2^15)*a21 +
  (-47190*a2^8 + 156000*a2^11 - 268110*a2^12 + 168480*a2^13 -
30660*a2^14)*a21^2 +
  (496452*a2^7 - 960960*a2^10 + 1735020*a2^11 - 1240704*a2^12 +
267360*a2^13)*
   a21^3 + (-3404478*a2^6 + 3313920*a2^9 - 6641190*a2^10 +
5664816*a2^11 -
    1490820*a2^12)*a21^4 + (15903624*a2^5 - 6067200*a2^8 +
15046560*a2^9 -
    16430688*a2^10 + 5512920*a2^11)*a21^5 +
  (-51258042*a2^4 + 4608000*a2^7 - 18698850*a2^8 + 29579904*a2^9 -
13520700*a2^10)*
   a21^6 + (112566564*a2^3 + 9841500*a2^7 - 30233088*a2^8 +
21209040*a2^9)*a21^7 +
  (-161221104*a2^2 + 13436928*a2^7 - 19310400*a2^8)*a21^8 +
  (136002240*a2 + 7776000*a2^7)*a21^9 - 51321600*a21^10,
 240*a2^15 - 600*a2^16 + 960*a2^17 - 720*a2^18 + 240*a2^19 - 24*a2^20
+
  (-15600*a2^14 + 37200*a2^15 - 58560*a2^16 + 44640*a2^17 -
15600*a2^18 +
    1680*a2^19)*a21 + (470400*a2^13 - 1068000*a2^14 + 1658880*a2^15 -
    1292400*a2^16 + 476160*a2^17 - 55440*a2^18)*a21^2 +
  (-8729280*a2^12 + 18841200*a2^13 - 28984320*a2^14 + 23221440*a2^15 -
    9072960*a2^16 + 1146768*a2^17)*a21^3 +
  (111494880*a2^11 - 228534600*a2^12 + 349856640*a2^13 -
290239920*a2^14 +
    121006560*a2^15 - 16675008*a2^16)*a21^4 +
  (-1038296160*a2^10 + 2020315200*a2^11 - 3096316800*a2^12 +
2680380000*a2^13 -
    1200340320*a2^14 + 181179504*a2^15)*a21^5 +
  (7283239680*a2^9 - 13461148800*a2^10 + 20808345600*a2^11 -
18958859280*a2^12 +
    9184757760*a2^13 - 1526251248*a2^14)*a21^6 +
  (-39188417280*a2^8 + 68936313600*a2^9 - 108479116800*a2^10 +
    105040379520*a2^11 - 55481241600*a2^12 + 10207299888*a2^13)*a21^7
+
  (163081291440*a2^7 - 274154284800*a2^8 + 444228408000*a2^9 -
    462219252480*a2^10 + 268502785200*a2^11 - 55041797160*a2^12)*a21^8
+
  (-524914190640*a2^6 + 849320371200*a2^7 - 1437436056000*a2^8 +
    1627834867200*a2^9 - 1050311722800*a2^10 +
241674404160*a2^11)*a21^9 +
  (1296211057920*a2^5 - 2042481408000*a2^6 + 3676192181760*a2^7 -
    4600000581120*a2^8 + 3334830714240*a2^9 -
868746336384*a2^10)*a21^10 +
  (-2411698069440*a2^4 + 3772377292800*a2^5 - 7390505180160*a2^6 +
    10407395543040*a2^7 - 8594951361600*a2^8 +
2561189840640*a2^9)*a21^11 +
  (3272898493440*a2^3 - 5245560883200*a2^4 + 11539455713280*a2^5 -
    18715732992000*a2^6 + 17908700655360*a2^7 -
6181873386240*a2^8)*a21^12 +
  (-3058655385600*a2^2 + 5308816588800*a2^3 - 13704035051520*a2^4 +
    26393756221440*a2^5 - 29905506274560*a2^6 +
12149702611968*a2^7)*a21^13 +
  (1760237568000*a2 - 3688292352000*a2^2 + 11957502320640*a2^3 -
    28552491601920*a2^4 + 39441785180160*a2^5 -
19254190123008*a2^6)*a21^14 +
  (-470292480000 + 1571880960000*a2 - 7225782681600*a2^2 +
22866665472000*a2^3 -
    40151145323520*a2^4 + 24225748475904*a2^5)*a21^15 +
  (-309657600000 + 2700822528000*a2 - 12769023098880*a2^2 +
    30423790632960*a2^3 - 23633940768768*a2^4)*a21^16 +
  (-470292480000 + 4437411102720*a2 - 16151320166400*a2^2 +
17230218559488*a2^3)*
   a21^17 + (-722369249280 + 5358845952000*a2 -
8831585157120*a2^2)*a21^18 +
  (-836075520000 + 2837879193600*a2)*a21^19 - 429981696000*a21^20,
 264*a2^15 - 1800*a2^17 + 3840*a2^18 - 3240*a2^19 + 1152*a2^20 -
120*a2^21 +
  (-17160*a2^14 + 102600*a2^16 - 215040*a2^17 + 184680*a2^18 -
69120*a2^19 +
    7800*a2^20)*a21 + (517440*a2^13 - 2683800*a2^15 + 5544960*a2^16 -
    4879440*a2^17 + 1935360*a2^18 - 237720*a2^19)*a21^2 +
  (-9602208*a2^12 + 42708600*a2^14 - 87383040*a2^15 + 79386480*a2^16 -
    33606144*a2^17 + 4515000*a2^18)*a21^3 +
  (122644368*a2^11 - 462142800*a2^13 + 942044160*a2^14 -
891100440*a2^15 +
    405609984*a2^16 - 59911320*a2^17)*a21^4 +
  (-1142125776*a2^10 + 3600644400*a2^12 - 7369405440*a2^13 +
7327295640*a2^14 -
    3614492160*a2^15 + 590165880*a2^16)*a21^5 +
  (8011563648*a2^9 - 20866964400*a2^11 + 43304079360*a2^12 -
45737537760*a2^13 +
    24656246784*a2^14 - 4476350520*a2^15)*a21^6 +
  (-43107259008*a2^8 + 91658444400*a2^10 - 195228810240*a2^11 +
    221609701440*a2^12 - 131730430464*a2^13 + 26762120280*a2^14)*a21^7
+
  (179389420584*a2^7 - 308208191400*a2^9 + 683857205760*a2^10 -
    845124188760*a2^11 + 559342215936*a2^12 -
128053935720*a2^13)*a21^8 +
  (-577405609704*a2^6 + 796200431400*a2^8 - 1873454269440*a2^9 +
    2557023004440*a2^10 - 1904462148096*a2^11 +
495170807880*a2^12)*a21^9 +
  (1425832163712*a2^5 - 1577541036600*a2^7 + 4020722903040*a2^8 -
    6158783503440*a2^9 + 5223345260544*a2^10 -
1556013804360*a2^11)*a21^10 +
  (-2652867876384*a2^4 + 2381348251800*a2^6 - 6741057745920*a2^7 +
    11800900465200*a2^8 - 11550295789056*a2^9 +
3981973811880*a2^10)*a21^11 +
  (3600188342784*a2^3 - 2704922985600*a2^5 + 8762528609280*a2^6 -
    17905351582440*a2^7 + 20540197817856*a2^8 -
8291201719560*a2^9)*a21^12 +
  (-3364520924160*a2^2 + 2265197032800*a2^4 - 8713398942720*a2^5 +
    21318266701800*a2^6 - 29196404716032*a2^7 +
13991736602280*a2^8)*a21^13 +
  (1936261324800*a2 - 1352637273600*a2^3 + 6486521057280*a2^4 -
    19625398035840*a2^5 + 32831870994432*a2^6 -
18999078057960*a2^7)*a21^14 +
  (-517321728000 + 543821184000*a2^2 - 3491435197440*a2^3 +
    13653978827040*a2^4 - 28751031553536*a2^5 +
20527709142600*a2^6)*a21^15 +
  (-131742720000*a2 + 1281131769600*a2^2 - 6926014149120*a2^3 +
    19146536479872*a2^4 - 17358772556160*a2^5)*a21^16 +
  (14515200000 - 286374528000*a2 + 2412499645440*a2^2 -
9346960852992*a2^3 +
    11211772788000*a2^4)*a21^17 + (29393280000 - 515171819520*a2 +
    3148207534080*a2^2 - 5328741634560*a2^3)*a21^18 +
  (50791587840 - 652736102400*a2 + 1753164518400*a2^2)*a21^19 +
  (62705664000 - 356078592000*a2)*a21^20 + 33592320000*a21^21,
 288*a2^15 - 4200*a2^18 + 10080*a2^19 - 9072*a2^20 + 3360*a2^21 -
360*a2^22 +
  (-18720*a2^14 + 210000*a2^17 - 493920*a2^18 + 453600*a2^19 -
178080*a2^20 +
    20880*a2^21)*a21 + (564480*a2^13 - 4704000*a2^16 + 10886400*a2^17
-
    10296720*a2^18 + 4327680*a2^19 - 559440*a2^20)*a21^2 +
  (-10475136*a2^12 + 62168400*a2^15 - 142450560*a2^16 +
140361984*a2^17 -
    63866880*a2^18 + 9177840*a2^19)*a21^3 +
  (133793856*a2^11 - 536873400*a2^14 + 1229457600*a2^15 -
1280122704*a2^16 +
    638729280*a2^17 - 102997440*a2^18)*a21^4 +
  (-1245955392*a2^10 + 3165775200*a2^13 - 7348501440*a2^14 +
8231515488*a2^15 -
    4572187200*a2^16 + 836462160*a2^17)*a21^5 +
  (8739887616*a2^9 - 12909842400*a2^12 + 31037852160*a2^13 -
38279276784*a2^14 +
    24104855040*a2^15 - 5069624400*a2^16)*a21^6 +
  (-47026100736*a2^8 + 35952806400*a2^11 - 92643264000*a2^12 +
    129754021824*a2^13 - 94780842240*a2^14 + 23295255120*a2^15)*a21^7
+
  (195697549728*a2^7 - 65444736000*a2^10 + 191530694880*a2^11 -
    318277294272*a2^12 + 277993191840*a2^13 - 81555151320*a2^14)*a21^8
+
  (-629897028768*a2^6 + 70318080000*a2^9 - 261245023200*a2^10 +
    551135757312*a2^11 - 600770046240*a2^12 +
216485226720*a2^13)*a21^9 +
  (1555453269504*a2^5 - 33868800000*a2^8 + 211631616000*a2^9 -
    639691831296*a2^10 + 929959349760*a2^11 -
428919999840*a2^12)*a21^10 +
  (-2894037683328*a2^4 - 77157360000*a2^8 + 446965972992*a2^9 -
    976539110400*a2^10 + 615107105280*a2^11)*a21^11 +
  (3927478192128*a2^3 - 142216445952*a2^8 + 623572992000*a2^9 -
    603598003200*a2^10)*a21^12 + (-3670386462720*a2^2 -
182891520000*a2^8 +
    362797056000*a2^9)*a21^13 + (2112285081600*a2 -
100776960000*a2^8)*a21^14 -
  564350976000*a21^15};

set1 = Take[polys,3];
set2 = Drop[polys,3];

Since you wish to avoid solutions where either variable is zero, you
can augment the system with a polynomial a1*a2*r - 1 ('r' for
"reciprocal"). I show a few Mathematica computations below. These were
run on a 2.8 MHz machine, I believe.

The first two indicate that, modulo a certain 9 digit prime, there are
no nontrivial solutions.

In[6]:= Timing[gb1prime = GroebnerBasis[Append[set1,a1*a2*r-1],
   MonomialOrder->DegreeReverseLexicographic,
   Sort->True, Modulus->Prime[11111111]]]
Out[6]= {0.52 Second, {1}}

In[7]:= Timing[gb2prime = GroebnerBasis[Append[set2,a1*a2*r-1],
   MonomialOrder->DegreeReverseLexicographic,
   Sort->True, Modulus->Prime[11111111]]]
Out[7]= {2.8 Second, {1}}

Actually we can get an approximate nonmodular Groebner basis fairly
quickly if we use sufficient precision.

In[15]:= Timing[gb1approx =
Rationalize[GroebnerBasis[Append[set1,a1*a2*r-1],
   MonomialOrder->DegreeReverseLexicographic,
   Sort->True, CoefficientDomain->InexactNumbers[1000]]]]
Out[15]= {8.59 Second, {1}}

In[17]:= Timing[gb2approx =
Rationalize[GroebnerBasis[Append[set2,a1*a2*r-1],
   MonomialOrder->DegreeReverseLexicographic,
   Sort->True, CoefficientDomain->InexactNumbers[2000]]]]
Out[17]= {114.31 Second, {1}}

To get an exact Groebner basis I found it expedient to take two steps.
In the first I compute an exact basis for just the original
polynomials, and then augment with the extra one that forces nonzero
solutions. I show this below with set1. From what is seen above I
would expect the analogous computations for set2 to be feasible but
several times slower.

In[18]:= Timing[gb1partial = GroebnerBasis[set1,
   MonomialOrder->DegreeReverseLexicographic,
   Sort->True];]
Out[18]= {24.46 Second, Null}

In[19]:= Timing[gb1full = GroebnerBasis[Append[gb1partial,a1*a2*r-1],
   MonomialOrder->DegreeReverseLexicographic, Sort->True]]
Out[19]= {2.8 Second, {1}}

We showed above that there are no solutions wherein neither variable
is zero. If what you had intended was to allow either but not both
coordinates to vanish, then you can proceed from here by explicitly
setting a1 respectively a2 to zero and solving the resulting system
for the other.

Daniel Lichtblau
Wolfram Research

Relevant Pages

  • Re: Solving overdetermined equations
    ... I rewrote the polynomials in syntax that most math programs will ... Since you wish to avoid solutions where either variable is zero, ... To get an exact Groebner basis I found it expedient to take two steps. ...
    (sci.math.research)
  • Re: Possible flaw in the polynomial ring A[X] construction
    ... We can zero out the ... that the tuple was stretched to an infinite chain of zeroes goes ... which relies upon the ring definition to yield the polynomial form as ... comes at the expense that polynomials with real coefficients are ...
    (sci.math)
  • Re: Solving overdetermined equations
    ... >> Since you wish to avoid solutions where either variable is zero, ... >> no nontrivial solutions. ... nontrivial polynomials that ultimately are eliminated by later ones. ... Daniel Lichtblau ...
    (sci.math.symbolic)
  • Re: Groebner basis question.
    ... Groebner basis exceeds the original number of polynomials. ... same set of roots does not in general give you that the ideals ... You can view each generating polynomials as rewrite rule, ...
    (sci.math)
  • Polynomial root-finding
    ... the art" of certain polynomial root finders. ... I'm writing a paper about polynomials and the process of zero finding ... Needs a polynomial zero finder itself (matlab built in roots function). ...
    (sci.math.num-analysis)