Rational maps: True shape

  • 3 Replies
  • 177 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 543
« on: October 15, 2019, 08:44:01 PM »
"rmapTSA"

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/fractal-mathematics-and-new-theories/28/rational-maps-true-shape/3134/

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 543
« 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

  • *
  • Fractal Frankfurter
  • *
  • Posts: 543
« 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

  • *
  • Fractal Frankfurter
  • *
  • Posts: 543
« 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.



clip
Other Polynomial and Rational Maps

Started by pauldelbrot on Image Threads

75 Replies
3140 Views
Last post Yesterday at 10:28:37 AM
by pauldelbrot
clip
3d Julia sets: True shape

Started by marcm200 on Image Threads

31 Replies
847 Views
Last post January 20, 2020, 11:42:23 AM
by marcm200
xx
True shape/IA 2D/3D Julia set source code

Started by marcm200 on Programming

12 Replies
488 Views
Last post January 21, 2020, 01:35:39 PM
by marcm200
xx
Julia sets: True shape and escape time

Started by marcm200 on Fractal Mathematics And New Theories

121 Replies
3827 Views
Last post Yesterday at 07:01:44 PM
by marcm200
clip
True-shape based C++ oracle for the int-/exterior of Julia sets

Started by marcm200 on Programming

6 Replies
262 Views
Last post August 23, 2019, 10:47:10 AM
by marcm200