MatCont for Homotopy Method

Hello,

has anybody managed or can give some advice how to apply the homotopy method within matcont? My goal is to follow the path of solution x (equilibrium) to a linear shifted function H(x, t) = F(x(t)) − (1 − t)F(x0). During that path, I want to encounter possible bifurcatin points. F is a different function, that outputs just some kind of vector to the given x(t).

MatCont seems to be perfect for that application but it seems like it only handles differential equations. How can I adapt it to work with a simple (system of) equations?

Answer 1

[Andrew Newell]

The primary purpose of MatCont (which is a GUI front end for Cl_MatCont) is to analyze solution curves of the form . These may be equilibrium solutions of an ODE system

and that is how MatCont expects you to enter it. So one approach would just be to pretend it's an ODE and then find the equilibrium solutions.

MatCont creates a curve file and then uses Cl_MatCont to solve for the curve and its critical points. So another approach is to create the curve file yourself and run Cl_MatCont. You can then formulate it explicitly as an equilibrium curve instead of an ODE. This is more work and requires a much greater familiarity with Cl_MatCont, but it's a better approach if you're planning to solve a particular kind of problem many times. If you want to do that, I recommend reading the manual. In the first example it shows you how to solve and there is no ODE.

[FBBVC]

Andre, thank you for your reply. I have read both the manuals of MatCont and MatContM and implemented some examples/ode's/mappings myself. As you can see from my stated formula above, I need the (active) parameter t slowly to increase from 0 to 1. When I implement my system of equations and give it a go (doesn't matter @continuation or @equilibrium), all parameters including t are varied. What I need (wished MatCont to do) is to increase t slowly but steady, find the solutions to disturbed H(x,t) and detect bifurcation points. Is that even possible? I'm quite familiar with MatCont now, so if theres any close example in the tutorials/programm just point at it.

[Andrew Newell]

FBBVC, not following a particular parameter is one of the strengths of MatCont because it continues to follow a curve efficiently even if it goes back on itself. And it detects the bifurcations, so I'm not sure what the problem is. If you want a closely spaced set of values for t, why not just interpolate?

[FBBVC]

I considered the "active parameter" t to be a manipulatable setting variable in the meaning of "by increasing t from t=a to t=b, compute the equilibrium curve coordinates of my system H(x,t) on that path". But t varies unpredictably between [a,b], even decreases below a. I guess thats because of the next point on the path is predicted by the curve's tangent, which is suitable for ordinary path continuation of ODEs but not on my homotopy approach, right?

[Andrew Newell]

If I understand you correctly, you expect the homotopy curves to proceed monotonically from to , and when they don't you believe that's because of the path continuation algorithm. But, in general, there is no reason to expect them to be monotonic (check out "Probability-one homotopies in computational science", for example).

Maybe it would help if I understood exactly what you're trying to do, so here are some questions:

1. Is the path itself your goal, or the solutions of ?
2. Are you looking for real or complex solutions?
3. Is a polynomial system or some other kind of function?
4. How did you find ?

[FBBVC]

First of all, thank you for having this discussion with me, I really appreciate it!

I'm looking for solutions to a system F(x) consisting of nonlinear, polynomial equations that result from applying the harmonic balance method. By increasing the order N of the harmonics, the number of polynomial equations increase likewise. An adapted homotopy method (degree-increasing spectral homotopy, or just DISH) allows me to find solutions by starting at x0 (with x0 is a solution of F_N-1(x0) at lower dimension) until I reach F_N(x) at higher dimension. The method itself isn't very spectacular can be easily implemented. So the answers to your question are:

1. If I can track some bifurcation points during the homotopy path and follow their emerging paths, I hope to find more solutions than just one by following the main branch. So actually, it's both.
2. Only real solutions are relevant.
3. As you can find above, it's a system of polynomial equations.
4. Since I start homotopy at very low dimension, I can afford to compute solutions out of a large grid of initial values for Newton-Rapson-Method. Having done this, I found a set of different solutions from where I hoped to apply matcont for path continuation and track down bifurcation points.

I think that approach is somehow possible with matcont, because even if t increases up and down unpredictably, in some cases it passes t=1. I inserted the coordinates that matcont computed at that point and they are indeed solutions to F_N. Of course there might be isolated solutions that will never fuse with any branch, but some will eventually do and those are the one I'm trying to find.

Do you think it's possible to give the parameter t a generic gradient to force it "up" the curve to t=1?

[Andrew Newell]

That doesn't sound like it's likely to be very efficient or effective. To get much advantage out of multiplying solutions by following bifurcations, you'd have to start with a very symmetric polynomial. And you'd probably have to pay close attention to each path, so you'd better not have many solutions.

It turns out that you can get smooth, monotonic homotopies "with probability 1" (i.e., aside from some isolated exceptional cases) if you are doing it in complex projective space and add some randomness into the problem. Matcont can't do that, but a package called Bertini can. And I have created a Matlab front end for this called BertiniLab that is in the Mathworks File Exchange.

The beauty of Bertini is that it is virtually guaranteed to find all of the solutions to a system of polynomial equations, you don't have to worry about finding the starting points, and it has very sophisticated "end games" that can give you as much accuracy as you like. However, you get all the complex solutions, the vast majority of which are generally not real, so you have to sift through them. In general, the number of solutions goes up rapidly with dimension or degree, so you can't do very large systems or high polynomial degree. Mind you, that's an inherent problem, and I don't know if there is any reason to expect that your system has an unusually low number of solutions.

There are some tricks that greatly improve the efficiency. One is paramatopy, which creates a good starting system from which you can rapidly move to any parameter you want. There is also regeneration, which is not easily explained in a sentence or two. These are implemented in BertiniLab. The creators of Bertini have also created Bertini_real, which is presumably much more efficient for finding real solutions, but I haven't created a Matlab front end for it.

[FBBVC]

I will have a look into Bertini. Thank you very much so far!

[Andrew Newell]

Glad to help!