Analysis Of Solving Polynomial Equations Using Homotopy Continuation Method

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:

1. Applying the Newtons method in solving polynomial equation;

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

3. 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 (general-purpose 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^6-1.96875000000000E+01*x^4

  + 6.56250000000000E+00*x^2-3.12500000000000E-01; ROOT COUNTS :

  total degree : 6

  HOMOTOPY PARAMETERS :

  d : 16

  k : 2

  a : -4.24751288571780E-01 -9.05310081053234E-01 t : 1.00000000000000E+00 0.00000000000000E+00

  no projective transformation

  ****************** CURRENT CONTINUATION PARAMETERS ***************** GLOBAL MONITOR :

  1. the condition of the homotopy 0

  2. number of paths tracked simultaneously 1

  3. maximum number of steps along a path 500

  4. distance from target to start end game : 1.000E-01

  5. order of extrapolator in end game 0

  6. maximum number of re-runs 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.000E-06 : 1.000E-08

  11:12. maximum step size : 1.000E-01 : 1.000E-02 13:14. reduction factor for step size : 7.000E-01 : 5.000E-01

  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.000E-09 : 1.000E-11

  23:24. absolute precision for residuals : 1.000E-09 : 1.000E-11 25:26. relative precision for corrections : 1.000E-09 : 1.000E-11 27:28. absolute precision for corrections : 1.000E-09 : 1.000E-11 SOLUTION TOLERANCES : along path : end game

  29:30. inverse condition of Jacobian : 1.000E-04 : 1.000E-12 31:32. clustering of solutions : 1.000E-04 : 1.000E-12

  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.220E-16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00

  m : 1

  the solution for t :

  x : 9.32469514203152E-01 -1.36845553156720E-48

  == err : 2.348E-17 = rco : 1.000E+00 = res : 2.220E-16 = 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.38619186083197E-01 0.00000000000000E+00

  == err : 0.000E+00 = rco : 1.000E+00 = res : 0.000E+00 = real regular == solution 3 : start residual : 5.551E-17 #iterations : 1 success

  t : 1.00000000000000E+00 0.00000000000000E+00

  m : 1

  the solution for t :

  x : -6.61209386466265E-01 1.55575381946529E-60

  == err : 1.769E-17 = rco : 1.000E+00 = res : 5.551E-17 = real regular == solution 4 : start residual : 2.220E-16 #iterations : 1 success

  t : 1.00000000000000E+00 0.00000000000000E+00

  m : 1

  the solution for t :

  x : -9.32469514203152E-01 1.36845553156720E-48

  == err : 2.348E-17 = rco : 1.000E+00 = res : 2.220E-16 = 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.38619186083197E-01 0.00000000000000E+00

  == err : 0.000E+00 = rco : 1.000E+00 = res : 0.000E+00 = real regular == solution 6 : start residual : 5.551E-17 #iterations : 1 success

  t : 1.00000000000000E+00 0.00000000000000E+00

  m : 1

  the solution for t :

  x : 6.61209386466265E-01 -1.55575381946529E-60

  == err : 1.769E-17 = rco : 1.000E+00 = res : 5.551E-17 = 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^6-48*x^4+18*x^2-1; ROOT COUNTS :

total degree : 6

HOMOTOPY PARAMETERS : d : 16

k : 2

a : 8.10952587803780E-01 5.85111869931172E-01 t : 1.00000000000000E+00 0.00000000000000E+00

no projective transformation

****************** CURRENT CONTINUATION PARAMETERS ***************** GLOBAL MONITOR :

1. the condition of the homotopy 0

2. number of paths tracked simultaneously 1

3. maximum number of steps along a path 500

4. distance from target to start end game : 1.000E-01

5. order of extrapolator in end game 0

6. maximum number of re-runs 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.000E-06 : 1.000E-08

11:12. maximum step size : 1.000E-01 : 1.000E-02 13:14. reduction factor for step size : 7.000E-01 : 5.000E-01

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.000E-09 : 1.000E-11

23:24. absolute precision for residuals : 1.000E-09 : 1.000E-11

25:26. relative precision for corrections : 1.000E-09 : 1.000E-11

27:28. absolute precision for corrections : 1.000E-09 : 1.000E-11 SOLUTION TOLERANCES : along path : end game

29:30. inverse condition of Jacobian : 1.000E-04 : 1.000E-12

31:32. clustering of solutions : 1.000E-04 : 1.000E-12

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.220E-16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00

m 1

the solution for t :

x : 7.07106781186548E-01 -1.18694596821997E-65

== err : 2.617E-17 = rco : 1.000E+00 = res : 2.220E-16 = real regular == solution 2 : start residual : 1.110E-16 #iterations : 1 success

t : 1.00000000000000E+00 0.00000000000000E+00

m 1

the solution for t :

x : -2.58819045102521E-01 0.00000000000000E+00

== err : 1.787E-17 = rco : 1.000E+00 = res : 1.110E-16 = real regular == solution 3 : start residual : 1.443E-15 #iterations : 1 success

t : 1.00000000000000E+00 0.00000000000000E+00

m 1

the solution for t :

x : -9.65925826289068E-01 1.36845553156720E-48

== err : 6.226E-17 = rco : 1.000E+00 = res : 1.998E-15 = real regular == solution 4 : start residual : 2.220E-16 #iterations : 1 success

t : 1.00000000000000E+00 0.00000000000000E+00

m 1

the solution for t :

x : -7.07106781186548E-01 5.93472984109987E-66

== err : 2.617E-17 = rco : 1.000E+00 = res : 2.220E-16 = real regular ==

solution 5 : start residual : 1.110E-16 #iterations : 1 success t : 1.00000000000000E+00 0.00000000000000E+00

m : 1

the solution for t :

x : 2.58819045102521E-01 0.00000000000000E+00

== err : 1.787E-17 = rco : 1.000E+00 = res : 1.110E-16 = real regular == solution 6 : tart residual : 1.443E-15 #iterations : 1 success

t : 1.00000000000000E+00 0.00000000000000E+00

m : 1

the solution for t :

x : 9.65925826289068E-01 -1.36845553156720E-48

== err : 6.226E-17 = rco : 1.000E+00 = res : 1.998E-15 = 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 non-linear 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