Re: Solving overdetermined equations
From: Daniel Lichtblau (danl_at_wolfram.com)
Date: 10/08/04
- Next message: Chakravarthi: "Re: a combinatorics proof needed"
- Previous message: steve fisk: "determinant inequality"
- In reply to: Martin Rubey: "Re: Solving overdetermined equations"
- Next in thread: Carlos Felippa: "Re: Solving overdetermined equations"
- Messages sorted by: [ date ] [ thread ]
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
- Next message: Chakravarthi: "Re: a combinatorics proof needed"
- Previous message: steve fisk: "determinant inequality"
- In reply to: Martin Rubey: "Re: Solving overdetermined equations"
- Next in thread: Carlos Felippa: "Re: Solving overdetermined equations"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
