June  2016, 3(2): 113-137. doi: 10.3934/jcd.2016006

Rigorous bounds for polynomial Julia sets

1. 

IMPA, Rio de Janeiro, Brazil, Brazil

2. 

Instituto de Computacão, UNICAMP, Campinas, Brazil

3. 

Faculdade de Informática, PUC-RS, Porto Alegre, Brazil

Received  March 2016 Revised  August 2016 Published  November 2016

We present an algorithm for computing images of polynomial Julia sets that are reliable in the sense that they carry mathematical guarantees against sampling artifacts and rounding errors in floating-point arithmetic. We combine cell mapping based on interval arithmetic with label propagation in graphs to avoid function iteration and rounding errors. As a result, our algorithm avoids point sampling and can reliably classify entire rectangles in the complex plane as being on either side of the Julia set. The union of the rectangles that cannot be so classified is guaranteed to contain the Julia set. Our algorithm computes a refinable quadtree decomposition of the complex plane adapted to the Julia set which can be used for rendering and for approximating geometric properties such as the area of the filled Julia set and the fractal dimension of the Julia set.
Citation: Luiz Henrique de Figueiredo, Diego Nehab, Jorge Stolfi, João Batista S. de Oliveira. Rigorous bounds for polynomial Julia sets. Journal of Computational Dynamics, 2016, 3 (2) : 113-137. doi: 10.3934/jcd.2016006
References:
[1]

Z. Arai, On hyperbolic plateaus of the Hénon map,, Experimental Mathematics, 16 (2007), 181.  doi: 10.1080/10586458.2007.10128992.  Google Scholar

[2]

P. Blanchard, Complex analytic dynamics on the Riemann sphere,, Bulletin of the American Mathematical Society, 11 (1984), 85.  doi: 10.1090/S0273-0979-1984-15240-6.  Google Scholar

[3]

B. Branner, The Mandelbrot set,, in Amer. Math. Soc., 39 (1989), 75.  doi: 10.1090/psapm/039/1010237.  Google Scholar

[4]

M. Braverman, Hyperbolic Julia sets are poly-time computable,, Electronic Notes in Theoretical Computer Science, 120 (2005), 17.  doi: 10.1016/j.entcs.2004.06.031.  Google Scholar

[5]

M. Braverman and M. Yampolsky, Computability of Julia Sets,, Springer-Verlag, (2009).   Google Scholar

[6]

R. Carniel, A quasi-cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm,, Applied Numerical Mathematics, 15 (1994), 133.  doi: 10.1016/0168-9274(94)00016-6.  Google Scholar

[7]

L. H. de Figueiredo and J. Stolfi, Affine arithmetic: concepts and applications,, Numerical Algorithms, 37 (2004), 147.  doi: 10.1023/B:NUMA.0000049462.70970.b6.  Google Scholar

[8]

M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors,, Numerische Mathematik, 75 (1997), 293.  doi: 10.1007/s002110050240.  Google Scholar

[9]

M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems,, in Handbook of dynamical systems, 2 (2002), 221.  doi: 10.1016/S1874-575X(02)80026-1.  Google Scholar

[10]

R. L. Devaney and L. Keen (eds.), Chaos and Fractals: The Mathematics behind the Computer Graphics,, Proceedings of Symposia in Applied Mathematics 39, (1989).   Google Scholar

[11]

A. Douady, Does a Julia set depend continuously on the polynomial?,, in Complex Dynamical Systems: The Mathematics Behind the Mandelbrot and Julia Sets (ed. R. L. Devaney), 49 (1994), 91.  doi: 10.1090/psapm/049/1315535.  Google Scholar

[12]

M. B. Durkin, The accuracy of computer algorithms in dynamical systems,, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 1 (1991), 625.  doi: 10.1142/S0218127491000452.  Google Scholar

[13]

Z. Galias, Rigorous investigation of the Ikeda map by means of interval arithmetic,, Nonlinearity, 15 (2002), 1759.  doi: 10.1088/0951-7715/15/6/304.  Google Scholar

[14]

E. Grassmann and J. Rokne, The range of values of a circular complex polynomial over a circular complex interval,, Computing, 23 (1979), 139.  doi: 10.1007/BF02252094.  Google Scholar

[15]

T. H. Gronwall, Some remarks on conformal representation,, Annals of Mathematics, 16 (): 72.  doi: 10.2307/1968044.  Google Scholar

[16]

S. L. Hruska, Constructing an expanding metric for dynamical systems in one complex variable,, Nonlinearity, 18 (2005), 81.  doi: 10.1088/0951-7715/18/1/005.  Google Scholar

[17]

S. L. Hruska, Rigorous numerical studies of the dynamics of polynomial skew products of $C^2$,, in Complex dynamics, (2006), 85.  doi: 10.1090/conm/396/07395.  Google Scholar

[18]

C. S. Hsu, Cell-to-cell Mapping: A Method of Global Analysis for Nonlinear Systems,, Springer-Verlag, (1987).  doi: 10.1007/978-1-4757-3892-6.  Google Scholar

[19]

C. S. Hsu, Global analysis by cell mapping,, International Journal of Bifurcations and Chaos, 2 (1992), 727.  doi: 10.1142/S0218127492000422.  Google Scholar

[20]

O. Junge, Rigorous discretization of subdivision techniques,, in International Conference on Differential Equations, (1999), 916.   Google Scholar

[21]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[22]

L. Keen, Julia sets,, in Proc. Sympos. Appl. Math., 39 (1989), 57.  doi: 10.1090/psapm/039/1010236.  Google Scholar

[23]

V. Kreinovich, Interval software,, , ().   Google Scholar

[24]

D. Michelucci and S. Foufou, Interval-based tracing of strange attractors,, International Journal of Computational Geometry & Applications, 16 (2006), 27.  doi: 10.1142/S0218195906001914.  Google Scholar

[25]

J. Milnor, Remarks on iterated cubic maps,, Experimental Mathematics, 1 (1992), 5.   Google Scholar

[26]

J. Milnor, Dynamics in One Complex Variable, vol. 160 of Annals of Mathematics Studies,, 3rd edition, (2006).   Google Scholar

[27]

R. E. Moore, Interval Analysis,, Prentice-Hall, (1966).   Google Scholar

[28]

R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis,, SIAM, (2009).  doi: 10.1137/1.9780898717716.  Google Scholar

[29]

R. P. Munafo, Roundoff error,, , (1996), 2015.   Google Scholar

[30]

D. Nehab and H. Hoppe, A fresh look at generalized sampling,, Foundations and Trends in Computer Graphics and Vision, 8 (2014), 1.  doi: 10.1561/0600000053.  Google Scholar

[31]

G. Osipenko, Dynamical Systems, Graphs, and Algorithms, vol. 1889 of Lecture Notes in Mathematics,, Springer-Verlag, (2007).   Google Scholar

[32]

A. Paiva, L. H. de Figueiredo and J. Stolfi, Robust visualization of strange attractors using affine arithmetic,, Computers & Graphics, 30 (2006), 1020.  doi: 10.1016/j.cag.2006.08.016.  Google Scholar

[33]

H.-O. Peitgen and P. H. Richter, The Beauty of Fractals: Images of Complex Dynamical Systems,, Springer-Verlag, (1986).  doi: 10.1007/978-3-642-61717-1.  Google Scholar

[34]

H.-O. Peitgen and D. Saupe (eds.), The Science of Fractal Images,, Springer-Verlag, (1988).  doi: 10.1007/978-1-4612-3784-6.  Google Scholar

[35]

M. S. Petković and L. D. Petković, Complex Interval Arithmetic and Its Applications,, Wiley-VCH Verlag, (1998).   Google Scholar

[36]

R. Rettinger, A fast algorithm for {Julia} sets of hyperbolic rational functions,, Electronic Notes in Theoretical Computer Science, 120 (2005), 145.  doi: 10.1016/j.entcs.2004.06.041.  Google Scholar

[37]

R. Rettinger and K. Weihrauch, The computational complexity of some Julia sets,, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), (2003), 177.  doi: 10.1145/780542.780570.  Google Scholar

[38]

J. Rokne, The range of values of a complex polynomial over a complex interval,, Computing, 22 (1979), 153.  doi: 10.1007/BF02253127.  Google Scholar

[39]

D. Ruelle, Repellers for real analytic maps,, Ergodic Theory and Dynamical Systems, 2 (1982), 99.  doi: 10.1017/S0143385700009603.  Google Scholar

[40]

S. M. Rump and M. Kashiwagi, Implementation and improvements of affine arithmetic,, Nonlinear Theory and Its Applications, 6 (2015), 341.   Google Scholar

[41]

H. Samet, The quadtree and related hierarchical data structures,, Computing Surveys, 16 (1984), 187.  doi: 10.1145/356924.356930.  Google Scholar

[42]

D. Saupe, Efficient computation of Julia sets and their fractal dimension,, Physica D, 28 (1987), 358.  doi: 10.1016/0167-2789(87)90024-8.  Google Scholar

[43]

N. Steinmetz, Rational Iteration: Complex Analytic Dynamical Systems,, Walter de Gruyter & Co., (1993).  doi: 10.1515/9783110889314.  Google Scholar

[44]

C. M. Stroh, Julia Sets of Complex Polynomials and Their Implementation on the Computer,, Master's thesis, (1997).   Google Scholar

[45]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM Journal on Computing, 1 (1972), 146.  doi: 10.1137/0201010.  Google Scholar

[46]

W. Tucker, The Lorenz attractor exists,, C. R. Acad. Sci. Paris Sér. I Math., 328 (1999), 1197.  doi: 10.1016/S0764-4442(99)80439-X.  Google Scholar

[47]

J. Tupper, Reliable two-dimensional graphing methods for mathematical formulae with two free variables,, in Proceedings of SIGGRAPH '01, (2001), 77.  doi: 10.1145/383259.383267.  Google Scholar

show all references

References:
[1]

Z. Arai, On hyperbolic plateaus of the Hénon map,, Experimental Mathematics, 16 (2007), 181.  doi: 10.1080/10586458.2007.10128992.  Google Scholar

[2]

P. Blanchard, Complex analytic dynamics on the Riemann sphere,, Bulletin of the American Mathematical Society, 11 (1984), 85.  doi: 10.1090/S0273-0979-1984-15240-6.  Google Scholar

[3]

B. Branner, The Mandelbrot set,, in Amer. Math. Soc., 39 (1989), 75.  doi: 10.1090/psapm/039/1010237.  Google Scholar

[4]

M. Braverman, Hyperbolic Julia sets are poly-time computable,, Electronic Notes in Theoretical Computer Science, 120 (2005), 17.  doi: 10.1016/j.entcs.2004.06.031.  Google Scholar

[5]

M. Braverman and M. Yampolsky, Computability of Julia Sets,, Springer-Verlag, (2009).   Google Scholar

[6]

R. Carniel, A quasi-cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm,, Applied Numerical Mathematics, 15 (1994), 133.  doi: 10.1016/0168-9274(94)00016-6.  Google Scholar

[7]

L. H. de Figueiredo and J. Stolfi, Affine arithmetic: concepts and applications,, Numerical Algorithms, 37 (2004), 147.  doi: 10.1023/B:NUMA.0000049462.70970.b6.  Google Scholar

[8]

M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors,, Numerische Mathematik, 75 (1997), 293.  doi: 10.1007/s002110050240.  Google Scholar

[9]

M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems,, in Handbook of dynamical systems, 2 (2002), 221.  doi: 10.1016/S1874-575X(02)80026-1.  Google Scholar

[10]

R. L. Devaney and L. Keen (eds.), Chaos and Fractals: The Mathematics behind the Computer Graphics,, Proceedings of Symposia in Applied Mathematics 39, (1989).   Google Scholar

[11]

A. Douady, Does a Julia set depend continuously on the polynomial?,, in Complex Dynamical Systems: The Mathematics Behind the Mandelbrot and Julia Sets (ed. R. L. Devaney), 49 (1994), 91.  doi: 10.1090/psapm/049/1315535.  Google Scholar

[12]

M. B. Durkin, The accuracy of computer algorithms in dynamical systems,, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 1 (1991), 625.  doi: 10.1142/S0218127491000452.  Google Scholar

[13]

Z. Galias, Rigorous investigation of the Ikeda map by means of interval arithmetic,, Nonlinearity, 15 (2002), 1759.  doi: 10.1088/0951-7715/15/6/304.  Google Scholar

[14]

E. Grassmann and J. Rokne, The range of values of a circular complex polynomial over a circular complex interval,, Computing, 23 (1979), 139.  doi: 10.1007/BF02252094.  Google Scholar

[15]

T. H. Gronwall, Some remarks on conformal representation,, Annals of Mathematics, 16 (): 72.  doi: 10.2307/1968044.  Google Scholar

[16]

S. L. Hruska, Constructing an expanding metric for dynamical systems in one complex variable,, Nonlinearity, 18 (2005), 81.  doi: 10.1088/0951-7715/18/1/005.  Google Scholar

[17]

S. L. Hruska, Rigorous numerical studies of the dynamics of polynomial skew products of $C^2$,, in Complex dynamics, (2006), 85.  doi: 10.1090/conm/396/07395.  Google Scholar

[18]

C. S. Hsu, Cell-to-cell Mapping: A Method of Global Analysis for Nonlinear Systems,, Springer-Verlag, (1987).  doi: 10.1007/978-1-4757-3892-6.  Google Scholar

[19]

C. S. Hsu, Global analysis by cell mapping,, International Journal of Bifurcations and Chaos, 2 (1992), 727.  doi: 10.1142/S0218127492000422.  Google Scholar

[20]

O. Junge, Rigorous discretization of subdivision techniques,, in International Conference on Differential Equations, (1999), 916.   Google Scholar

[21]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[22]

L. Keen, Julia sets,, in Proc. Sympos. Appl. Math., 39 (1989), 57.  doi: 10.1090/psapm/039/1010236.  Google Scholar

[23]

V. Kreinovich, Interval software,, , ().   Google Scholar

[24]

D. Michelucci and S. Foufou, Interval-based tracing of strange attractors,, International Journal of Computational Geometry & Applications, 16 (2006), 27.  doi: 10.1142/S0218195906001914.  Google Scholar

[25]

J. Milnor, Remarks on iterated cubic maps,, Experimental Mathematics, 1 (1992), 5.   Google Scholar

[26]

J. Milnor, Dynamics in One Complex Variable, vol. 160 of Annals of Mathematics Studies,, 3rd edition, (2006).   Google Scholar

[27]

R. E. Moore, Interval Analysis,, Prentice-Hall, (1966).   Google Scholar

[28]

R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis,, SIAM, (2009).  doi: 10.1137/1.9780898717716.  Google Scholar

[29]

R. P. Munafo, Roundoff error,, , (1996), 2015.   Google Scholar

[30]

D. Nehab and H. Hoppe, A fresh look at generalized sampling,, Foundations and Trends in Computer Graphics and Vision, 8 (2014), 1.  doi: 10.1561/0600000053.  Google Scholar

[31]

G. Osipenko, Dynamical Systems, Graphs, and Algorithms, vol. 1889 of Lecture Notes in Mathematics,, Springer-Verlag, (2007).   Google Scholar

[32]

A. Paiva, L. H. de Figueiredo and J. Stolfi, Robust visualization of strange attractors using affine arithmetic,, Computers & Graphics, 30 (2006), 1020.  doi: 10.1016/j.cag.2006.08.016.  Google Scholar

[33]

H.-O. Peitgen and P. H. Richter, The Beauty of Fractals: Images of Complex Dynamical Systems,, Springer-Verlag, (1986).  doi: 10.1007/978-3-642-61717-1.  Google Scholar

[34]

H.-O. Peitgen and D. Saupe (eds.), The Science of Fractal Images,, Springer-Verlag, (1988).  doi: 10.1007/978-1-4612-3784-6.  Google Scholar

[35]

M. S. Petković and L. D. Petković, Complex Interval Arithmetic and Its Applications,, Wiley-VCH Verlag, (1998).   Google Scholar

[36]

R. Rettinger, A fast algorithm for {Julia} sets of hyperbolic rational functions,, Electronic Notes in Theoretical Computer Science, 120 (2005), 145.  doi: 10.1016/j.entcs.2004.06.041.  Google Scholar

[37]

R. Rettinger and K. Weihrauch, The computational complexity of some Julia sets,, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), (2003), 177.  doi: 10.1145/780542.780570.  Google Scholar

[38]

J. Rokne, The range of values of a complex polynomial over a complex interval,, Computing, 22 (1979), 153.  doi: 10.1007/BF02253127.  Google Scholar

[39]

D. Ruelle, Repellers for real analytic maps,, Ergodic Theory and Dynamical Systems, 2 (1982), 99.  doi: 10.1017/S0143385700009603.  Google Scholar

[40]

S. M. Rump and M. Kashiwagi, Implementation and improvements of affine arithmetic,, Nonlinear Theory and Its Applications, 6 (2015), 341.   Google Scholar

[41]

H. Samet, The quadtree and related hierarchical data structures,, Computing Surveys, 16 (1984), 187.  doi: 10.1145/356924.356930.  Google Scholar

[42]

D. Saupe, Efficient computation of Julia sets and their fractal dimension,, Physica D, 28 (1987), 358.  doi: 10.1016/0167-2789(87)90024-8.  Google Scholar

[43]

N. Steinmetz, Rational Iteration: Complex Analytic Dynamical Systems,, Walter de Gruyter & Co., (1993).  doi: 10.1515/9783110889314.  Google Scholar

[44]

C. M. Stroh, Julia Sets of Complex Polynomials and Their Implementation on the Computer,, Master's thesis, (1997).   Google Scholar

[45]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM Journal on Computing, 1 (1972), 146.  doi: 10.1137/0201010.  Google Scholar

[46]

W. Tucker, The Lorenz attractor exists,, C. R. Acad. Sci. Paris Sér. I Math., 328 (1999), 1197.  doi: 10.1016/S0764-4442(99)80439-X.  Google Scholar

[47]

J. Tupper, Reliable two-dimensional graphing methods for mathematical formulae with two free variables,, in Proceedings of SIGGRAPH '01, (2001), 77.  doi: 10.1145/383259.383267.  Google Scholar

[1]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[2]

Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323

[3]

Tin Phan, Bruce Pell, Amy E. Kendig, Elizabeth T. Borer, Yang Kuang. Rich dynamics of a simple delay host-pathogen model of cell-to-cell infection for plant virus. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 515-539. doi: 10.3934/dcdsb.2020261

[4]

Jesús A. Álvarez López, Ramón Barral Lijó, John Hunton, Hiraku Nozawa, John R. Parker. Chaotic Delone sets. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021016

[5]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049

[6]

Riccarda Rossi, Ulisse Stefanelli, Marita Thomas. Rate-independent evolution of sets. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 89-119. doi: 10.3934/dcdss.2020304

[7]

Jian-Xin Guo, Xing-Long Qu. Robust control in green production management. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021011

[8]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[9]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[10]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[11]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

[12]

Lisa Hernandez Lucas. Properties of sets of Subspaces with Constant Intersection Dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052

[13]

H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433

[14]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020381

[15]

Tinghua Hu, Yang Yang, Zhengchun Zhou. Golay complementary sets with large zero odd-periodic correlation zones. Advances in Mathematics of Communications, 2021, 15 (1) : 23-33. doi: 10.3934/amc.2020040

[16]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[17]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 61-79. doi: 10.3934/dcdsb.2020351

[18]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113

[19]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

[20]

Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096

 Impact Factor: 

Metrics

  • PDF downloads (54)
  • HTML views (0)
  • Cited by (0)

[Back to Top]