# An Algorithm for Isolating the Real Solutions of Piecewise Algebraic Curves

Authors: Jinming Wu; Xiaolei Zhang
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

The piecewise algebraic curve, as the set of zeros of a bivariate spline function,
is a generalization of the classical algebraic curve. In this paper, an algorithm is presented
to compute the real solutions of two piecewise algebraic curves. It is primarily based on the
Krawczyk-Moore iterative algorithm and good initial iterative interval searching algorithm.
The proposed algorithm is relatively easy to implement.


---

## Body

## 1. Introduction

LetΩ be a connected region in ℝ2. Using a finite number of irreducible algebraic curves in ℝ2, we divide the region Ω into several simply connected regions which are called partition cells. Denote by Δ the partition of the region Ω, which is the union of all partition cells δi,i=1,2,…,T.Denote byℙk(Δ) the collection of piecewise polynomials of degree k with respect to partition Δ as follows:(1.1)Pk(Δ)={s(x,y)∣s(x,y)|δi∈Pk,i=1,2,…,T},
where ℙk denotes the set of bivariate polynomials with total degree k.For integerμ≥0, we say(1.2)Skμ(Δ)={s(x,y)∣s(x,y)∈Cμ(Δ)∩Pk(Δ)}
is a bivariate spline space with smoothness μ and degree k of real coefficients.For as(x,y)∈Skμ(Δ), the zero set(1.3)C:{(x,y)∈Ω∣s(x,y)=0}
is called a Cμ real piecewise algebraic curve, denoted by z(s). Obviously, the piecewise algebraic curve is a generalization of the classic algebraic curve. However, it is very difficult to study piecewise algebraic curve not only because of the complexity of the partition but also because of the possibility of {(x,y)∣s(x,y)|δi=0}∩δi=∅.The piecewise algebraic curve is originally introduced by Wang in the study of multivariate spline interpolation. He pointed out that the given interpolation knots are properly posed if and only if they do not lie in a nonzero piecewise algebraic curve [1]. In recent years, Wang and his research group have done significant work on piecewise algebraic curves (see [1–8]). For example, Bēzout’s theorem [2, 4], Noether-type theorem [5, 7], Cayley-Bacharach theorem [6], and Riemann-Roch-type theorem [7] of piecewise algebraic curves were established. Besides, piecewise algebraic curve also relates to the remarkable Four-Color conjecture [4]. In fact, the Four-Color conjecture holds if and only if there exist three linear piecewise algebraic curves, and the union of these linear piecewise algebraic curves equals the union of all central lines of all triangles in arbitrary triangulation.The piecewise algebraic curve is a new and important topic in computer-aided geometry design and computational geometry and has many applications in various fields. It is necessary to study the related problems on piecewise algebraic curves. However, the above-mentioned Bēzout theorem gives a theoretic upper bound for the number of the intersection points of piecewise algebraic curves. Thus, it is important to compute or isolate the real zeros of the given piecewise algebraic curve (piecewise algebraic variety). In 2008, Wang and Wu [9] presented an algorithm for isolating the real zeros for univariate splines based on Descartes’ rule of signs. Later, Wang and Zhang [10] discussed the computation problem of the piecewise algebraic variety based on the interval iterative algorithm by introducing the concept of ɛ-deviation solutions. Very recently, Zhang and Wang [11] discussed the real roots isolation of the piecewise algebraic variety on polyhedron partition. Lang and Wang [12] presented an intersection points algorithm for piecewise algebraic curves based on Groebner bases. However, there is a common defect of these algorithms that we do not know whether there exists intersection points for two given piecewise algebraic curves on cells. It will cause a huge waste of computation.In this paper, we give the algorithm for isolating the real solutions of two piecewise algebraic curves which is primarily based on Krawczyk-Moore interval iterative algorithm and good initial iterative interval searching algorithm. The proposed method can reduce the computational cost greatly compared to the existing methods [11, 12]. More importantly, the proposed algorithm is easy to implement.The rest of this paper is organized as follows. In Section2, several concepts and results on interval iterative algorithm are recalled. In Section 3, the good initial iterative interval searching algorithm is given, which is the key of this paper. In Section 4, the main algorithm for isolating the real solutions of two piecewise algebraic curves is outlined. An illustrate example is provided in Section 5 and conclusion is drawn in Section 6.


## 2. Interval Iterative Algorithm

An interval iterative algorithm for nonlinear systems has been introduced by Moore in [13], developed and modified in papers [14–16]. Several basic concepts and results about interval arithmetic and interval iterative algorithm are reviewed.Definition 2.1.
For an intervalX=[a,b], the width, the midpoint, the absolute value and the sign of X are defined, respectively, as W([a,b])=b-a,m(X)=(a+b)/2,|X|=max⁡{a,b} and sign⁡(X) is −1 if b<0; 1 if a>0 and 0 otherwise.Definition 2.2.
Denoted byI(ℝ) is the set of all intervals. For X,Y∈I(ℝ), and ⋄∈{+,-,×,÷}, one defines
(2.1)X⋄Y={x⋄y∣x∈X,y∈Y}.Definition 2.3.
For an interval matrix(2.2)A=(A11A12⋯A1nA21A22⋯A2n⋯⋯⋯⋯An1An2⋯Ann),
where each Aij is an interval, then the midpoint, the width, and the norm of A are defined, respectively, as
(2.3)m(A)=(m(A11)m(A12)⋯m(A1n)m(A21)m(A22)⋯m(A2n)⋯⋯⋯⋯m(An1)m(An2)⋯m(Ann)),W(A)=max⁡i,jW(Aij),‖A‖=max⁡i∑j=1n|Aij|.Definition 2.4.
Letf be an arithmetic expression of a polynomial in ℝ[x1,…,xn]. One replaces all operands of f an intervals and replace all operations of f as interval operations and the result is denote by F. Then, F:I(ℝ)n→I(ℝ) is called an interval evaluation.Now, we recall the Moore form of Krawczyk algorithm and its basic results.Letf(x)=0 be a system of n nonlinear equations in n variables. Moore’s interval Newton algorithm is defined by(2.4)N(X)=m(X)-V(X)f(m(X)),
where V(X) is an interval matrix containing the inversion of interval matrix F′(x) and F′(x) is the monotonic interval evaluation of f′(x).Krawczyk proposed improved version of interval Newton’s method which does not require the inversion of interval matrix. The Krawczyk algorithm has the form(2.5)K(y,X)=y-Yf(y)+(I-YF′(X))(X-y),
where y is chosen from the region X, and Y is an arbitrary nonsingular matrix.In particular, ify and Y are chosen to be y=m(X) and Y=[m(F′(X))]-1, respectively, then the Moore form of Krawczyk algorithm becomes(2.6)K(X)=m(X)-[m(F′(X))]-1f(m(X))+(I-[m(F′(X))]-1F′(X))(X-m(X)).
The Moore form of Krawczyk algorithm has the following three basic properties.(1)
Ifx*∈X is a zero of f(x), then x*∈K(X).(2)
IfX∩K(X)=∅, then f(x) does not have zeros on X.(3)
IfK(X)⊂X, then f(x) has zeros on X.Thus, Krawczyk-Moore interval iterative algorithm is(2.7)X(k+1)=X(k)∩K(X(k)),K(X(k))=m(Xk)-[m(F′(Xk))]-1f(m(Xk))+(I-[m(F′(Xk))]-1F′(Xk))(Xk-m(Xk)),k=0,1,….For the existence of solutions to nonlinear equations, Moore proved the following results.Theorem 2.5 (see [14]).
If the two conditions(2.8)K(X(0))⊆X(0),r0=‖I-YF′(X(0))‖<1
are satisfied simultaneously, then there exists a unique solution x* of f(x)=0 in X(0) and the sequence {X(k)}k=0∞ converges at least linearly to x*.In fact, Moore further proved that the second condition was not essential with respect to this algorithm. Hence, this theorem still holds after deleting it [15]. Hence, we introduce the following definition in order to facilitate the later use.Definition 2.6.
IfK(X(0))⊆X(0), then X(0) is called a good initial iterative interval of f(x)=0.It is difficult to find the good initial iterative interval and we often can obtainX(0)∩K(X(0))≠∅ after a large number of iterations.


## 3. Good Initial Iterative Interval Searching Algorithm

An important problem in the Krawczyk algorithm is how to select the initial interval satisfying the unique restrictionK(X(0))⊆X(0). It is generally both X(0)∩K(X(0))=∅ and K(X(0))⊂X(0) cannot be satisfied after large amount of iterations if X(0) is chosen arbitrary. That is to say, X(0)∩K(X(0))≠∅ is occurred even when f(x) does not have zeros on X(0) and the algorithm is frustrating in this case. If we can determine that f(x) has real zeros in the prescribed domain and find all the good initial intervals, then the computational cost of interval iterative algorithm will be reduced greatly.In order to determine whether there exist real solutions of algebraic curvesf1(x,y)=0 and f2(x,y)=0 in the given region D, we firstly introduce the method of rotation degree of vector field.The rotation degree of the closed curve𝒞 on the vector field (f1,f2), denoted by j(f1,f2,𝒞D), is equal to(3.1)j(f1,f2,CD)=12π∮Cdarctanf2f1=12π∮Cf1df2-f2df1f12+f22,
where the given region D is circled by a closed curve 𝒞.We present the main result on the rotation degree of vector field.Theorem 3.1.
If there are no intersection points of algebraic curvesf1=0 and f2=0 in the domain D circled by closed curve 𝒞, then the rotation degree of the closed curve 𝒞 on the vector field (f1,f2) is equal to zero. Conversely, if the rotation degree of the closed curve 𝒞 on the vector field (f1,f2) is not equal to zero, then f1=0 and f2=0 have intersection points in the domain D.Proof.
Equation (3.1) can be written as
(3.2)∮Cf1df2-f2df1f12+f22=∮Cg1dx+g2dy,
where,
(3.3)g1=f1(∂f2/∂x)-f2(∂f1/∂x)f12+f22,g2=f1(∂f2/∂y)-f2(∂f1/∂y)f12+f22.
It can be easily checked that
(3.4)∂g1∂y=∂g2∂x.
Thus, if any point(x0,y0) on D satisfies f1(x0,y0)2+f2(x0,y0)2≠0, then it is from the Green formula that we have
(3.5)j(f1,f2,CD)=∮Cg1dx+g2dy=∫∫D(∂g2∂x-∂g1∂y)dxdy=0.
(1)
This conditionf1(x0,y0)2+f2(x0,y0)2≠0 is equivalent to that f1=0 and f2=0 do not have intersection points (x0,y0). The proof of the conversion is obvious.Remark 3.2.
It is pointed out that the rotation degree of the closed curve𝒞 on the vector field (f1,f2) can be computed conveniently when D=[xl,xr]×[yd,yu]. In this case, the simplified form of rotation degree is
(3.6)j(f1,f2,CD)=12π(∫xlxr[g1(x,yd)-g1(x,yu)]dx+∫ydyu[g2(xr,y)-g2(xl,y)]dy),
where the rotation degree of the closed curve 𝒞 is measured in the counterclockwise direction for positive direction. We denote by j(𝒞D) the rotation degree on the vector field (f1,f2) whenever this does not cause any confusion.Now, the good initial iterative interval searching algorithm for two algebraic curves which is outlined as follows.Algorithm 3.3.
Good initial iterative interval searching algorithm.
Input Two algebraic curvesf1(x,y)=0 and f2(x,y)=0 on an arbitrary region Ω.
Output The set of all good initial iterative intervals ofz(f1,f2).Step 1.
SetI=∅ and let X(0) be the minimal rectangle region containing Ω.Step 2.
IfK(X(0))∩Ω≠∅, then stop. Otherwise, compute j(𝒞X(0)). If j(𝒞X(0))=0, then z(f1,f2) has no real solutions and stop; if sign⁡(j(𝒞X(0)))≠0 and K(X(0))⊂X(0), then X(0) is a good initial iterative interval and I:=I∪X(0); otherwise, X(0) is divided into four smaller rectangles at the midpoints, denoted by Xj(1),j=1,…,4 and go to Step 3.Step 3.
SetX(0)=Xj(1),j=1,…,4 and go to Step 2.The number of real solutions ofz(f1,f2) is finite, which guarantees the algorithm will terminate after finite steps. Without loss of generality, we illustrate it with a simple example.Example 3.4.
LetΩ=[0,1]×[0,1] and suppose
(3.7)f1(x,y)=x2-3y+25,f2(x,y)=13x+y2-516.
SetX(0)=[0,1]×[0,1] and compute sign⁡(j(𝒞X(0)))=1. Meanwhile, we have K(X(0))=[-0.23,1.77]×[-0.03,0.64]. Since X(0)∩K(X(0))≠∅, then no conclusion can be drawn and X(0) is divided into four smaller rectangles at the midpoints, denoted by Xj(1),j=1,…,4 (see Figure 1).
Then we havej(𝒞X1(1))=j(𝒞X3(1))=j(𝒞X4(1))=0 and sign⁡(j(𝒞X2(1))=1. Meanwhile, we compute K(X2(1))=[0.54,0.94]×[0.16,0.42]. Hence, X2(1) is a good initial iterative interval because K(X2(1))⊂X2(1). Furthermore, the real solution of z(f1,f2) on Ω is [0.6852,0.6856]×[0.2898,0.29] only after three iteration steps with X2(1).
However, if we use the Krawczyk-Moore algorithm directly with initial iterative interval[0,1]×[0,1], then we have K(X[5])⊂X[5] after five iteration steps. Thus, we can only conclude that z(f1,f2) has one real solution on X[5]=[0.34,1]×[0.12,0.45] and we do not know whether there exists real solutions on Ω other than X[5].Figure 1
Region partition.


## 4. Main Algorithm

Given two piecewise algebraic curves which are defined by two bivariate spliness1(x,y)∈Sk1μ1(Δ),s2(x,y)∈Sk2μ2(Δ) and z(s1,s2) is assumed to be zero-dimensional, that is, it consists of only a finite number of points. Here, all the cells δi,i=1,…,T are assumed to be in “general position,” which means none of the zeros lie on their boundary. The problem we are addressing is to isolate the real zeros of z(s1,s2)={(x,y)∈Ω∣s1(x,y)=0,s2(x,y)=0}.It is well known that the interior of eachδi can be described as(4.1)δi={(x,y)∈R2∣g1[i](x,y)>0,…,gNi[i](x,y)>0},
where, g1[i](x,y),…,gNi[i](x,y)∈ℝ(x,y) are irreducible algebraic curves.Bys1[i] and s2[i] we denote bivariate polynomials representing s1 and s2 in the cell δi, respectively. The problem for isolating the real solutions of z(s1,s2) on Ω is equivalent to isolating the real solutions of the following semialgebraic systems(4.2)z[i](s1,s2)={s1[i](x,y)=0,s2[i](x,y)=0,g1[i](x,y)>0,…,gNi[i](x,y)>0,i=1,…,T.
With the above preparation, we can easily present the main algorithm for isolating the real intersection points of two piecewise algebraic curves s1(x,y)=0 and s2(x,y)=0 on Ω.Algorithm 4.1.
Isolating the real solutions of piecewise algebraic curves.
Input Two bivariate spliness1(x,y)∈Sk1μ1(Δ),s2(x,y)∈Sk2μ2(Δ) and a small tolerance ɛ.
Output The set of all isolating intervals ofz(s1,s2).Step 1.
Setj=1 and let I be an empty set.Step 2.
Perform good initial interval searching Algorithm3.3 for z(s1[j],s1[j]) on δi and obtain all the good iterative interval Xi(0),i=1,…,Ni. For each Xi(0),i=1,…,Ni, compute (Gj(Xi(0)))(j=1,…,Ni), where Gj is an interval evaluation of gj and consider the following three cases.
Case 1.
Ifsign⁡(Gj(Xi(0)))<0 for some j0(1≤j0≤Ni), delete Xi(0).
Case 2.
Ifsign⁡(Gj(Xi(0)))=0 for some j(1≤j0≤Ni), then we compute (K(Xi(0))) repeatedly until sign⁡(Gj(K(Xi(0))))<0 or sign⁡(Gj(K(Xi(0))))>0.
Case 3.
Ifsign⁡(Gj(Xi(0)))>0 for all j(1≤j0≤Ni) and W(Xi(0))<ɛ, then set I:=I∪Xi(0) and stop. Otherwise, if we let Xi(0):=K(Xi(0)) and compute K(Xi(0)) repeatedly until W(Xi(0))<ɛ, then set I:=I∪K(Xi(0)) and stop.Step 3.
Setj=j+1, If j≤T then go to Step 2. Else, stop and output the set of all isolating intervals I.


## 5. Numerical Example

In this section, an example is provided to illustrate the proposed algorithm is flexible and easy to implement.Example 5.1.
LetΩ={δ1,δ2,δ3,δ4} be a convex polyhedron partition of a pentagon VAVBVCVDVE in ℝ2, where δ1=[VAVBVCVO],δ2=[VCVDVO],δ3=[VDVEVO],δ4=[VEVAVO],VA=(1,0),VB=(1,1),VC=(0,1),VD=(-1,0),VE=(0,-1)andVO=(0,0) (see Figure 2). Let s1(x,y)∈S31(Δ) and s2(x,y)∈S21(Δ) be defined as follows:(i)
on cell(5.1)δ1:{s1[1](x,y)=y3-x,s2[1](x,y)=x2+y2-1,(ii)
on cell(5.2)δ2:{s1[2](x,y)=y3-2x2y-x,s2[2]=3x2+y2-1,(iii)
on cell(5.3)δ3:{s1[3]=-2x2y+3y2-x,s2[3](x,y)=3x2+2y2-1,(iv)
on cell(5.4)δ4:{s1[4](x,y)=3y2-x,s2[4](x,y)=x2+2y2-1.Figure 2
Two piecewise algebraic curvess1(x,y)=0 and s2(x,y)=0.The number of partition, the number of calculation for rotation degree and the number of calculation forK(X) on each cell δi,i=1,…,4 in order to find the good initial iterative intervals are listed in Table 1.Table 1
Computational complexity for isolating the real solutions.
Cellδ1δ2δ3δ4Number of partition2001Calculation for rotation degree9114Calculation forK(X)2001Therefore, the isolating interval ofz(s1,s2) on Ω is [0.5634,0.5638]×[0.8259,0.8261] after three iteration steps with good initial iterative interval [0.5,0.75]×[0.75,1] in cell δ1.Remark 5.2.
The total number of rotation degree and iteration steps required to be calculated in Example5.1 are 15 and 6, respectively. However, if we use the algorithm in [10] to compute z(s1,s2) globally, then more than three thousand iteration steps are needed in order to obtain the result with the same precision.Remark 5.3.
Compared to the algorithms in [11, 12], our proposed method does not require to transform the system into some triangular systems and compute the real zeros of polynomial or interval polynomial.


## 6. Conclusion and Future Work

This paper presents an algorithm for isolating the real solutions of two piecewise algebraic curves. It is primarily based on Krawczyk-Moore interval iterative algorithm and the good initial interval searching algorithm. The proposed algorithm is easy to implement and reduces the computational cost greatly.It is from Bezout’s number for piecewise algebraic curves that we know the number of intersection points of piecewise algebraic curves which not only depend on the degree of splines, but also heavily depend on the geometrical structure of the partition. However, the proposed algorithm does not use the intrinsic characteristic and relationship of bivariate splines and performs it on each cell independently. Therefore, it is vital to establish the relationship between the number of intersection points between the adjacent cells before performing our proposed algorithm. It remains to be our future work.



---

*Source: 658282-2011-12-25.xml*