 Open Access
 Total Downloads : 273
 Authors : Bassi, I. G, Abdullahi Mohammed, Okechukwu C. E
 Paper ID : IJERTV2IS80394
 Volume & Issue : Volume 02, Issue 08 (August 2013)
 Published (First Online): 21082013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Analysis Of Solving Polynomial Equations Using Homotopy Continuation Method
1 Bassi, I. G . , 2 Abdullahi Mohammed , 3 Okechukwu C. E.
1,2,&3Department of Maths/Stat, University of Maiduguri, Nigeria
Keywords: Polynomial homotopy continuation (phc), Newtons method, The Legendre Polynomial, Chebychevs Polynomial, The imbedding method
ABSTRACT
The Newtons method was used to compute the root of a polynomial equation and then compared with the homotopy continuation method. The imbedding method has the advantages of producing solutions over a large range of the independent variable, thereby giving a complete description of the solution behaviour and is use as a tool in overcoming the local convergence of iterative processes. The imbedding methods may be considered as a possibility to widen the domain of convergence that is providing all the isolated real roots of a polynomial equation.
INTRODUCTION
The necessity of solving nonlinear equation often arises in simulating and designing a chemical
plant or optimizing a process. When f(x) = 0 where
f : Rn Rn
is a nonlinear equation, we
want to find the solution of f(x). The Newtons method applied to nonlinear equation of the form f(x) = 0 in general will only converge if the iteration is started near a root of the equation. (Kuno and Seader, 1988) said that, Newtons method is locally convergent. In addition, the method is designed to locate, at best, just one root even though multiple solutions may exist. This is the major disadvantage.
The imbedding method or continuation methods are rapidly being applied to numerous problems of such kind. A solution method for nonlinear equation that is globally convergent from any starting point is the homotopy continuation method. The method has advantages of
producing solution over a large range of independent variables, giving a complete description of the solution behavior and a substantial improvement to Newtons and other similar methods in terms of global convergence. This method is based on the homotopy concept in algebraic topology.
The method, does not solve the nonlinear equation directly, but gradually reaches a root by beginning from a starting point which satisfies the second nonlinear equation. Both equations are embedded or homotoped into a homotopy function. Thus, if f(x) is the nonlinear equation to be solved and g(x) is a second simpler nonlinear equation of same degree with f(x), the homotopy function might be constructed as
H(x, t) tf(x) + (1 t)g(x) = 0
Where t is a scalar homotopy parameter which is gradually varied from 0 to 1 as the path is tracked from starting point to a solution.
Finding roots fails to give a correct solution to a nonlinear algebraic equation unless a good guess is chosen. Difficulty in finding a suitable initial guess is avoided by using homotopy methods such as fixed point and Newtons homotopy methods.
AIM AND OBJECTIVES
The aim of this research is to use homotopy continuation method to solve polynomial equations and has the following objectives:

Applying the Newtons method in solving polynomial equation;

Using the phc (polynomial homotopy continuation) software to solve polynomial equation;

Comparing solutions obtained from both Newtons method and the phc (polynomial homotopy continuation) software.
The homotopy continuation methods are rapidly being applied to numerous problems in engineering analysis like simulating and designing a chemical plant or optimizing a process, in
circuit board design, river routing, in motion path planning and also to mention but a few, in geographic information systems (GIS).
MAIN RESULT
We provide solutions to polynomial equations namely; the Legendre and Chebychevs polynomials using the Newtons method and the phc (generalpurpose solver for polynomial systems by Homotopy continuation).
THE LEGENDRE POLYNOMIAL
We shall use the Newtons method in finding the roots of the Legendre polynomial and also, the phc (polynomial homotopy continuation)
p(x)
1 (693×6 945×4 315×2 15)
48
Using the Newton's method:
p(x)=
1 (693×6 945×4 315×2 15)
48
p(x) 693 x5 945 x3 315 x
8 12 24
xn1 xn

p(x)
p(x)
693 x6 945 x4 315 x2 15
48 n 48 n 48 n 48
xn1 xn 693 945 315
n
n
8
x5
n
n
12
x3
24 xn
(14.4375×6 19.6875×4 6.5625×2 0.3125)
xn1 xn n n n
n n
n n
86.625×5 78.75×3 13.125x
n 0,1,…
for n 0,
(14.4375×6 19.6875×4 6.5625×2 0.3125)
x1 x0
0 0 0
0 0 0
0 0 0
86.625×5 78.75×3 13.125x
Take x0 0.75
14.4375(0.75)6 19.6875(0.75)4 6.5625(0.75)2 0.3125
x1 0.75
86.625(0.75)5 78.75(0.75)3 13.125(0.75)
x 0.75 (2.56956 6.22925 3.69 0.3125)
1 20.55652 33.22266 9.84375
x 0.75 (0.28219)
1 (2.82239)
x 0.75 0.28219
1 2.82239
x1 0.75 0.09998
st
st
x1 0.65002(1 iteration). for n 1,
(14.4375×6 19.6875×4 6.5625×2 0.3125)
x2 x1 1 1 1
1 1 1
1 1 1
86.625×5 78.75×3 13.125x
14.4375(0.65002)6 19.6875(0.65002)4 6.5625(0.65002)2 0.3125
x2 0.65002
86.625(0.65002)5 78.75(0.65002)3 13.125(0.65002)
x 0.65002 (1.08906 3.51477 2.77283 0.3125)
2 10.05256 21.62872 8.53151
x 0.65002 0.03462
2 3.04465
x2 0.65002 0.01137
nd
nd
x2 0.66139(2 iteration) Hence,0.66139 is a root of p(x).
Below is the solution of the legendre polynomial provided by the phc software:
1.44375000000000E+01*x^61.96875000000000E+01*x^4
+ 6.56250000000000E+00*x^23.12500000000000E01; ROOT COUNTS :
total degree : 6
HOMOTOPY PARAMETERS :
d : 16
k : 2
a : 4.24751288571780E01 9.05310081053234E01 t : 1.00000000000000E+00 0.00000000000000E+00
no projective transformation
****************** CURRENT CONTINUATION PARAMETERS ***************** GLOBAL MONITOR :

the condition of the homotopy 0

number of paths tracked simultaneously 1

maximum number of steps along a path 500

distance from target to start end game : 1.000E01

order of extrapolator in end game 0

maximum number of reruns 1
STEP CONTROL (PREDICTOR) : along path : end game 7: 8. type ( x:Sec,t:Rea ):( x:Sec,t:Rea ) : 0 0
9:10. minimum step size : 1.000E06 : 1.000E08
11:12. maximum step size : 1.000E01 : 1.000E02 13:14. reduction factor for step size : 7.000E01 : 5.000E01
15:16. expansion factor for step size : 1.250E+00 : 1.100E+00 17:18. expansion threshold : 1 1
PATH CLOSENESS (CORRECTOR) : along path : end game 19:20. maximum number of iterations : 4 4
21:22. relative precision for residuals : 1.000E09 : 1.000E11
23:24. absolute precision for residuals : 1.000E09 : 1.000E11 25:26. relative precision for corrections : 1.000E09 : 1.000E11 27:28. absolute precision for corrections : 1.000E09 : 1.000E11 SOLUTION TOLERANCES : along path : end game
29:30. inverse condition of Jacobian : 1.000E04 : 1.000E12 31:32. clustering of solutions : 1.000E04 : 1.000E12
33:34. solution at infinity : 1.000E+08 : .000E+12
******************************************************************** OUTPUT INFORMATION DURING CONTINUATION :
0 : no intermediate output information during continuation
TIMING INFORMATION for continuation
The elapsed time in seconds was 0.046000000 = 0h 0m 0s 46ms
THE SOLUTIONS : 6 1
===================================================================
solution 1 : start residual : 2.220E16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 9.32469514203152E01 1.36845553156720E48
== err : 2.348E17 = rco : 1.000E+00 = res : 2.220E16 = real regular ==
solution 2 : start residual : 0.000E+00 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 2.38619186083197E01 0.00000000000000E+00
== err : 0.000E+00 = rco : 1.000E+00 = res : 0.000E+00 = real regular == solution 3 : start residual : 5.551E17 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 6.61209386466265E01 1.55575381946529E60
== err : 1.769E17 = rco : 1.000E+00 = res : 5.551E17 = real regular == solution 4 : start residual : 2.220E16 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 9.32469514203152E01 1.36845553156720E48
== err : 2.348E17 = rco : 1.000E+00 = res : 2.220E16 = real regular == solution 5 : start residual : 0.000E+00 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 2.38619186083197E01 0.00000000000000E+00
== err : 0.000E+00 = rco : 1.000E+00 = res : 0.000E+00 = real regular == solution 6 : start residual : 5.551E17 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 6.61209386466265E01 1.55575381946529E60
== err : 1.769E17 = rco : 1.000E+00 = res : 5.551E17 = real regular ==
===========================================================================
A list of 6 solutions has been refined : Number of regular solutions : 6. Number of singular solutions : 0. Number of real solutions : 6. Number of complex solutions : 0.
Number of clustered solutions : 0. Number of solutions at infinity : 0. Number of failures : 0.
===========================================================================
Frequency tables for correction, residual, and condition numbers : FreqCorr : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 : 6
FreqResi : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 : 6
FreqCond :6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : 6
Small correction terms and residuals counted to the right. Well conditioned and distinct roots counted to the left.
TIMING INFORMATION for Root Refining
The elapsed time in seconds was 0.016000000 = 0h 0m 0s 16ms
TIMING INFORMATION for solving the polynomial system
The elapsed time in seconds was 63.180000000 = 0h 1m 3s180ms
PHC ran from 25 March 2013, 09:03:38 till 25 March 2013, 09:09:11. The total elapsed time is 333 seconds = 5 minutes 33 seconds.
CHEBYCHEVS POLYNOMIAL
We shall use the Newtons method in finding the roots of the chebychevs method and also, the phc (polynomial homotopy continuation)
T(x) 32×6 48×4 18×2 1 0. using Newton's method: T(x)=32×6 48×4 18×2 1 T(x) 192×5 192×3 36x
xn1 xn


T(xn ) T(xn )
(32×6 48×4 18×2 1)
xn1 xn n n n
n n n
n n n
192×5 192×3 36x
n 0,1,…
for n 0
(32×6 48×4 18×2 1)
x1 x0 0 n 0
0 0 0
0 0 0
192×5 192×3 36x
Take x0 0.6
x1 0.6
32(0.6)6 48(0.6)4 18(0.6)2 1
192(0.6)5 192(0.6)3 36(0.6)
x 0.6 (1.49299 6.2208 6.48 1)
1 14.92992 41.472 21.6
x 0.6 0.75219
1 4.94208
x1 0.6 0.1522
st
st
x1 0.7522(1 iteration) for n 0
(32×6 48×4 18×2 1)
x2 x1 1 1 1
1 1 1
1 1 1
192×5 192×3 36x
x 0.7522 (5.79629 15.36649 10.18449 1)
2 46.23468 81.71489 27.0792
x 0.7522 0.38571
2 8.40101
x2 0.7522 0.04591
nd
nd
x2 0.70629(2 iteration) Hence, 0.70629 is a root of T(x).
Below is the solution of the chebychevs polynomial provided by the phc software:
32*x^648*x^4+18*x^21; ROOT COUNTS :
total degree : 6
HOMOTOPY PARAMETERS : d : 16
k : 2
a : 8.10952587803780E01 5.85111869931172E01 t : 1.00000000000000E+00 0.00000000000000E+00
no projective transformation
****************** CURRENT CONTINUATION PARAMETERS ***************** GLOBAL MONITOR :

the condition of the homotopy 0

number of paths tracked simultaneously 1

maximum number of steps along a path 500

distance from target to start end game : 1.000E01

order of extrapolator in end game 0

maximum number of reruns 1
STEP CONTROL (PREDICTOR) : along path : end game 7: 8. type ( x:Sec,t:Rea ):( x:Sec,t:Rea ) : 0 0
9:10. minimum step size : 1.000E06 : 1.000E08
11:12. maximum step size : 1.000E01 : 1.000E02 13:14. reduction factor for step size : 7.000E01 : 5.000E01
15:16. expansion factor for step size : 1.250E+00 : 1.100E+00
17:18. expansion threshold : 1 1
PATH CLOSENESS (CORRECTOR) : along path : end game 19:20. maximum number of iterations : 4 4
21:22. relative precision for residuals : 1.000E09 : 1.000E11
23:24. absolute precision for residuals : 1.000E09 : 1.000E11
25:26. relative precision for corrections : 1.000E09 : 1.000E11
27:28. absolute precision for corrections : 1.000E09 : 1.000E11 SOLUTION TOLERANCES : along path : end game
29:30. inverse condition of Jacobian : 1.000E04 : 1.000E12
31:32. clustering of solutions : 1.000E04 : 1.000E12
33:34. solution at infinity : 1.000E+08 : 1.000E+12
********************************************************************
OUTPUT INFORMATION DURING CONTINUATION :
0 : no intermediate output information during continuation
TIMING INFORMATION for continuation
The elapsed time in seconds was 0.016000000 = 0h 0m 0s 16ms THE SOLUTIONS :
6 1
===========================================================================
solution 1 : start residual : 2.220E16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00
m 1
the solution for t :
x : 7.07106781186548E01 1.18694596821997E65
== err : 2.617E17 = rco : 1.000E+00 = res : 2.220E16 = real regular == solution 2 : start residual : 1.110E16 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m 1
the solution for t :
x : 2.58819045102521E01 0.00000000000000E+00
== err : 1.787E17 = rco : 1.000E+00 = res : 1.110E16 = real regular == solution 3 : start residual : 1.443E15 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m 1
the solution for t :
x : 9.65925826289068E01 1.36845553156720E48
== err : 6.226E17 = rco : 1.000E+00 = res : 1.998E15 = real regular == solution 4 : start residual : 2.220E16 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m 1
the solution for t :
x : 7.07106781186548E01 5.93472984109987E66
== err : 2.617E17 = rco : 1.000E+00 = res : 2.220E16 = real regular ==
solution 5 : start residual : 1.110E16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 2.58819045102521E01 0.00000000000000E+00
== err : 1.787E17 = rco : 1.000E+00 = res : 1.110E16 = real regular == solution 6 : tart residual : 1.443E15 #iterations : 1 success
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x : 9.65925826289068E01 1.36845553156720E48
== err : 6.226E17 = rco : 1.000E+00 = res : 1.998E15 = real regular ==
=================================================================
A list of 6 solutions has been refined :
Number of regular solutions : 6. Number of singular solutions : 0.
Number of real solutions : 6. Number of complex solutions : 0. Number of clustered solutions : 0. Number of solutions at infinity : 0. Number of failures : 0.
==================================================================
Frequency tables for correction, residual, and condition numbers : FreqCorr : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 : 6
FreqResi : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 : 6
FreqCond :6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : 6
Small correction terms and residuals counted to the right. Well conditioned and distinct roots counted to the left.
TIMING INFORMATION for Root Refining
The elapsed time in seconds was 0.000000000 = 0h 0m 0s 0ms
TIMING INFORMATION for solving the polynomial system
The elapsed time in seconds was 129.325000000 = 0h 2m 9s325ms
PHC ran from 25 March 2013, 05:16:33 till 25 March 2013, 05:20:34. The total elapsed time is 240 seconds = 4 minutes
DISCUSSION
The roots of polynomial equations was obtained using both the Newtons method and the phc (polynomial homotopy continuation) and their result was compared, we observed that the Newtons method is locally convergent while, the homotopy continuation method is globally convergent that is, blowing out all isolated real roots of the polynomial equation.
CONCLUSION
Many iterative techniques and Newton method for the solution of nonlinear equations have the drawback that the convergence depends on only good approximation.
If no approximation roots are known most of the classical method may be of little use. The method for following the path is a substantial global convergence. But Newton method could circle or could blow up when the Jacobian matrix at some point is singular. The imbedding method has the advantages of producing solutions over a large range of the independent variable, thereby giving a complete description of the solution behaviour and is use as a tool in overcoming the local convergence of iterative processes. The imbedding methods may be considered as a possibility to widen the domain of convergence or from another point of view, as a procedure to obtain sufficiently close starting points.
REFERENCE
Li, T. Y. (1987). Solving polynomial Systems. Maths. Intel. 9, 3, 33 39.
Morgan, A. AND SOMMESE, A.( 1987). Computing all solutions to polynomial systems using homotopy continuation. Appl. math. Comput. 24, 2, 115 138.
M. K. Jain, S. R. K. Iyengar, R. K. Jain. Numerical Methods for Scientific and Engineering Computation (Fifth Edition)
Shui Nel chow, John Mallet paret and J. A. Yorke, (1978) finding zeros of maps: Homotopy methods that are constructive with probability one, math. Of comput. Vol.32 , 887 899.
Watson, L. T, Morgan, A. P., AND Walker, H. F. (1997). HOMEPACK 90: A suite of Fortran 90 codes for globally convergent homotopy algorithms, ACM Trans. Math. Softw. 23, 4, 514 549.
ZANGWILL, W. I., AND C. B. GARCIA, (1981). Equilibrium programming: The path Following Approach and Dynamics