# Computing Singular Points of Projective Plane Algebraic Curves by Homotopy Continuation Methods

Authors: Zhongxuan Luo; Erbao Feng; Jielin Zhang
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

We present an algorithm that computes the singular points of projective plane algebraic curves and determines their multiplicities and characters. The feasibility of the algorithm is analyzed. We prove that the algorithm has the polynomial time complexity on the degree of the algebraic curve. The algorithm involves the combined applications of homotopy continuation
methods and a method of root computation of univariate polynomials. Numerical experiments show that our algorithm is feasible and efficient.


---

## Body

## 1. Introduction

Algebraic curves are a classic research object in mathematics. The related computation of algebraic curves arises in several applications, including number theoretic problems [1], ancient and modern architectural designs, error-correcting [2], biological shape [3], cryptographic algorithms [4, 5], and computer aided geometric design [6, 7]. Singular points and their multiplicities and characters play an important role in the research of algebraic curves [8]. They help to determine the genus of an algebraic curve. Singular points also show some shape features, such as nodes, self-intersections or cusps of real curves in robot motion planning, computer aided geometry design, and machine vision. And the determination of geometric shape and topology of the real curves depends on the singular points. The computation of singular points is also crucial for tracing curves algorithms [9].As singular points of an algebraic curve are the solutions of a polynomial system, most of algorithms in [10–15] solve the polynomial system either by Gröbner basis method described in [16] or by resultant computation. These methods rely on symbolic algebraic computation that requires exact input of coefficients of algebraic curves. It is easy for them to suffer from the overwhelming coefficient swell. So these methods may be limited to relatively small problem. Furthermore, it is difficult to obtain exact coefficients of algebraic curves due to data error in many fields of science and engineering.Although we have presented an algorithm to compute singular points of irreducible algebraic curves in [17], the algorithm is almost experimental and related analysis of the algorithm is not provided, for instance, the feasibility and complexity. The aims of this paper are analyzing the feasibility of this algorithm for computing singular points of reducible algebraic curves and proving that the algorithm has polynomial time complexity on the degree of an algebraic curve. We also present the effect of tiny perturbations of coefficients of algebraic curves on singular points and it may be a part of reasons why we compute the singular points numerically.Our algorithm is totally numerical and can deal with algebraic curves with inexact coefficients. It includes the applications of homotopy continuation methods and the method of calculating the multiple roots of univariate polynomials with inexact coefficients without using multiprecision arithmetic. Homotopy continuation method is a reliably and efficiently numerical method to solve the polynomial systems [18]. Several methods have been presented to compute roots of univariate polynomials, such as Laguerre’s method, Jenkins-Traub method, and the QR algorithm with the companion matrix. However, they cannot overcome a barrier of attainable accuracy on an m multiple root [19, 20]. If we have k1 digits coefficients accuracy and k2 digits machine precision, the attainable accuracy is min⁡{k1,k2}/m digits. For example, if the standard double precision of 16 decimal digits is used and the accuracy of coefficients of the polynomial is 15 digits, only 3 correct digits of a root of multiplicity 5 can be obtained by the above methods. A method proposed by Zeng [21] is not subject to the accuracy barrier and a lot of numerical experiments have shown its efficiency and robustness.The following section presents the basic notions on algebraic curves and singular points. In Section3, we focus on the algorithm of computing singular points. Section 4 is devoted to the numerical experiments. We conclude this paper in Section 5.


## 2. Preliminaries

In this section, we introduce some basic notions and results on algebraic curves and singular points. LetC be the complex numbers field and let P2(C) be the projective plane over C.Definition 1 (see [8, 22]).
A projective plane algebraic curve overC is defined as the set
(1)C={(a:b:c)∈P2(C)∣F(a,b,c)=0}
for a nonconstant square-free homogeneous polynomial F(x,y,z)∈C[x,y,z].
We callF(x,y,z) the defining polynomial of C. The degree of polynomial F(x,y,z) is called the degree of C.We take the linez=0 in P2(C) as the line at infinity. If the projective plane algebraic curve C is defined by the polynomial F(x,y,z), then the corresponding affine plane algebraic curve C* is defined by the dehomogenization f(x,y) of F(x,y,z),
(2)C*={(a,b)∈A2(C)∣f(a,b)=0},
where A2(C) is the affine plane over C.Therefore, if(3)F(x,y,z)=fn(x,y)+fn-1(x,y)z+⋯+f0(x,y)zn,
then
(4)f(x,y)=fn(x,y)+fn-1(x,y)+⋯+f0(x,y),
where fk(x,y) is a homogeneous polynomial of degree k and fn(x,y) is nonzero.Throughout this paper, whenever we speak of a “curve” we mean an “algebraic curve.” For brevity, we will usually use the phrase “the curveF(x,y,z)=0” instead of “the projective plane algebraic curve whose defining polynomial is F(x,y,z).” Of course, a polynomial G=cF, for some nonzero c∈C, defines the same curve, so F is unique only up to multiplication by nonzero constants. The above usage is also for the case of affine plane algebraic curve.Every point(a,b) on C* corresponds to a point (a:b:1) on C, and every additional point on C is a point at infinity. In other words, the first two coordinates of additional points are the nontrivial solutions of fn(x,y)=0, with the third coordinates being 0. Thus, the curve C has only finitely many points at infinity.Definition 2 (see [8, 22]).
LetC* be an affine plane algebraic curve over C defined by f(x,y)∈C[x,y], and let P=(a,b)∈C*. P is of multiplicity r on C* if and only if all derivatives of f(x,y) up to and including the (r-1)th vanish at P, but at least one rth derivative does not vanish at P.
A point of multiplicity two or more is said to be a singular point, and especially the point of multiplicity two is called a double point. A point of multiplicity one is called a simple point.It is evident that a necessary and sufficient condition that a point(a,b) of the curve f(x,y)=0 is singular is that
(5)f(a,b)=0,fx(a,b)=0,fy(a,b)=0.Definition 3 (see [8]).
Let the parametric equations of tangents to the curvef(x,y)=0 at P=(a,b) be
(6)x=a+λt,y=b+μt,
and the tangents to the curve f(x,y)=0 at P=(a,b) of multiplicity r are determined by the ratio λ:μ and correspond to the roots of
(7)fxrλr+(r1)fxr-1yλr-1μ+⋯+(rr)fyrμr=0,
where fxr-iyi=(∂rf/∂xr-i∂yi)(a,b), and they are counted with multiplicities equal to the multiplicities of the corresponding roots of this equation.Definition 4 (see [8, 22]).
A singular pointP of multiplicity r on an affine plane algebraic curve C* is called ordinary if and only if the r tangents to C* at P are distinct and nonordinary otherwise. The property of singular point P of being ordinary or nonordinary is called the character of P.The criteria for the multiplicity of a point on the projective plane algebraic curve can be characterized as follows.Proposition 5 (see [8]).
Q
∈
P
2
(
C
) is a point of multiplicity r on the projective plane algebraic curve F(x,y,z)=0 if and only if all the (r-1)th derivatives of F(x,y,z), but not all the rth derivatives, vanish at Q.As a corollary of this proposition, a pointQ of the curve F(x,y,z)=0 being singular can be put in a more convenient form.Proposition 6 (see [8, 22]).
Q
∈
P
2
(
C
) is a singular point of the projective plane algebraic curve F(x,y,z)=0 if and only if
(8)∂F∂x(Q)=∂F∂y(Q)=∂F∂z(Q)=0.The following two theorems are of use for analyzing the algorithm of the next section.Theorem 7 (see [8]).
If a curve of degreen with no multiple components has multiplicities ri at points Pi, then
(9)(n-1)(n-2)≥∑ri(ri-1).Theorem 8 (see [8] Bézout’s theorem).
Two curves of degreesm and n with no common components have exactly mn intersections.


## 3. Computation of Singular Points

In this section, a method of solving the overdetermined polynomial systems is presented first. We also outline the algorithm on computing the singular points of projective plane algebraic curves, and afterwards we analyze feasibility and complexity of the algorithm. The last subsection includes the effect of tiny perturbations of coefficients of the curve on singular points.


### 3.1. Solving Overdetermined Polynomial Systems

The following proposition shows how to reduce an overdetermined polynomial system to a square system that most of the papers and software programs on homotopy continuation method focus on. Letn and N be the number of equations and unknowns, respectively, and n>N.Proposition 9 (see [23, 24]).
There are nonempty Zariski open dense sets of parametersλij∈CN(n-N) or λij∈RN(n-N) such that every isolated solution of
(10)f1(x1,…,xN)=0,⋮fn(x1,…,xN)=0
is an isolated solution of
(11)f1(x1,…,xN)+∑j=N+1n‍λ1jfj(x1,…,xN)=0,⋮fN(x1,…,xN)+∑j=N+1n‍λNjfj(x1,…,xN)=0.The solutions set of an overdetermined system belongs to that of the corresponding square system, but the converse is not true.


### 3.2. Algorithm

We summarize the algorithm described in [17] for computing the singular points of irreducible projective plane algebraic curves.Algorithm 1.
Input. Consider projective plane algebraic curve F(x,y,z)=0 and corresponding affine plane algebraic curve f(x,y)=0. Threshold is ϵ>0.
Output. Consider singular points and their multiplicities and characters of the curve F(x,y,z)=0.Step 1 (randomization).
By Proposition9 and choosing the random complex numbers α and β, we add random multiples of the last equation to the first two equations of the polynomial system (5):
(12)f(x,y)+αfy(x,y)=0,fx(x,y)+βfy(x,y)=0.Step 2 (computing the singular points(a:b:1)).
We solve the polynomial system (12) by the polyhedral homotopy continuation method first and denote the solutions set as {(a:b:1)}. If |f(a,b)|<ϵ, (a:b:1) will be a singular point.Step 3 (computing the singular points(a:b:0) at infinity).
Sincefn(x,y) is a bivariate homogeneous polynomial of degree n, we obtain the points set {(a:b:0)} at infinity by solving the corresponding univariate polynomial. By Proposition 6, if Max⁡{(∂F/∂x)(a,b,0),(∂F/∂y)(a,b,0),(∂F/∂z)(a,b,0)}<ϵ, then (a:b:0) will be a singular point at infinity.
When we determined the multiplicity and character of singular point(a:b:0) at infinity, (a:b:0) will be transferred to point (a′:b′:1) by simple linear transformation.Step 4 (determining the multiplicity).
Evaluating the derivatives off(x,y) at a singular point from order equal to 2, if the moduli of all derivatives of f(x,y) up to and including the (r-1)th are less than ϵ, but at least one modulus of rth derivatives is greater than ϵ, then the multiplicity of this singular point will be determined as r.Step 5 (determining the character).
The tangents to the curvef(x,y)=0 at a singular point of multiplicity r correspond to the roots of (7). Whether the singular point is ordinary or not will be determined if there are multiple roots of (7).


### 3.3. Remarks on Feasibility of Algorithm

The following theorems and remarks will show the feasibility of Algorithm1 for computing the singular points of reducible projective plane algebraic curves.Theorem 10.
All the solutions of polynomial system (12) are isolated.Proof.
Sincef(x,y) is square-free, f(x,y) and fx(x,y) have no nonconstant common divisors. It also holds for f(x,y) and fy(x,y). In Step 1 of Algorithm 1, for the random complex numbers α and β, f(x,y)+αfy(x,y) and fx(x,y)+βfy(x,y) also have no nonconstant common divisors. It follows that all the solutions of polynomial system (12) are isolated.Remark 11.
The inequality in Theorem7 shows that an irreducible curve has finitely many singular points. So, the singular point of an irreducible curve is isolated.Theorem 12.
A reducible curvef(x,y)=0 has only finitely many singular points and they are all isolated points.Proof.
Without loss of generality, we may assume thatf(x,y)=f1(x,y)f2(x,y), where f1(x,y) and f2(x,y) are irreducible polynomials. Obviously, the singular points of f(x,y)=0 are the singular points of fi(x,y)=0(i=1,2) and the intersections of f1(x,y)=0 and f2(x,y)=0. By Remark 11 and Theorem 8, the set of singular points of f(x,y)=0 is finite and the singular points are all isolated.Remark 13.
When solving the polynomial system (12) in Step 2 of Algorithm 1 by homotopy continuation methods, Proposition 9 and Theorem 12 imply that all singular points (a:b:1) of reducible curve can be determined.Remark 14.
In Step2 of Algorithm 1, the Jacobian of polynomial system (12) is
(13)(fx+αfxyfy+αfyyfxx+βfxyfxy+βfyy).
This matrix is singular at a singular point of multiplicity three at least. The numerical techniques of homotopy continuation methods could deal with this well.Remark 15.
Asf(x,y) is a nonzero polynomial and has finite degree n, the modulus of some derivative of order less than or equal to n must be greater than the given threshold at a singular point. Hence, Step 4 of Algorithm 1 ends for determining the multiplicities of finitely many singular points.Remark 16.
We solve univariate polynomials in Steps3 and 5 of Algorithm 1. Numerical singular points make the coefficients of univariate polynomials in Step 5 inexact. We have mentioned the efficiency of computation of multiple roots of inexact univariate polynomials proposed by Zeng in Section 1. Employing Zeng’s method, we compute the singular points at infinity accurately in Step 3 and the characters of all singular points can be determined correctly in Step 5.


### 3.4. Computational Complexity

In this subsection, we analyze the computational complexity of Algorithm1. The degree of the curve f(x,y)=0 is denoted by n.Theorem 17.
The complexity of Step2 in Algorithm 1 is O(n2).Proof.
Shub and Smale [25, 26] present that finding an approximate zero of a polynomial system by homotopy continuation methods can be solved in polynomial time on the average and the number of arithmetic operations is bounded by cN4, where c is a universal constant and N is the number of variables. By Bézout’s Theorem 8, the number of solutions of polynomial system (12) is n(n-1) at most. We deduce that the complexity of Step 2 is no more than 16cn(n-1).Theorem 18.
The complexity of Steps3 and 5 in Algorithm 1 is O(n3) and O(n5) or less, respectively.Proof.
Pan reports [19] that the complexity of general root-finders of univariate polynomial of degree d is O(d2) or less, but Zeng’s method [21] reaches high accuracy on multiple roots at the higher computing cost of O(d3). It follows that the complexity of Step 3 is O(n3). From Steps 2 and 3, we know that the number of singular points of the curve f(x,y)=0 of degree n is n2 at most. Therefore, we conclude that the complexity of Step 5 is O(n5) or less.Theorem 19.
The complexity of Step4 in Algorithm 1 does not exceed O(n5).Proof.
The number of all the nonzero derivatives of bivariate polynomialf(x,y) of degree n is not more than n(n+3)/2. The complexity of evaluation of a polynomial at a point is linear in the degree of the polynomial and the number of variables. Since there are n2 points at most in Step 4 of Algorithm 1 and the complexity of linear change of coordinates is polynomial in the number of variables, the complexity of Step 4 does not exceed O(n5).The following theorem holds at once.Theorem 20.
The complexity of Algorithm1 is polynomial time in the degree n of the projective plane algebraic curve and is O(n5).


### 3.5.  Effect of Tiny Perturbations on Singular Points

The authors [27] conclude that random perturbations of coefficients of plane algebraic curves will almost invariably destroy all singular points. The current methods dealing with plane algebraic curves are almost ill-conditioned with respect to tiny perturbations. For example, let us consider the curve x3-y2=0 with nonordinary double singular point (0,0) and its perturbation x3-y2+ϵx2=0, where ϵ>0. It is natural to compute the approximate singular point out and the original character for relative magnitude ϵ>0. However, the character of singular point (0,0) is changed by using symbolic algebraic computation, even if ϵ>0 is sufficiently small.For the curvex3-y2+ϵx2=0, when ϵ=0.0000001, the numerical procedure based on Algorithm 1 outputs a nonordinary double singular point
(14)(-0.00000006666667+0.00000000000000i,a0.00000000000000-0.00000000000000i).


## 3.1. Solving Overdetermined Polynomial Systems

The following proposition shows how to reduce an overdetermined polynomial system to a square system that most of the papers and software programs on homotopy continuation method focus on. Letn and N be the number of equations and unknowns, respectively, and n>N.Proposition 9 (see [23, 24]).
There are nonempty Zariski open dense sets of parametersλij∈CN(n-N) or λij∈RN(n-N) such that every isolated solution of
(10)f1(x1,…,xN)=0,⋮fn(x1,…,xN)=0
is an isolated solution of
(11)f1(x1,…,xN)+∑j=N+1n‍λ1jfj(x1,…,xN)=0,⋮fN(x1,…,xN)+∑j=N+1n‍λNjfj(x1,…,xN)=0.The solutions set of an overdetermined system belongs to that of the corresponding square system, but the converse is not true.


## 3.2. Algorithm

We summarize the algorithm described in [17] for computing the singular points of irreducible projective plane algebraic curves.Algorithm 1.
Input. Consider projective plane algebraic curve F(x,y,z)=0 and corresponding affine plane algebraic curve f(x,y)=0. Threshold is ϵ>0.
Output. Consider singular points and their multiplicities and characters of the curve F(x,y,z)=0.Step 1 (randomization).
By Proposition9 and choosing the random complex numbers α and β, we add random multiples of the last equation to the first two equations of the polynomial system (5):
(12)f(x,y)+αfy(x,y)=0,fx(x,y)+βfy(x,y)=0.Step 2 (computing the singular points(a:b:1)).
We solve the polynomial system (12) by the polyhedral homotopy continuation method first and denote the solutions set as {(a:b:1)}. If |f(a,b)|<ϵ, (a:b:1) will be a singular point.Step 3 (computing the singular points(a:b:0) at infinity).
Sincefn(x,y) is a bivariate homogeneous polynomial of degree n, we obtain the points set {(a:b:0)} at infinity by solving the corresponding univariate polynomial. By Proposition 6, if Max⁡{(∂F/∂x)(a,b,0),(∂F/∂y)(a,b,0),(∂F/∂z)(a,b,0)}<ϵ, then (a:b:0) will be a singular point at infinity.
When we determined the multiplicity and character of singular point(a:b:0) at infinity, (a:b:0) will be transferred to point (a′:b′:1) by simple linear transformation.Step 4 (determining the multiplicity).
Evaluating the derivatives off(x,y) at a singular point from order equal to 2, if the moduli of all derivatives of f(x,y) up to and including the (r-1)th are less than ϵ, but at least one modulus of rth derivatives is greater than ϵ, then the multiplicity of this singular point will be determined as r.Step 5 (determining the character).
The tangents to the curvef(x,y)=0 at a singular point of multiplicity r correspond to the roots of (7). Whether the singular point is ordinary or not will be determined if there are multiple roots of (7).


## 3.3. Remarks on Feasibility of Algorithm

The following theorems and remarks will show the feasibility of Algorithm1 for computing the singular points of reducible projective plane algebraic curves.Theorem 10.
All the solutions of polynomial system (12) are isolated.Proof.
Sincef(x,y) is square-free, f(x,y) and fx(x,y) have no nonconstant common divisors. It also holds for f(x,y) and fy(x,y). In Step 1 of Algorithm 1, for the random complex numbers α and β, f(x,y)+αfy(x,y) and fx(x,y)+βfy(x,y) also have no nonconstant common divisors. It follows that all the solutions of polynomial system (12) are isolated.Remark 11.
The inequality in Theorem7 shows that an irreducible curve has finitely many singular points. So, the singular point of an irreducible curve is isolated.Theorem 12.
A reducible curvef(x,y)=0 has only finitely many singular points and they are all isolated points.Proof.
Without loss of generality, we may assume thatf(x,y)=f1(x,y)f2(x,y), where f1(x,y) and f2(x,y) are irreducible polynomials. Obviously, the singular points of f(x,y)=0 are the singular points of fi(x,y)=0(i=1,2) and the intersections of f1(x,y)=0 and f2(x,y)=0. By Remark 11 and Theorem 8, the set of singular points of f(x,y)=0 is finite and the singular points are all isolated.Remark 13.
When solving the polynomial system (12) in Step 2 of Algorithm 1 by homotopy continuation methods, Proposition 9 and Theorem 12 imply that all singular points (a:b:1) of reducible curve can be determined.Remark 14.
In Step2 of Algorithm 1, the Jacobian of polynomial system (12) is
(13)(fx+αfxyfy+αfyyfxx+βfxyfxy+βfyy).
This matrix is singular at a singular point of multiplicity three at least. The numerical techniques of homotopy continuation methods could deal with this well.Remark 15.
Asf(x,y) is a nonzero polynomial and has finite degree n, the modulus of some derivative of order less than or equal to n must be greater than the given threshold at a singular point. Hence, Step 4 of Algorithm 1 ends for determining the multiplicities of finitely many singular points.Remark 16.
We solve univariate polynomials in Steps3 and 5 of Algorithm 1. Numerical singular points make the coefficients of univariate polynomials in Step 5 inexact. We have mentioned the efficiency of computation of multiple roots of inexact univariate polynomials proposed by Zeng in Section 1. Employing Zeng’s method, we compute the singular points at infinity accurately in Step 3 and the characters of all singular points can be determined correctly in Step 5.


## 3.4. Computational Complexity

In this subsection, we analyze the computational complexity of Algorithm1. The degree of the curve f(x,y)=0 is denoted by n.Theorem 17.
The complexity of Step2 in Algorithm 1 is O(n2).Proof.
Shub and Smale [25, 26] present that finding an approximate zero of a polynomial system by homotopy continuation methods can be solved in polynomial time on the average and the number of arithmetic operations is bounded by cN4, where c is a universal constant and N is the number of variables. By Bézout’s Theorem 8, the number of solutions of polynomial system (12) is n(n-1) at most. We deduce that the complexity of Step 2 is no more than 16cn(n-1).Theorem 18.
The complexity of Steps3 and 5 in Algorithm 1 is O(n3) and O(n5) or less, respectively.Proof.
Pan reports [19] that the complexity of general root-finders of univariate polynomial of degree d is O(d2) or less, but Zeng’s method [21] reaches high accuracy on multiple roots at the higher computing cost of O(d3). It follows that the complexity of Step 3 is O(n3). From Steps 2 and 3, we know that the number of singular points of the curve f(x,y)=0 of degree n is n2 at most. Therefore, we conclude that the complexity of Step 5 is O(n5) or less.Theorem 19.
The complexity of Step4 in Algorithm 1 does not exceed O(n5).Proof.
The number of all the nonzero derivatives of bivariate polynomialf(x,y) of degree n is not more than n(n+3)/2. The complexity of evaluation of a polynomial at a point is linear in the degree of the polynomial and the number of variables. Since there are n2 points at most in Step 4 of Algorithm 1 and the complexity of linear change of coordinates is polynomial in the number of variables, the complexity of Step 4 does not exceed O(n5).The following theorem holds at once.Theorem 20.
The complexity of Algorithm1 is polynomial time in the degree n of the projective plane algebraic curve and is O(n5).


## 3.5.  Effect of Tiny Perturbations on Singular Points

The authors [27] conclude that random perturbations of coefficients of plane algebraic curves will almost invariably destroy all singular points. The current methods dealing with plane algebraic curves are almost ill-conditioned with respect to tiny perturbations. For example, let us consider the curve x3-y2=0 with nonordinary double singular point (0,0) and its perturbation x3-y2+ϵx2=0, where ϵ>0. It is natural to compute the approximate singular point out and the original character for relative magnitude ϵ>0. However, the character of singular point (0,0) is changed by using symbolic algebraic computation, even if ϵ>0 is sufficiently small.For the curvex3-y2+ϵx2=0, when ϵ=0.0000001, the numerical procedure based on Algorithm 1 outputs a nonordinary double singular point
(14)(-0.00000006666667+0.00000000000000i,a0.00000000000000-0.00000000000000i).


## 4. Numerical Experiments

In this section, Algorithm1 is implemented in Matlab and some examples are presented to show the efficiency of corresponding numerical procedure. There are many freely available homotopy continuation packages. As Lee et al. [28] report that HOM4PS-2.0 is generally the fastest package for solving small to moderately large sparse systems, it is employed to solve polynomial system (12) in Algorithm 1. Many numerical examples are provided in [17] where the curves are irreducible and the coefficients of the curves are inexact. We finish this section with two reducible curves.Example 1.
Consider(15)f(x,y)=f1(x,y)f2(x,y)=x5y2+x4y+x6+x6y+2x4y2+x5+x5y+x3y4+x4y3+x2y4+x3y2+x3y3-xy4-y3-x2y2-y4-xy2-y3x,f1(x,y)=y2x+y+x2+yx2+y2+x+yx,f2(x,y)=x4+x2y2-y2.There are two componentsf1(x,y)=0 and f2(x,y)=0 for the curve f(x,y)=0. The curve f1(x,y)=0 has no singular points and its real part is plotted in Figure 1. The curve f2(x,y)=0 has nonordinary double singular point corresponding to (0 : 0 : 1) and ordinary double singular point corresponding to (0 : 1 : 0). Figure 2 shows real part of the curve f2(x,y)=0 and the singular point corresponding to (0 : 0 : 1) is marked by a solid square.Figure 1
Real part off1(x,y)=0 in Example 1.Figure 2
Real part off2(x,y)=0 in Example 1.The curvesf1(x,y)=0 and f2(x,y)=0 have 8 intersections corresponding to Qi(i=1,…,8). Their related projective curves intersect Q9=(0,1,0) at infinity. (0,0) is the simple point of f1(x,y)=0, nonordinary double point of f2(x,y)=0. Therefore, (0,0) corresponding to Q1= (0 : 0 : 1) is nonordinary singular point of multiplicity of 3 of f(x,y)=0. Q9= (0 : 1 : 0) is ordinary double point and simple point of the corresponding projective curves for f2(x,y)=0 and f1(x,y)=0, respectively. The tangent to the latter at Q9 coincides with one tangent to the former at Q9. So, Q9= (0 : 1 : 0) is nonordinary singular point of multiplicity of 3 of the projective curve corresponding to f(x,y)=0.Table1 lists the results of our numerical procedure for the projective curve corresponding to f(x,y)=0 in Example 1. Figure 3 presents the real part of f(x,y)=0 in Example 1. The solid dot marks the real intersection of f1(x,y)=0 and f2(x,y)=0 corresponding to Q5. The real singular point corresponding to Q1= (0 : 0 : 1) is still marked by a solid square.Table 1
Results forf(x,y)=0 in Example 1.
x
y
z
Mult.
Ord.
Q
1
0.00000003
+
0.00000005
i
0.00000000
+
0.00000000
i
1.00000000
3
No
Q
2
-
0.89868027
+
0.41873939
i
-
0.15046254
+
1.06341745
i
1.00000000
2
Yes
Q
3
0.36804326
-
1.20320368
i
-
0.92239819
-
0.40178011
i
1.00000000
2
Yes
Q
4
0.36804326
+
1.20320368
i
-
0.92239819
+
0.40178011
i
1.00000000
2
Yes
Q
5
-
0.49367385
-
0.00000000
i
0.28024456
+
0.00000000
i
1.00000000
2
Yes
Q
6
-
0.89868027
-
0.41873939
i
-
0.15046254
-
1.06341745
i
1.00000000
2
Yes
Q
7
0.77747393
+
0.21532054
i
-
0.56726154
-
0.66500198
i
1.00000000
2
Yes
Q
8
0.77747393
-
0.21532054
i
-
0.56726154
+
0.66500198
i
1.00000000
2
Yes
Q
9
0.00000000
1.00000000
0
3
NoFigure 3
Real part off(x,y)=0 in Example 1.We use the abbreviations “Mult.” and “Ord.” for the words “multiplicity” and “ordinary” in our tables, respectively.Example 2.
Consider(16)f(x,y)=f1(x,y)f2(x,y)=3264925x4y+445317x2y2+1485786x2y+1055617x4+443586x2-1606976xy4-222040y4-326949x5y+2949048xy5+421959x3y3-295824y2-283584y3-291435x2y3+8419454x3y2-3938342y5x2-2629937x5y2+270492x9y2-180328x8y-707315x7y+121188x9y+2832768y6x+572040y5x5+160152y9x+621050y7x3-536400y4x4+2513654x3y-1676336xy3-3734596y6x5+154032y10x-102688y9+24438y2x4+491170x7y3-542892x6y2-1330879x7y2-734296y8x3-4707928y5x4+215696y7x2+8655317y6x3-1322704y8x-211840y5+659312y7-106768y8+685832y6+296494x6-80792x8+496542x6y-698748y6x2-2167689y5x3-1375744y7x+1350780y4x2+9826722y4x5-6460272y3x4-18749449y4x3-346096x7y4-250144x6y3-1006320y3x5,f1(x,y)=51344y5+53384y4-47264y3-415912x2y3-49304y2+29070x2y2+247631x2y+90164x4y+73931x2+40396x4,f2(x,y)=3x5y+3xy5+10x3y3-2x4-2y4-12x2y2-23x3y-23xy3+11x2+11y2+34xy+6.The curvef(x,y)=0 has two components f1(x,y)=0 and f2(x,y)=0. There are six singular points corresponding to Pi(i=1,…,6) for the curve f1(x,y)=0 and they are marked by solid squares in Figure 4 where the real part of the curve f1(x,y)=0 is plotted. Four singular points corresponding to Pi(i=7,…,10) of the curve f2(x,y)=0 are illustrated by the solid triangles in Figure 5 where the real part of the curve f2(x,y)=0 is presented. Obviously, Pi(i=1,…,10) are singular points of the projective curve corresponding to the curve f(x,y)=0.Figure 4
Real part off1(x,y)=0 in Example 2.Figure 5
Real part off2(x,y)=0 in Example 2.There are 29 intersections corresponding toPi(i=11,…,39) for the curves f1(x,y)=0 and f2(x,y)=0. Their related projective curves intersect P40 at infinity. These 30 intersections Pi(i=11,…,40) are also singular points of the projective curve corresponding to the curve f(x,y)=0. So the curve f(x,y)=0 has 40 singular points.Figure6 shows the real part of the curve f(x,y)=0 whose real singular points are marked by the solid dots, squares, and triangles. The solid dots mark the real intersections of the curves f1(x,y)=0 and f2(x,y)=0. The solid squares and triangles illustrate the singular points of the curves f1(x,y)=0 and f2(x,y)=0, respectively. Table 2 lists the results of our numerical procedure for the projective curve corresponding to f(x,y)=0 in Example 2.Table 2
Results forf(x,y)=0 in Example 2.
x
y
z
Mult.
Ord.
P
1
0.00000000
0.00000000
-
0.00000000
i
1.00000000
2
Yes
P
2
-
0.50000000
-
0.00000000
i
0.99999999
+
0.00000000
i
1.00000000
2
Yes
P
3
-
0.00000000
-
0.00000000
i
-
1.00000000
+
0.00000000
i
1.00000000
2
Yes
P
4
0.99999999
+
0.00000000
i
-
0.50000000
-
0.00000000
i
1.00000000
2
Yes
P
5
-
1.00000000
+
0.00000000
i
-
0.50000000
+
0.00000000
i
1.00000000
2
Yes
P
6
0.50000000
+
0.00000000
i
1.00000000
+
0.00000000
i
1.00000000
2
Yes
P
7
2.41421356
-
0.00000000
i
0.41421356
-
0.00000000
i
1.00000000
2
Yes
P
8
-
2.41421356
+
0.00000000
i
-
0.41421356
-
0.00000000
i
1.00000000
2
Yes
P
9
0.41421356
-
0.00000000
i
2.41421356
-
0.00000000
i
1.00000000
2
Yes
P
10
-
0.41421356
-
0.00000000
i
-
2.41421356
+
0.00000000
i
1.00000000
2
Yes
P
11
1.86368244
+
0.00000000
i
-
0.81167781
+
0.00000000
i
1.00000000
2
Yes
P
12
-
0.56599742
+
0.66867689
i
0.95095432
-
0.12549545
i
1.00000000
2
Yes
P
13
-
0.58308154
+
0.00000000
i
-
2.34385106
+
0.00000000
i
1.00000000
2
Yes
P
14
1.67570344
+
0.00000000
i
1.32326562
+
0.00000000
i
1.00000000
2
Yes
P
15
0.79829233
1.77539598
+
0.00000000
i
1.00000000
2
Yes
P
16
0.09549542
-
0.39009016
i
-
0.97196258
+
0.89462218
i
1.00000000
2
Yes
P
17
0.52445070
+
0.00000000
i
-
2.19040368
-
0.00000000
i
1.00000000
2
Yes
P
18
0.05975897
-
0.25434442
i
-
0.06366391
-
0.36672723
i
1.00000000
2
Yes
P
19
0.15502368
-
1.39689139
i
-
0.01303583
+
0.19325672
i
1.00000000
2
Yes
P
20
0.51269502
+
0.43085324
i
-
0.51116222
+
0.08768075
i
1.00000000
2
Yes
P
21
0.15502368
+
1.39689139
i
-
0.01303583
-
0.19325672
i
1.00000000
2
Yes
P
22
0.09549542
+
0.39009016
i
-
0.97196258
-
0.89462218
i
1.00000000
2
Yes
P
23
0.54660137
+
0.59723958
i
-
0.36484540
-
0.17346068
i
1.00000000
2
Yes
P
24
1.40455064
+
0.00000000
i
1.22984070
+
0.00000000
i
1.00000000
2
Yes
P
25
-
2.11390876
-
0.00000000
i
-
0.91044961
-
0.00000000
i
1.00000000
2
Yes
P
26
-
2.39860964
+
0.00000000
i
-
0.45929305
-
0.00000000
i
1.00000000
2
Yes
P
27
-
0.35998047
+
0.25179313
i
0.61198862
-
0.60194230
i
1.00000000
2
Yes
P
28
-
1.29601698
-
0.00000000
i
1.19480441
+
0.00000000
i
1.00000000
2
Yes
P
29
0.05975897
+
0.25434442
i
-
0.06366391
+
0.36672723
i
1.00000000
2
Yes
P
30
-
0.51418694
-
0.00000000
i
-
2.16372657
-
0.00000000
i
1.00000000
2
Yes
P
31
-
1.79027097
+
0.00000000
i
-
0.78332475
-
0.00000000
i
1.00000000
2
Yes
P
32
-
0.82449210
+
0.00000000
i
1.84542750
+
0.00000000
i
1.00000000
2
Yes
P
33
-
0.35998047
-
0.25179313
i
0.61198862
+
0.60194230
i
1.00000000
2
Yes
P
34
-
2.28499755
-
0.00000000
i
-
0.46036727
+
0.00000000
i
1.00000000
2
Yes
P
35
2.24284114
-
0.00000000
i
-
0.46080446
-
0.00000000
i
1.00000000
2
Yes
P
36
0.92084852
+
0.00000000
i
2.10459508
+
0.00000000
i
1.00000000
2
Yes
P
37
-
0.56599742
-
0.66867689
i
0.95095432
+
0.12549545
i
1.00000000
2
Yes
P
38
0.54660137
-
0.59723958
i
-
0.36484540
+
0.17346068
i
1.00000000
2
Yes
P
39
0.51269502
-
0.43085324
i
-
0.51116222
-
0.08768075
i
1.00000000
2
Yes
P
40
1.00000000
0.00000000
0.00000000
2
YesFigure 6
Real part off(x,y)=0 in Example 2.It takes 0.28628 seconds and 1.26786 seconds for our numerical procedure to obtain the results of Examples1 and 2, respectively, on the Lenovo PC with Pentium Dual Core, CPU of 2.5 GHZ, and memory of 1.99 GB. We usually choose 10-6 as the thresholds in Steps 2, 3, and 4 in Algorithm 1.


## 5. Conclusions

This paper provides an effective algorithm for computing the singular points of projective plane algebraic curves by homotopy continuation methods. The determination of multiplicities relies on the accuracy of singular points. The characters of singular points are determined by Zeng’s method for computing multiplicities of roots of inexact univariate polynomials. The precision of coefficients of inexact univariate polynomials in our algorithm depends on the accuracy of singular points. Several numerical examples are presented to illustrate the efficiency of our algorithm. We will discuss the adaptive thresholds of the algorithm in the future.



---

*Source: 230847-2014-06-05.xml*