MASS-97 COMPUTER LAB 11/18/97
General structure of homotopy program
--------------------------------------
Prepare standard polynomial p0 and his roots,
given polynomial p1 and
their linear combination p=(1-t)p0+tp1 for t=0
Choose number_of_steps and dt=1/number of steps.
The real number of steps will slightly different, if collisions occur.
main loop:
roots=roots of p0
while t<1
t=t+dt; calculate new p, calculate newroots by Newton
find a pair of closest newroots: newroots(kmin) and newroots(mmin)
and calculate olddz and newdz (before and after attempt of Newton step
if TWO CLOSEST NEWROOTS DON'T COLLIDE then continue the standard procedure
if THEY ARE GOINg TO COLLIDE THEN switch to jump-procedure, i.e.
disregard the previous Newton step
find better approximation for z1=roots(kmin) and z2=roots(mmin),
calculate d1=(z1-z2)^2, store the current value of t at t1
increase t by dt/2 (safe step)
calculate z1 and z2 for new value of t (two Newton steps)
calculate again d2=(z1-z2)^2, store the current value of t at t2
!! now the crucial step: we are trying to predict the moment T
!! of collision: T=t2+x, x=(t2-t1)*d2/(d1-d2)
!! WARNING: x is a complex number which is close to positive real number
!! let's replace x by abs(x)
now lets jump to new value t3:
............t1.........t2...............T................t3........
and calculate new values of z1 and z2 after the jump from t2 to t3
to dd this just rotate z1 and z2 by 90 degrees about their center
implant new value z1 and z2 back to roots (calculated for t=t1)
and make two Newton steps
recalculate dt to prepare continue with the snadtard procedure
endif
end while