Printer Friendly

Distributed cooperative algorithm for k-M set with negative integer k by fractal symmetrical property.

1. Introduction

Since Mandelbrot has presented M set (Mandelbrot's set), fractals have been soon used everywhere [1]. Nowadays, generalized M sets become representatives of chaotic dynamics. We present M set in Definition 1 and k-M set in Definition 2 as follows [2]. In Definition 1 [f.sup.n.sub.c](z) is defined in (1).

Definition 1. M-set = {c | [lim.sub.n][right arrow][f.sup.n.sub.c](0)[??][infinity](c [member of C, n = 1 ... [infinity)}

[f.sup.n.sub.c](z) = [([f.sup.n-1.sub.c](z)).sup.2] + c where [f.sup.1.sub.c] (z) = [z.sup.2] + c. (1)

Then, when we reform [f.sup.n.sub.c](z) to [f.sup.n.sub.c](z) in (2), definition of k-M set is presented in Definition 2. Consider

[f.sup.n.sub.c](z) = [([f.sup.n.sub.c-1] (z)).sup.k] + c where [f.sup.1.sub.c](z) = z + c. (2)

Definition 2. k-M set = {c| [lim.sub.n[right arrow][infinity]][f.sup.n.sub.c](0)[??] [infinity](c[member of]C, n= 1 ... [infinity])}.

Nowadays, many scholars research deeply in k-M set with many kinds of exponents. In fact, we know that the dynamics system k-M set is generalization of M set, and classic M set is actually 2-M set.

Then, because the structure of k-M set is complex, we use escape time algorithm (ETA) to create its fractal. The algorithm ETA compares [absolute value of [f.sup.n.sub.c] (c)] to a given large number N of all points c. Admittedly, a point c is in k-M set when the iteration time is more than another given number M. To explain it, we present the escape time algorithm in Algorithm 1.

In Algorithm 1, if [I.sub.z] > I, the iterations of z are convergent; else are divergent.

In fact, Algorithm 1 is an approximate algorithm because M and N cannot be determined. For example, if there exists a point c makes [absolute value of [f.sup.k.sub.c](z)(0)] < T and [absolute value of [f.sup.k+1.sub.c](z)(0)] > T or [absolute value of [f.sup.k.sub.c](z)(0)] > T and [absolute value of [f.sup.k+1.sub.c] (z)(0)] < T, we will find different results when I = k. So we cannot make sure the point c is convergent or not for ETA in these two conditions. Another problem is that when the iteration exponent is negative or complex number with negative real part, the iteration value is often changed from greatly large to greatly low or opposite. It is hardly to use ETA in this condition. So a strict proof is necessary to be given, which is used to prove convergence and divergence of k-M set in complex plane with k < 0.

Then, there is another problem in fractal creating algorithms, that is, the huge time cost. Assuming the displayed area contains M x N points, which need to compute I times in the worst condition (I is maximum iteration times), we know that the computational times C = M x N x I. This is a huge number and it needs huge time to be processed. So we have to use a distributed cooperative algorithm to decrease the computational times.

ALGORITHM 1: Escape time algorithm (ETA).

Step 1.
   Let T = escape threshold, I = max iterated number.
   Assuming [I.sub.c] = 0is iterated times of points c.
   Set [T.sub.c] = c as [f.sup.n.sub.c](z) (0) of points c.
Step 2.
   For all points c in complex plane,
   While [I.sub.c][less than or equal to] I and [absolute
   value of [T.sub.c]] < T
     [I.sub.c] = [I.sub.c] + 1. [T.sub.c] = f ([T.sub.c).]
Step 3.

Color all points c by different [I.sub.z].

For years, distributed cooperative algorithms are widely used in many areas, which indeed decrease time cost by using multiprocessors instead of single processor. Today, researchers usually use multicomputers to construct a cooperative system. Furthermore, parallel and distributed system is always used for transportation [3], estimation [4], optimization [5], and localization [6] in engineering area. Admittedly, we call them distributed cooperative transportation/ estimation/optimization/localization algorithms.

In fractal area, there are many initial iterated functions with complex structure [7, 8]. So we have to use novel iterated method to process them [9]. Admittedly, distributional method is an effective method to decrease the computational time, just like parallel and cloud environment [10,11].

In this paper, in order to decrease huge time cost which comes from fractal creating algorithms of k-M set, we present a distributed cooperative algorithm under a parallel system at first. We create k-M set with both classic ETA and novel DCETA to validate the correctness of DCETA. Besides, in order to validate the positive of DCETA, the parallel experimental results are also presented and analyzed.

Second, we prove that k-M set has strongly symmetrical properties with phase angles. In this case, we decrease the iterated time further. Meantime, we analyze these results and find the parallel properties of this distributional algorithm. It is also experimented in DCETA and the experimental results also validate our conclusions.

In conclusion, in this paper, we firstly present a separate method to reform ETA into distributional environment. Meanwhile, we analyze this novel algorithm with experimental results. Secondly, we research in properties of k-M set and find self-symmetrical regions with phase angles. Then, we present a separate method to reform ETA into distributional environment. Meanwhile, we analyze this novel algorithm with experimental results. The results also validate properties of k-M set. Finally, some Julia sets are created to validate containable properties between k-M set and the corresponding Julia sets.

The remainder of the paper is organized as follows. We proved properties of k-M set when k < 0 in Section 2. Moreover, we have their parallel experimental results and analysis in Section 3. Finally, Section 4 summarizes the main results of the paper.

In this paper, k is a negative integer, i and n are positive integers, c is a complex number, T and I are positive real numbers.

2. Distributed Cooperative ETA with Fractal Symmetrical Property

In order to run ETA in distributed system, we use SIMC in the distributional method in Algorithm 2.

Not as usual as other cooperative algorithm, DCA creates the final image with the hidden cooperative multitask nodes, which provides a part of the final image. So we cannot find the cooperative relation in DCT. In our experiment, by these two distributed cooperative methods which are presented, the parallel system is constructed with 3 same PCs. In this system, one PC is the primary node and other two are task nodes. Then, all subresults are connected in the primary node as the final result.

In this paper, we use k = -3 and -4 to process the experiment and compute a sector with center (0,0) and radius ([square root of 2]/2)s (s is a side of displayed area). For example, when k = -3, the original and improved fractal is presented in Figure 1 (with no larger than threshold 10 and no lower than threshold 0.1). Similarly, the original and improved fractal is presented in Figure 2 (with no larger than threshold 10 and no lower than threshold 0.1) when k = -4. In these figures, Theorems 4 and 6, Lemma 5, and Inference 2 are validated. In detail, we find the symmetrical property from the general views of Figures 1-2, and they validate Lemma 5 and Inference 2. Then, the escape areas are all similar-round with the escape points in Figures 1-2. They validate Theorem 4. Additionally, we have the farthest fractal area to validate Theorem 6.

In this paper, the two worker nodes compute results of the area ([rho], [theta]) with modality of polar coordinates. In the area, [rho] = ([square root of 2]/2)s, and d = [2p[pi] [absolute value of k], 2(1 + p)[pi][absolute value of k]), where p [member of] {0,1} denotes number of the two worker nodes. We present Figures 3-4 to validate the conclusion we given. In Figure 3, we present the two fractal image created by two worker nodes.


Primary node
(i) For all task nodes
      Send group message ([area.sub.i], f) to ith task nodes;
in the message, [area.sub.i] = ([x.sub.start], [x.sub.end]) x
([y.sub.start]_I], [y.sub.end_I]) denotes iterated area, and
 function f dotes the iterated mapping
(ii) While all task nodes send its result
       Connect all sub-images and display it;
(iii) Finished;
Task nodes
(i) If primary node send message ([area.sub.ii], f)
    Use ETA to create sub-image by compute all points in this
    area with iterated function f;
(ii) Send sub-image to primary node;

In Figure 4, we present the remainder of whole k-M set. Then, we find that the pseudoescape lines are the symmetry axes of k-M set. Moreover, Figure 5 is similar to Figures 3-4. It is presented to validate our conclusion with k = -4.

Then, the basic computational area is presented in Figures 6(a)-6(b) and 7(a)-7(b), which are corresponding to k = -3 and k = -4. Moreover, their symmetrical fractals of pseudo escape line are presented in Figures 6(c)-6(d) and Figures 7(c)7(d). In these figures, (a) is the original computational area with original threshold, (b) is the improved computational area with improved threshold, and (c) and (d) are the symmetrical areas with corresponding axis pseudoescape lines. Meantime, in these two examples, the expected displayed area is (-1.2,1.2) x (-1.2,1.2). So radius of the computational sector is about 1.697.

Finally, Figure 8 presents the symmetrical properties of k-M set by the two thresholds, and we validate Theorems 6 and 7 with Figures 6, 7, and 8.

3. Proof of Fractal Property in k-M Set

3.1. Correctness of the New Threshold. In this paper, we study properties when k is a negative integer from (2). At first, we give threshold and convergent properties of k-M set by Theorem 3.

Theorem 3. k-M set contains whole complex plane except countable points.

Furthermore, when k = -1, we reach Inference 1, which presents escape points of k-M set.

Inference 1. Origin is the only escape point of k-M set when k = -1.

In this way, we can analyze these countable escape points of k-M set. So when we let E = {Set of escape points}, we know that S = {[S.sub.i]}, i = 1 ... [infinity] is a partition of E, where [S.sub.i] = {c | c is a solution of [r.sup.*.sub.i] = 0}. It is because of the following:

[S.sub.i] [+ or -] [empty set],

[S.sub.i] [intersection][S.sub.j], = [empty set] when i = j,

[??] [S.sub.i] = E. (3)

Then, when we reach Theorem 4 to find all escape points which are attracting, we will found the structure of k-M set.

Theorem 4. All escape points of k-M set are attracting.

Proof. Firstly, (4) is applied to compute all escape points of k-M set:

[F.sup.i.sub.c] (0) = 0. (4)

Generalizing (4) to infinite, we have (5). It means that c is an escape point. However, using 1/[infinity] = 0, we have (6). It means that c is similar to a periodic point. Meantime, in this paper, a point c is called pseudoperiodic point when it reaches (4)-(6):

[F.sup.i+1.sub.c] (0) = [infinity], (5)

[F.sup.i+2.sub.c] (0) = c. (6)

So when applying (7), we have (8) to reach its derivative:

[f.sup.i](z) = [f.sup.i-1] ([z.sup.k] + c), (7)

([f.sup.i](z))' = [??] (f ([z.sub.j]))' ([z.sub.0] = c, [z.sub.j] = [f.sup.j] ([z.sub.0])). (8)

Then we have 9) to reform 8):


Admittedly, infinite is attracting fixed point, and zero is pseudo-2 periodic point.

So when applying (10) into 9), we have (11) when i - 1 is even or (12) when i - 1 is odd:

[z.sub.i] x [z.sub.i+1] = [z.sub.i] x ([z.sup.k.sub.i] + c) = [z.sup.k+1].sub.i] + [cz.sub.i], (10)



So when [z.sub.i] = 0 or [z.sub.i] = [infinity], (10) is infinite, and computational result of (11) is zero. Moreover, it is admittedly that computational result of (12) is zero. So we know these pseudoperiodic points are all attracting.

Theorem 4 is proved. []

Moreover, we know that escape points of k-M set are all attracting from Theorem 4. So when we use a threshold T as the threshold, we know that 1/T can also be used as a threshold in the fractal generation.

When assuming that radius of the approximately circle is e. So we have 13) from the newer threshold:

[absolute value of [](c + [epsilon]] < 1/T when [f.sup.i](c) = 0. (13)

Then, it reforms to (14) because e is tiny and ([f.sup.i](c)) = 0:

[absolute value of [epsilon] x (([f.sup.i](c))' + ([f.sup.i](c + [epsilon]))')/2] = [absolute value of [epsilon] x (([f.sup.i] (c+ [epsilon]))'/2]< 1/T. (14)

So, we have (15) to present attracting area of the ith escape point c:

[epsilon] < 2/T[absolute value of ([f.sup.i](c+[epsilon]))'] [less than or equal to] 2/T. (15)

In this case, we prove the novel threshold of k-M set. Then, the symmetrical fractal property of k-Mandelbrot set is presented in the following section.

3.2. Fractal Symmetrical Property of k-M Set. At first, when we analyze [S.sub.i] in (9)-(11), we have Lemma 5 as follows.

Lemma 5. [c.sup.*] = c c x [e.sup.2]n[pi]i/1-k)] [epsilon] [S.sub.i] when c [member of [S.sub.i] (n = 1 ... 1 - k).

Proof. Using mathematical induction, first, let i = 1; using [c.sub.*] in [r.sup.*.sub.i] = [r.sup.*.sub.0] + [([r.sup.*.sub.i-1).sup.k], we have


Then, let i = n; assuming

[r.sup.*.sub.n]([c.sup.*]) = [e.sup.2n[pi]i/(1-k)] x [r.sub.n] (17)

we have


Summarizing (16)-(18), we have (19). So when c [member of] [S.sub.i], which is equal to [r.sup.*.sub.1] (c) = 0, we know that [r.sup.*.sub.1]([c.sup.*]) = 0 :

[absolute value of [r.sup.*.sub.n]([c.sup.*])] = [r.sup.*.sub.n](c)]. (19)

It means that [c.sup.*] [member of] [S.sub.i]. Lemma 5 is proved []

In this way, we separate all [S.sub.i] to 1 - k parts, which differ from each other with phase angle 2[pi]/(1 - k).

Then, we reach Inference 2 from (19).

Inference 2. [c.sup.*] = c x [e.sup.2n[pi]i/(1-(k)] [member of] k-M set when c [member of] k-M set (n= 1 ... 1 - k).

In this case, we know that k-M sets also can be separated to 1 - k parts, which differ from each other with phase angle 2[pi]/(1 - k).

From Lemma 5 and Inference 2, we find the separation of [S.sub.i] clearly by fractal symmetry of k-M set. In our distributional strategy, [S.sub.i] is divided into 1-k parts, which differ from each other with phase angle 2[pi]/(1 - k). In this case, we separate k-M set to n nodes. The ith node computes area with phase angle (2[pi](i - 1)/n(1 - k), 2[pi]i/n(1 - k)) and we only compute area with phase angle (0,2[pi]/(1 - k)). The other area is same as the computational area and can be collaged with it.

Then, we have Theorem 6 to present the farthest "escape point" of origin, which denotes the displayed area of k-M set.

Theorem 6. In Algorithm 1, the farthest pseudoescape point of origin is at the line [theta] = (2n + 1)[pi]/(1 - k), n = 0 ... 1 - k.

Proof. Without loss of generality, we assume a point c = r x [e.sup.ix] (x > 0) as a farthest escape point. Then, we find that [absolute of (c)] has the lowest modulus than any other points with modulus r in the following by using mathematical induction.

(a) Let i = 1; [[f.sup.i](c)] is lower than other points with modulus r, where x = (2n + 1)[pi]/(1 - k) and phase angle of f(c) is same as c. Its proof is in the following.

Applying c = r x ([e.sup.ix] in (11), we have

f(c) = c x ([c.sup.k-1] + 1) = c x ([r.sup.k-1] x [e.sup.ix(k-1)] + 1), (20)

[absolute value of f(c)] = r x [r.sup.k.-1] x [e.sup.ix(k-1)] + 1]]. (21)

Admittedly, [absolute value of f(c)] reach its lowest value when x(k - 1) = (2n + 1)[pi]; applying it into (20), we find the lowest value is

[absolute value of f(c)] = r x [absolute value of [r.sup.k-1]. (22)

(b) Let i = n and assuming that [absolute [f.sup.n](c)] is lower than other points with modulus r, where x = (2n+1)[pi]/(1-k) and phase angle of [f.sup.n](c) is same as c.

(c) Let i = n + 1; [absolute value of [f.sup.i],(c)| is lower than other points with modulus r, where x = (2n + 1)n/(1 - k) and phase angle of fn+1(c) is same to c. Its proof is in the following.

Assuming that

[f.sup.n] (c) = R x c, (23)

we have

[f.sup.n+1] (c) = c x ([R.sup.k] x [c.sup.k-1] + 1). (24)

So, when x = (2n + 1)[pi]/(1 - k), we have [absolute value of [f.sup.n+1](c)] = r x [absolute value of - 1] which is the lowest of all points with modulus r. Summarizing (a)-(c), we prove that [f.sup.n](c) is lowest when its modulus is lower than T in Algorithm 1. Then when we apply Theorem 3, we have threshold of these pseudoescape points which are determined by [([f.sup.n](c)).sup.k]. So c is farther from origin when [f.sup.n](c) is lower.

It means Theorem 6 is proved. []

In this way, we know that k-M set has 1-k farthest pseudoescape points, which are at lines [theta] = (2n + 1)[pi]/(1-k) for n = 1 ~ 1 -k. In this paper, we use radii to name these 1-k lines. Then, we use Theorem 7 to present their symmetrical properties.

Theorem 7. [absolute [f.sup.i](c)] = [absolute value f.sup.i](c')](i = 1,2,...) for all points c = r x [e.sup.i[alpha]], c' = r x [e.sup.i(2[theta]-[alpha]) with [theta] = (2n + 1)[pi]/(1-k), n = 0 ... - k.

Proof. Using mathematical induction, first, let i = 1; we have

[f.sup.1] ([bar.c]) = [bar.c] = [bar.[f.sup.1](c)]. (25)

Then, let i = n, and assuming

[f.sup.n] ([bar.c]) = [bar.[f.sup.n](c)]], (26)

we have

[f.sup.n+1] ([bar.c]) = ([f.sup.n][([bar.c])).sup.k] + [bar.c]

= [([bar.f.sup.n](c)).sup.k] + [bar.c] = [([f.sup.n](c))).sup.k] + [bar.c]

= ([f.sup.n](c)).sup.k] + c = [bar.[.sup.fn]+1]] (c). (27)

Summarizing (25)-(27), we have that [f.sup.n]([bar.c]) = [bar.[f.sup.n](c)] for all n. In other words, k-M set is symmetry with the real axis. Then, when applying Lemma 5 and Inference 2, we know that k-M set is symmetric with phase angle 2n[pi]/(1 - k) (n = 1 ... 1 - k).It means

c' = r x e x [e.sup.i(2[theta]-[alpha]) = [bar.c] x [e.sup.2[theta]i]. (28)

Moreover, it is admittedly that 2[theta] = 2(2n+1)[pi]/(1-k) (n < [k/2] + 1) or 2[theta] = 2(2n+ k)[pi]/(1 - k) + 2[pi](n> [k/2]). So we have (29) by 19), (26), and (28):

[absolute value of [f.sup.n]](c')] = [[f.sup.n]([bar.c])] = [absolute value of [f.sup.n](c)]. (29)

It means Theorem 7 is proved.

In this case, we know that these pseudoescape lines are all symmetrical lines of k-M set. So the ratio of computational area is reduced to 1/2(1 - k) with original displayed area. In conclusion of Section 3.2, we know the correctness of symmetrical property in k-M set.

4. Conclusion

In this paper, we analyze k-M set with formula [f.sub.c](z) = [z.sup.k] + c (k = -1,-2,...) by using distributed cooperative algorithm. We present an algorithm DCETA to improve classic ETA to a distributed parallel system, and this novel fractal creating method has lower computations. With experimental results, we validate our conclusions.

Then, we proved the fractal property of k-M set, which contains the correctness of the novel threshold and the fractal symmetrical properties. These novel properties are improvements of [12,13].

Since we have already studied some special k-M set with many methods [14], and used k-M set in many other areas, in the next step, first, we will find some properties of k-M set, which can enhance understanding of k-M set. Then, we will use properties of k-M set into distributed parallel system to enhance its effectiveness and robustness.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.


The authors wish to thank the anonymous reviewers for their helpful comments in reviewing this paper. This work is supported by grants from Programs of Higher-level talents of Inner Mongolia University (nos. 125126, 115117), Scientific Projects of Higher School of Inner Mongolia (no. NJZY13004), Scientific Research Fund of Hunan Provincial Education Department (no. 12B023), and National Natural Science Foundation of China (nos. 61261019, 61262082).


[1] B. B. Mandelbrot, The Fractal Geometry of Nature, W. H. Freeman, San Francisco, Calif, USA, 1982.

[2] J. Falconer, Fractal Geometry: Mathematical Foundations and Applications, John Wiley & Sons, New York, NY, USA, 2nd edition, 2003.

[3] A. C. Sanderson, "A distributed algorithm for cooperative navigation among multiple mobile robots," Advanced Robotics, vol. 12, no. 4, pp. 335-349, 1997.

[4] X. C. Hao, J. Z. Wu, C. F. Chien, and M. Gen, "The cooperative estimation of distribution algorithm: a novel approach for semiconductor final test scheduling problems," Journal of Intelligent Manufacturing, pp. 1-13, 2013.

[5] I. Necoara and D. Clipici, "Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC," Journal of Process Control, vol. 23, no. 3, pp. 243-253, 2013.

[6] S. Liu, X.-J. Che, and Z.-X. Wang, "Existence domain analysis and numerical algorithm of fixed point for generalized 3x +1 function T(x)," Acta Electronica Sinica, vol. 39, no. 10, pp. 22822287, 2011 (Chinese).

[7] S. Liu, W. Fu, W. Zhao, J. Zhou, and Q. Li, "A novel fusion method by static and moving facial capture," Mathematical Problems in Engineering, vol. 2013, Article ID 503924, 6 pages, 2013.

[8] S. Liu and Z. Wang, "Fixed point and fractal images for a generalized approximate 3x +1 function," Journal of Computer-Aided Design and Computer Graphics, vol. 21, no. 12, pp. 1740-1744, 2009 (Chinese).

[9] S. Liu, X. Che, and Z. Wang, "Improvement of escape time algorithm by no-escape-point," Journal of Computers, vol. 6, no. 8, pp. 1648-1653, 2011.

[10] M. Liu, S. Liu, W. Fu et al., "Distributional escape time algorithm based on generalized fractal sets in cloud environment," Chinese Journal of Electronics. In press.

[11] S. Liu, W. Fu, H. Deng, C. Lan, and J. Zhou, "Distributional fractal creating algorithm in parallel environment," International Journal of Distributed Sensor Networks, vol. 2013, Article ID 281707, 8 pages, 2013.

[12] N. Chen and W. Zhu, "Constructed general high-order Mandelbrot fractal images and symmetrical escape time algorithm," Journal of Northeastern University: Natural Science, vol. 17, no. 3, pp. 225-229.

[13] X. Liu and W. Zhu, "Constructed M-set and filled J-set by accelerative escape time algorithm of combination," Journal of Northeastern University: Natural Science, vol. 18, no. 4, pp. 413416.

[14] S. Liu, X. Cheng, C. Lan et al., "Fractal property of generalized M-set with rational number exponent," Applied Mathematics and Computation, vol. 220, pp. 668-675, 2013.

Gelan Yang (1,2) and Shuai Liu (2,3)

(1) College of Information Science and Technology, Hunan City University, Yiyang 413000, China

(2) College of Computer Science, Inner Mongolia University, Hohhot 010012, China

(3) School of Physical Science and Technology, Inner Mongolia University, Hohhot 010012, China

Correspondence should be addressed to Shuai Liu;

Received 6 December 2013; Accepted 19 February 2014; Published 8 May 2014

Academic Editor: Yong Jin

Copyright [c] 2014 G. Yang and S. Liu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
COPYRIGHT 2014 Sage Publications, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Yang, Gelan; Liu, Shuai
Publication:International Journal of Distributed Sensor Networks
Article Type:Report
Date:Jan 1, 2014
Previous Article:An energy-efficient collaborative target tracking framework in distributed wireless sensor networks.
Next Article:Node replication attacks in mobile wireless sensor network: a survey.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters