• May 08, 2021, 04:11:47 AM

Login with username, password and session length

Author Topic:  Rational maps: True shape  (Read 733 times)

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • 3d
  • ****
  • Posts: 959
Rational maps: True shape
« on: October 15, 2019, 08:44:01 PM »

I am trying to extend the Figueiredo cell-mapping/interval arithmetics method to rational maps p/q.

The extension itself was rather straightforward - except for two major points: Afaik, rational Julia sets do not necessarily need to be contained in a finite region, so exterior is not known beforehand - and dividing intervals with dyadic endpoints does not necessarily (and most of the times will not) result in a representable interval, so correct (outward) rounding needs to take place.

As for the non-finiteness, I currently am only interested in finding squares whose orbits are bounded, so the resulting image only has two colors: black for interior - and gray for "could not yet be judged as interior". I use a somewhat guided value n (see technical details below) to compute the n-square. If an orbit escapes that rectangle, its starting square is colored "gray-forever-at-that-refinement-level". Interior is detected by finding invariant sets of squares who keep to themselves under one rational iteration (the first method I implemented for the polynomial TSA case).

As for rounding the interval's end points, I currently use a published library for interval arithmetics. I tried several - the first that I could install and get to work was Kashiwagi's kv library combined with boost (1.62).

Here are the first, preliminary results:

First image is - as always - the basilica in the 2-square. I used z²-1 as the enumerator polynomial and the constant 1 polynomial as denominator just to check the routines. The result shows the interior (left side). I compared those interior pixels with a complete image computed with the standard TSA algorithm (right side). The rmapTSA's interior pixels were in deed interior - fortunately.

The 2nd example is the simple degree 3 rational f(z)=z²/(z3-1). Left side is the rmapTSA output in the 2-square, right side is a point-sampled "control" (gray pixels are not bounded, colored and black pixels are bounded, blue being starting points where the orbit stays in the 1-square, yellow in the 2-square, turquois in the 4-square).

The next steps now are:
  • computing several already published images of rational maps to qualitatively validate the implementation
  • trying the basin of attraction method from the polynomial TSA
  • optimization - time requirement, even for small 1k images, is pretty big

Technical details:
  • The bounding boxes for the two polynomials p and q are calculated with the normal routines I use in the standard TSA as for those I can calculate beforehand whether the datatype provides sufficient accuracy.
  • Dividing two bounding boxes, i.e. complex intervals is implemented using the classic expansion: (A+i*B) / (C+i*D) = (A+i*B) / (C+i*D) * (C-i*D) / (C-i*D) = (A+i*B)*(C-i*D) / (C*C+D*D), the denominator being a simple real interval.
  • In the point-sampled image I try to find two regions: one that contains quite a substantial amount of non-bounded points and one that contains only bounded points. Those are then checked primarily in the rmapTSA to see which one needs less time.

Linkback: https://fractalforums.org/index.php?topic=3134.0

Offline marcm200

  • 3d
  • ****
  • Posts: 959
Re: Rational maps: True shape
« Reply #1 on: October 18, 2019, 09:38:39 AM »
"Traveling salesman"

Precomputing the bounding boxes and storing them in memory sped the computation up about 4-fold - however at the cost of huge memory consumption - I now need 8 bytes per pixel instead of 2 bits as in the polynomial case (where storing was not beneficial as data shuffling from memory into cache was slower than computing the bounding boxes as needed).

Below is an example of degree 3: \( \frac{i\cdot z^2-z+2}{2\cdot z^3+3\cdot z^2-i\cdot z+i} \) in the 4-square - it looks like a tour of a traveling salesman, trying to avoid the gray regions.

Left is the rmapTSA output (level 15, trustworthily downscaled 16-fold, red pixels mean bounding box's denominator contains zero), right side is a point-sampled version (blue/yellow/turquois/black: orbits stay in the 1/2/4/10-square, gray travels beyond).

Interesting to compare are the cloverleaf structures which give me confidence that the rather complicated bounding box formulas (automatically generated) are correct.

Offline marcm200

  • 3d
  • ****
  • Posts: 959
Re: Rational maps: True shape
« Reply #2 on: October 20, 2019, 11:09:52 AM »
"Basins of attraction - or not?"

I tried the basin of attraction method with the Newton map for p(z)=z^3-2z+2, N(z)=(2z^3-2) / (3z^2-2).

Left image below is the rmapTSA output in the 2-square (contains all the roots), right is the point-sampled control using the universal set of starting points (see forum link, the example equation was also from that paper, fig. 1) (color description below).

At first they looked qualitatively identical, so I will now try to detect immediate basins and the periodicity. And the rmapTSA did detect 4 cycles, the yellow one being an attracting non-root 2 cycle.

But since up to now I always worked with finitely bounded interior regions - and purple e.g. in the Newton map extends to infinity, I was wondering:

Can it happen in rational maps that e.g. here purple and turquois will flow together far far away from the origin and are in fact the same basin?

I think here in the Newton map this won't happen as the large regions are the immediate basins of the roots, so they are disjoint, but in the general rational case?

My basin detection method looks for geometrically disjoint regions of interior cells. If for two regions D, E there is no path from D to E (using all interior cells) and vice versa, they are considered two distinct basins of attraction. This works well in case the interior is finitely bounded, but I am not sure about the dynamics of rational maps.

I'm mainly focusing on Newton maps - as I'd like to find the immediate basins for the roots and finally the roots themselves. Dynamics of the channels (above paper) is tame outside the Lagrange, so maybe if I stick to that large a square to compute, the method will work (?).

Technical note:
  • Colors left image: basins of attraction/partitions colored, gray not detectable as interior, red: not evaluable since denominator intervals contain zero.
  • Colors right image: root-attracting basins colored, black=non root-convergent, exaggerated red squares indicate the numerically found roots.

Offline marcm200

  • 3d
  • ****
  • Posts: 959
Re: Rational maps: True shape
« Reply #3 on: October 26, 2019, 10:09:47 AM »
I implemented the periodicity routine from the polynomial TSA algorithm to determine the immediate basins of some Newton maps.

Here I used the degree 5 example from gerrit's image thread which has an attracting cycle 0 -> 1 -> 0, so non-root converging areas are present.

N(z)=(4*z^5-4) / (5*z^4-4) for the polynomial f(z)=z^5-4*z+4.

First image shows the immediate basins in the 4-square where all the (numerically found) roots lie deep within. Purple is the period-2-non-root cycle, zooming in shows the smaller periodic point at 1+0i (pixels ~2560,2048), black is bounded but not in any immediate basin and gray is undetermined.

Second image shows in a heat-map fashion (non-trustworthily downscaled 2-fold) how often a pixel was hit by  a bounding box in one iteration (anti-buddha style, only interior pixels were used as starting points). The white hot regions correspond to the roots (small black rectangles afterwards introduced into the image).

It's very interesting and still unexpected to me that the roots are so prominently visited by just considering one iteration. I read that Newton's method converges quite fast, so maybe that's (part of) an explanation: large steps to the destination and no detours.

Offline Adam Majewski

  • Fractal Frogurt
  • ******
  • Posts: 472

Offline marcm200

  • 3d
  • ****
  • Posts: 959
Re: Rational maps: True shape
« Reply #5 on: March 14, 2021, 09:36:02 AM »
(The function below is not actually a rational, but as I do not have a valid escape radius - if existent, I used the rmapTSA from here to detect interior)

Non-integer iteration (forum link, 2) for:

P(m,z,c) := P(m-1,z,c)^2+c~\text{for m}\geq 1 \\
\text{else} := |z|^{1+m}
\cdot e^{i\cdot arg(z)\cdot (1+m)}

with the angle in \( 0..2\cdot\pi \).

t=5.5, c=-820/1024 at L10 (first image) in the 2-square. A pixel represents a small complex square of width 4/2^10. Black denotes the underlying complex intervals are all bounded, pale yellow is bounded (definite) and may construct 2-cycle (caution!).

While the interior is detected correctly (it finds regions that only map among each other) - but could grow to a completely different shape as long as no exterior can be detected, my first thought about the cycle was: The periodicity routine relies on the property for polynomial Julia/Fatou sets, that one Fatou component maps to one other (and does not diverge to two or more) - is this cycle real?

And indeed, one llevel later at L11, there emerged a geometrically connected component (which in polynomial sets is a Fatou component), that contains points that map to two different other geometrically connected blobs (second image, arrow points to the particular component, blue circumferenced, the red lines go to the two target blobs). Maybe this is the results of the jumps, Yodadude2003 mentioned in his thread.

I will next follow the orbit of several individual points in the blue blob with maxima or a manual computation to verify that they actually land in very different locations.

However, I would really like to see an explicit equation for the middle, rectangular main structure's boundary (supposing the shape doesn't grow into something simple in the limit). Maybe there is a method to get Fatou component boundaries, like e.g. the resultant method for hyperbolic components in the Mset? (My literature search has not revealed anything so far).

Does anyone know of such a method/article?

Other Polynomial and Rational Maps

Started by pauldelbrot on Image Threads

139 Replies
Last post April 24, 2021, 05:52:23 PM
by pauldelbrot
Buried components in rational maps

Started by marcm200 on Fractal Mathematics And New Theories

1 Replies
Last post April 10, 2020, 03:45:16 PM
by pauldelbrot
3d Julia sets: True shape

Started by marcm200 on Image Threads

31 Replies
Last post January 20, 2020, 11:42:23 AM
by marcm200
Strange attractors: True shape

Started by marcm200 on Fractal Mathematics And New Theories

2 Replies
Last post June 09, 2020, 09:39:05 AM
by marcm200
True shape/IA 2D/3D Julia set source code

Started by marcm200 on Programming

15 Replies
Last post July 05, 2020, 11:46:53 AM
by marcm200