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.


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.


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?


Newton’s Method

The Newton’s Method is the useful way to approximate the value of root of function. Even though it contains the calculation of the derivative of the function, the speed of the calculation is faster than the other methods, for instance, Bisection Method. Before we describe the Newton’s Method, first let us know about the Newton’s operator.

Suppose that we have a polynomial f\in \mathbf{k}[x] where \mathbf{k} is a field. Then, we can define Newton’s operator like the following:

N_f:\mathbf{k}[x]\rightarrow \mathbf{k},~~ N_f(x)=x-\frac{f(x)}{f'(x)}.

Now, we need to decide an initial approximation x_0. Then, by this x_0, we have the next approximation x_1 where x_1=N_f(x_0). Repeatedly, we can get the approximation \{x_n\} which, hopefully, converges to the root of f.


We can extend Newton’s method to the multivariate case. That is, if we have \mathbf{f} is a polynomial system (i.e. \mathbf{f}\in \mathbf{k}[x]^n), then we can define the Newton’s operator of \mathbf{f} like the following:

N_{\mathbf{f}}(x)=x-\left(\frac{\partial \mathbf{f}}{\partial x}(x)\right)^{-1}\mathbf{f}(x).

We can use the Newton’s Method if each approximation x_n satisfies \det\left(\frac{\partial \mathbf{f}}{\partial x}(x_n)\right)\ne0. In other words, if the solution is regular, then we can use the Newton’s Method.

However, we have a problem when the Jacobian matrix \frac{\partial \mathbf{f}}{\partial x} is not square, especially, when we have fewer variables than polynomials. Now, we will consider the way to “squaring up” the Jacobian matrix \frac{\partial \mathbf{f}}{\partial x}.

Suppose that we have n variables and m polynomials with m>n. First, in order to square up the matrix, we may “add” m-n more variables. However, then the determinant of the new matrix is clearly zero. Thus, it does not satisfy the regularity condition.

Secondly, we may think about the random linear combinations of the polynomials. In other words, consider the matrix A\in \mathbf{k}^{n\times m} and calculate A\mathbf{f}. Then, we have the square system A\mathbf{f}\in \mathbf{k}[x]^n. Moreover, we can verify the property that \mathbb{V}(\mathbf{f})\subset \mathbb{V}(A\mathbf{f}).

We will check the simple example about these problems.

Consider the polynomial system \mathbf{f}=(x^2~y^2~xy) in \mathbb{Q}[x]. Then,

(1) find the multiplicity of (0,0)

(2) does “squaring up” change the multiplicity of (0,0)?

In here, the multiplicity is defined by the number of elements in \mathbb{Q}[x]/\left<x^2, y^2,xy\right>.


From the figure above, we know that the multiplicity is 3.

Now, we will take any 2 linear combinations of x^2, y^2 and xy.


When we calculate the Gröbner basis for the ideal generated by randomly obtained 2 polynomials, we know that the leading terms are xy, x^2 and y^3. Therefore, the multiplicity is changed from 3 to 4.


What is GitHub?  If you are like me and have very little experience with computers, aside from email, then you probably don’t know what GitHub is.  I found this post to be very helpful in explaining what it is and why we would care to use it.  In short, GitHub is a version control system, it is open source, user-friendly, and we need it for our summer project.

Clear and easy to follow directions on how to set up an account and get started are available on Anton’s wiki.  Once you create an account, you would want to go to your settings and then choose the SSH and GPG Keys link from the left-hand tab (see below).

Screen Shot 2016-05-18 at 6.08.08 PM

Next, you would need to generate an SSH Key, following the instructions here. A link to these is also available on Anton’s wiki.

Once you have completed this part, open Aquamacs, if you are working on MacOSX, or Emacs for Windows OS.  Find/open the file named init.m2 in Aquamacs or Emacs; you can reference this post on where to look for the initialization file.  Once you have located the initialization file, you would want to redirect the path highlighted in the screenshot below.

Screen Shot 2016-05-18 at 9.52.27 PM.png

Replace the highlighted path with
-- path = {"< ~ >/M2/M2/Macaulay2/packages/"} | path.

This allows you to pull the Macaulay2 packages from the repository you cloned from GitHub.

Installing Macaulay2 on Microsoft-Windows

Macaulay2 would be the most important computer program that we may use. It is a useful calculation program especially for Algebraic Geometry field. There are lots way to run Macaulay2, but we will use the editor GNU Emacs. Since Macaulay2 can be supported by MacOSX and Linux, it may be not that problematic to install Macaulay2 for Mac, Linux users. However, Macaulay2 for Microsoft-Windows is not yet compiled and so, it may be a bit hard to start Macaulay for Windows users. Thus, in this post I will briefly introduce the way to install Macaulay2 on Windows environment.

Actually.. It can be a little personal.

First, the main instruction for the installation is here (Professor Anton’s website). To launch Macaulay2, we first need to make an environment of Linux-Ubuntu. In order to run Ubuntu on Windows, we use the Virtual Machine(VM), for instance, Virtualbox. Since Anton’s instruction and attached files provide whole method and conditions for installing Macaulay2 on Linux-Ubuntu. Thus, if you download Virtualbox, then you can just run the attached file on Anton’s instruction. Then, you may easily launch Emacs and Macaulay2 at there.

However, in my computer (I use Microsoft Surface pro 2, actually which is not that good machine on 2016) Anton’s attached file doesn’t work. So we selected the other way. We downloaded Ubuntu directly and made a new virtual system by using that. Now, what should we do is installing Emacs and Macaulay2. Our instruction for this issue was in the official page for Macaulay2. First by clicking ctrl+alt+t, we can open the terminal. Then, by using command sudo emacs /etc/apt/sources.list we can install the Emacs. After that we should add the line deb http://www.math.uiuc.edu/Macaulay2/Repositories/Ubuntu xenial main in the file  /etc/apt/sources.list (You may use Emacs for this).  Then, back to terminal and enter the public key sudo apt-key adv –keyserver hkp://keys.gnupg.net –recv-key CD9C0E09B0C780943A1AD85553F8BD99F40DCB31 for Macaulay2. And then the last things to do is installing Macaulay2 by using the following commands.

sudo apt-get update -q
sudo apt-get install -y -q macaulay2

You may need to download some files first (the files on the first part of the instruction for installing Macaulay2).


Now, it is  time to run Macaulay2 on Emacs.

First, enter alt+x and enter M2. Then, we can start Macaulay2.


We can make a temporary file to make a script file or load the exist script file. The content of the script can be calculated by f112.jpg

Numerical Algebraic Geometry

First Post!

We are a group of mathematicians from Georgia Tech: one professor – Anton Leykin, and three students: Tim, Cvetelina, & Kisun.  During the summer semester of 2016 we will be studying Numerical Algebraic Geometry; we will use this blog as the framework for this course/project.  Our main goals are listed below.

  • Create a knowledge base for Numerical Algebraic Geometry
    • Create a database of entries containing notes, problems, examples, etc.
  • Documentation of NumericalAlgebraicGeometry Package for Macaulay2
    • NumericalAlgebraicGeometry is a package used in Macaulay2, which is a software system used primarily in algebraic geometry and commutative algebra.  A description of this package is described here.  Our goal is to refine the documentation, provide appropriate examples, and relevant explanations.
  • Create a library of examples
    • Test the code from the NumericalAlgebraicGeometry package against this library of examples for efficiency.

In addition to three main goals listed above, collaboration is another component in our project.  We will welcome several visitors during the month of June whose work ranges from theory to applications in various fields, such as biology and computer vision.