The Domino Method Applied to Solving a Nonlinear Integer System of Nine Equations from the Literature, Second Edition

Jsun Yui Wong

Using the following nonlinear system representing a problem of robotics [2, p. 347] and coming from Bellido [2, p. 348; 3, p. I-14], the following computer program is an illustration of the algorithm merging the ideas on page 251-256 of Miller [1] and the ideas in the falling domino principle, domino effect, domino phenomenon , and domino theory.  It is important to note that the domino effect is a chain reaction.  X(2) of line 504, X(4) of line 611, and X(5) of line 612 are like the first domino, the second domino, and the third domino, respectively, of the falling domino principle.   X(2) of line 504 has been chosen as the first domino because it appears that X(2) of line 504 can be knocked down as easily as any other choice.  Using the latest number for X(1) and the latest number for X(3) from the lines preceding line 503, the right-hand side of line 504, (-X(1)^2-X(3)^2+12*X(1)+68)^.5, can push the first domino/X(2) down to its stationary-position/resolution/solution/optimal-value/stationary-value.  After that, that X(1), X(2) and X(3) have already been used in line 504 can help the right-hand side of line 611 knock down the second domino, X(4). Similarly, that X(1),  X(3), X(4), X(6), X(7), and X(8) have been used in line 504 and line 611 can help the right-hand side of line 612 knock down the third domino, X(5).  After line 612, there is a specific number for each of X(1), X(2), X(3), X(4), X(5), X(6), X(7), X(8), and X(9).  These nine values are a solution to the nonlinear system of equations if these numbers make each of  P(2), P(3), P(4), P(5), P(6), and P(7) close to zero.  In this paper only integer solutions are of interest.

X(1)^2+X(2)^2+X(3)^2-12*X(1)-68=0
X(4)^2+X(5)^2+X(6)^2-12*X(5)-68=0
X(7)^2+X(8)^2+X(9)^2-24*X(8)-12*X(9)+100=0
X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52=0
X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64=0
X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32=0
2*X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7)-X(9)+18=0
X(1)+X(2)+2*X(3)+2*X(4)+2*X(6)-2*X(7)+X(8)-X(9)-38=0
X(1)+X(3)-2*X(4)+X(5)-X(6)+2*X(7)-2*X(8)+8=0

The nonlinear system above is from Bellido [2, p.348; 3, p.I-14].  These nine equations are used in line 503 through line 677.  The following computer program is looking for integer solutions only.

0 REM DEFDBL A-Z
2 DEFINT I,J,K,X,A
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(111)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
22 RJJJJ=RND
23 RJJJJJ=RND
61 FOR KLQ=1 TO 9
62 A(KLQ)=RND*50
63 NEXT KLQ
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 9
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
181 J=1+FIX(RND*9)
183 R=(1-RND*2)*A(J)
191 IF RND<.14 THEN X(J)=A(J)+RND^5*R ELSE IF RND<.17 THEN X(J)=A(J)+R ELSE IF RND<.2 THEN X(J)=A(J)+RND*R ELSE IF RND<.25 THEN X(J)=A(J)+RND^2*R ELSE IF RND<.33 THEN X(J)=A(J)+RND^3*R ELSE IF RND<.5 THEN X(J)=A(J)+RND^4*R ELSE X(J)=INT(X(J))
503 IF  ( -X(1)^2-X(3)^2       +12*X(1)         +68)<0 THEN 1670
504 X(2)= ( -X(1)^2-X(3)^2       +12*X(1)         +68)^.5
511 IF RND<.5 THEN X(2)=X(2) ELSE X(2)=-X(2)
611 X(4)=(-X(1)-X(2)-2*X(3)-2*X(6)+2*X(7)  -X(8) +X(9)+38       )/2
612 X(5)=   -X(1)-X(3)+2*X(4)+X(6)-2*X(7)+2*X(8)      -8
616 P(2)= X(4)^2 +X(5)^2+X(6)^2       -12*X(5)         -68
617 P(3)= X(7)^2 +X(8)^2+X(9)^2       -24*X(8)-12*X(9) +100
622 P(4)=    X(1)*X(4)+X(2)*X(5)+X(3)*X(6)-6*X(1)-6*X(5)-52
624 P(5)=    X(1)*X(7)+X(2)*X(8)+X(3)*X(9)-6*X(1)-12*X(8)-6*X(9)+64
626 P(6)=    X(4)*X(7)+X(5)*X(8)+X(6)*X(9)-6*X(5)-12*X(8)-6*X(9)+32
628 P(7)= 2* X(2)+2*X(3)-X(4)-X(5)-2*X(6)-X(7) -X(9)+18
666 REM     P(2)= X(4)^2 +X(5)^2+X(6)^2       -12*X(5)         -68
677 REM    P(3)= X(7)^2 +X(8)^2+X(9)^2       -24*X(8)-12*X(9) +100
1450 P=-ABS(P(2)) -ABS(P(3))-ABS(P(4)) -ABS(   P(5))-ABS(P(6)) -ABS(P(7))
1451 IF P<=M THEN 1670
1452 M=P
1453 PP(2)=P(2):PP(3)=P(3):PP(4)=P(4)
1454 FOR KLX=1 TO 9
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1890   IF M>-7 THEN 1928 ELSE 1999
1928 PRINT A(1),A(2),A(3),A(4),A(5)
1929 PRINT A(6),A(7),A(8),A(9),M,JJJJ
1999 NEXT JJJJ

This BASIC computer program was run with Microsoft’s GW BASIC 3.11 interpreter. The best solutions through JJJJ=32000 are presented below.  What immediately follows is a hand copy from the computer monitor.

12   8   2   8   12
2   8   16   6   0
-24771

4   0   10   0   4
10   0   8   14   0
-22316

12   8   2   8   12
2   8   16   6   0
26688
.
The solution vector shown above at JJJJ=-22316 also occurred at JJJJ=-20081, -14468, -11546, -4779, -2843, -2053, 18, 882, 3347,  12476, 12476, 14446, 15379, 17351, 19106, 20717, 21963, 22559, and 25393.

On a personal computer with an Intel 2.66 chip and the IBM basica/D interpreter, version GW BASIC 3.11, the running time for the whole program from JJJJ=-32000 through JJJJ=32000 was one hour plus half an hour.

In general, a usable solution for another application of this algorithm may come early, late, or worse.  To alleviate this shortcoming, one can simultaneously run independent computers with different line 126s.  Here is one example: 126 IMAR=10+FIX(RND*1000), 126 IMAR=10+FIX(RND*1200), and 126 IMAR=10+FIX(RND*1500).  This multicomputer approach can considerably reduce the length of time to obtain one usable solution.

References

[1] Ronald E. Miller, Optimization: Foundations and Applications.  New York: John Wiley and Sons, Inc., 2000.
[2] A.-M. Bellido.  Construction of iteration functions for the simultaneous computation of the solutions of equations and algebaric systems.  Numerical Algorithms 6(1994) 317-351.
[3] A.-M. Bellido.  “Construction of iteration functions for the simultaneous computation of the solutions of equations and algebaric systems,” Seminaire d’ANALYSE NUMEROQUE, Annee 1991-1992, PP. i-1 to i-16.  Universite Paul Sabatier de Toulouse, U.F.R. Mathematiques, Informatique, Gestion.
[4] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.