Deflation Method to Find Singularity

We have considered paths obtained by the homotopy continuation and quadratic turning points. Now, we will suggest the way to approximate the quadratic turning point by using the method called the deflation method.

First, consider the following situation.

def.jpgThe homotopy path in \mathbb{C}^{n+1} is denoted by H(x,t). A=(x_0, t_0) is the quadratic turning point that we want to find and A'=(x_1,t_1) is the point that will be used to approximate A by using Newton’s method. In order to use the Newton’s method, we need to consider the following polynomial system obtained by the property of A.

\left\{\begin{array}{l} H(x,t)=0\\ \det\frac{\partial H(x,t)}{\partial x}=0 \end{array}\right.

The first condition H(x,t)=0 is obtained since the quadratic turning point is the point on the path. The second condition \det\frac{\partial H(x,t)}{\partial x}=0 is given by the property that the quadratic turning point is singular.

However, in here we encounter the problem about ‘inefficiency’. We know that \frac{\partial H(x,t)}{\partial x} is an (n+1)\times (n+1) matrix with polynomial entries. Therefore, computing the determinant of \frac{\partial H(x,t)}{\partial x} is a quite expensive task. We will consider the other way to use Newton’s method to A' to approximate A. The point is making the system of polynomial which consists of much simpler polynomials. For simpler polynomials, we will burrow unknowns  \bar{\lambda}=(\lambda_1,\dots, \lambda_n) from the higher dimension space \mathbb{C}^{2n+1}. Then, we can consider the following system with 2n+1 variables and $lates 2n+1$ equations.

\left[\begin{array}{c} H(x,t)\\ \frac{\partial H(x,t)}{\partial x}\left[\begin{array}{c} \lambda_1\\ \vdots \\ \lambda_n \end{array}\right]\\ \lambda \cdot v+1 \end{array}\right]

where v is the random vector in \mathbb{C}^n.

The first condition H(x,t) is trivial since the quadratic turning point is singular. The second condition \frac{\partial H(x,t)}{\partial x}\left[\begin{array}{c} \lambda_1\\ \vdots \\ \lambda_n \end{array}\right] is the variation of the condition \det\frac{\partial H(x,t)}{\partial x}=0. Since we have \det\frac{\partial H(x,t)}{\partial x}=0, we know that \frac{\partial H(x,t)}{\partial x} is a singular matrix, and hence, there is a nonzero element in the kernel of \frac{\partial H(x,t)}{\partial x} (actually, the dimension of the kernel of \frac{\partial H(x,t)}{\partial x} is 1 i.e. the line in \mathbb{C}^{n}). We consider \bar{\lambda}=(\lambda_1,\dots,\lambda_n) as a coordinate of an arbitrary element of the kernel of \frac{\partial H(x,t)}{\partial x}. Then, we have \frac{\partial H(x,t)}{\partial x}\left[\begin{array}{c} \lambda_1\\ \vdots \\ \lambda_n \end{array}\right]=0. The last condition \lambda \cdot v+1 is the procedure to choose the only one vector from the kernel of \frac{\partial H(x,t)}{\partial x}. Since the kernel of \frac{\partial H(x,t)}{\partial x} is 1-dimensional, there are infinitely many elements in the kernel. Therefore, by choosing an arbitrary vector v, we have the only one element \bar{\lambda} which satisfies the condition of \lambda \cdot v+1. It can be considered as the procedure to find the intersection between the kernel (the line) and v (the plane).

 Then, by using A'=(x_1,\lambda_1,t_1), we can approximate A=(x_0,\lambda_0,t_0) by Newton’s method. After we get A=(x_0,\lambda_0,t_0), we get the point (x_0,t_0) by just dropping \lambda coordinates.

Here is the additional question about this approach. How the ‘good’ value of \lambda_1 can be chosen? It may be a problem to find the proper initial condition for the system because by the initial condition \lambda_1, the approximate value of A can be changed substantially. Thus, it is needed to know how to decide \lambda_1.


Leave a Reply

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

You are commenting using your 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