1
$\begingroup$

I am trying to implement an algorithm that finds (possibly) all solutions of a system of nonlinear polynomial equations $$F(X) = 0$$ I thought about using the (convex) homotopy $$H(X,T) = TF(X) + (1-T)G(X_0)$$ with $X_0$ a known solution to $G(X_0)=0$. By increasing $T$ iteratively from $0$ to $1$, the sought solution of $F(X)$ will be found.

During the hike on that path, I expect to encounter points of different bifurcation types. I hoped to use some of the many well-implemented numerical continuation algorithms that are available on the internet and would allow me to detect those points with their belonging paths.

I'm currently stuck at getting the numerical continuation running on the homotopy. To be more precise, the paths of solutions during numerical continuation is far from being a solution to $H(X,1)=0$. I do have a solid background in programming but only mediocre knowledge of mathematics. Therefore I hoped someone could review my approach and answer the following questions:

  1. Is numerical continuation applicable to the homotopy method? I see that there are some differences compared to the continuation of an ODE (i.e. in the predictor/corrector scheme) but isn't the approach the same?

  2. If not, can one detect the above-mentioned bifurcation points differently?

$\endgroup$
  • $\begingroup$ If X0 is a solution doesn't it make the second term on the right-hand side identically zero? $\endgroup$ – Maxim Umansky Apr 26 at 16:27
  • $\begingroup$ Exactly, G(x0) as the mapping with known solution x0 to the system will be 0 all the time. Iteratively increasing T and subsequent solving of H(X,T) on that path (i.e. by Newton-Rapsen-Method), you will distance yourself from G(x0) until you finally reached F(X). Actually, its about finding proper initial solutions for F(X) to make i.e. NR work. $\endgroup$ – RockedSalad121 Apr 27 at 8:06
  • $\begingroup$ I think @MaximUmansky ‘s purpose is because $G(X_0)=0$ always you have $H(X,T)=TF(X)$ and pretty much role of $G$ here is nothing and definition of $H$ is not helpful. I’m not sure what do you expect to receive by taking this approach... $\endgroup$ – Alone Programmer Apr 27 at 12:02
  • $\begingroup$ Homotopy method (sometimes called successive loading) is a widely used technique for solving systems of nonlinear equations. Hopefully I didn’t withheld crucial definitions for understanding the basic procedure but I’m actually more interested in the detection of bifurcation points and not homotopy implementation which I already did. But imagine just the first iteration: Inserting x=x0, t=0.1 into H(x,t) and apply NR will yield a solution x1 which is close enough for NR to converge, but different to x0 since F(x0) =|= 0. Increasing t slowly until t=1 and insert your before computed solution x. $\endgroup$ – RockedSalad121 Apr 27 at 15:05
  • $\begingroup$ I guess you could neglect the second term after the first iteration in the implementation but the stated formula is just the general definition of convex homotopy method $\endgroup$ – RockedSalad121 Apr 27 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.