Quadratic Turning Points

Suppose we are given a polynomial system with real coefficients whose solutions we don’t know but want to find, say f.  And suppose we have another polynomial system, also with real coefficients, which has the same number of solutions and we know said solutions, say g.  We assume both polynomials have real solutions.  We would like to use homotopy continuation to track the roots of g and obtain the roots of f.  This problem can become very interesting even for a simple case of one equation and one unknown.  Let’s consider the following example.

Let f=(x-1)(x-2)(x-3) and g=(x+1)(x+3)(x+5).  We pretend that we do not know the roots of f, but we know the roots of g – namely -1,-3,-5.  We use the homotopy h = (1-t)g+tf to track the roots of g for t \in [0,1].  In order to avoid any singularities, the \gamma-trick is commonly used.  That is, we solve the homotopy h_1 = (1-t)g+\gamma tf for some random \gamma \in \mathbb{C}.   What if we don’t want to use the \gamma-trick?  What happens in this case, generically?  If we proceed to solve h we run into a problem referred to as a quadratic turning point.  In the figure below we have the roots of g on the left hand side, and the roots of f on the right hand side.  One of the roots of g is easily tracked to a root of f; however, the other two fail.  They collide at the red point below.  This red point shows that for some value of the parameter t we have a double root of the system h, this is the quadratic turning point.

QuadTurnPoint

The two real roots collide and turn into complex roots, which never reach the real roots of f.  We can also see this in Macaulay2.  Running the code

needsPackage "NumericalAlgebraicGeometry"
R = CC[symbol x]
f = (x-1)*(x-2)*(x-3)
g = (x+1)*(x+3)*(x+5)
solsg = {{-1},{-3},{-5}}
solsf = track({g},{f},solsg)

we get as the output of the last line

o155 = {{1}, [M,t=.0141907], [M,t=.0141907]},

which shows that two of the roots of g could not be tracked to the roots of f.  We take a look to see what happens with the ill-behaved roots.

HomotopTrack

The first root was tracked in 11 steps, while the second and third roots failed the tracking at t=0.0141907. We can check that the system h has three real solutions for that value of t,namely -3.90919, -3.91807, -0.959881.  However, for t=0.014191, the solutions of h are -3.91363 - 0.000987i,  -3.91363 + 0.000987i, -0.95988.  Clearly, we have lost two real solutions to two complex solutions after passing through a double root of h.

To avoid this quadratic turning point, we can compute the discriminant of the polynomial h and identify when double roots will occur.  One question that arises from the observations above is —  Is there a way to “jump around” the double root?  That is, can we locally avoid this quadratic turning point by selecting points close by and continuing past it?

Now suppose we have a system with more equations and more unknowns.  How can we determine if there is a double root? A triple root? A root with even higher multiplicity?  The discriminant only tells us if there is a repeated root, but it does not tell us the multiplicity.  So, is there a way to determine for what coefficients of the system h we get multiple roots, the multiplicity of the roots, and how we can use this information to avoid singularities in the homotopy tracking?

 

Advertisements

One thought on “Quadratic Turning Points”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s