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