• December 03, 2021, 07:55:42 AM

Author Topic:  Another solution to perturbation glitches  (Read 1570 times)

0 Members and 1 Guest are viewing this topic.

Offline claude

  • 3f
  • ******
  • Posts: 2081
    • mathr.co.uk
Re: Another solution to perturbation glitches
« Reply #45 on: November 19, 2021, 06:06:59 PM »
I'm using linear approximation. It's similar to bivariate series approximation, but only linear terms are used.

Bivariate linear would be of the form (z, c) -> (U z + V c + W, c), but that's a bad approximation when e.g. a region surrounding 0 is squared (it wraps twice around now).

Analyse the reference orbit with interval arithmetics to know the iterations where z may be near a critical point, at which points do rebasing (if necessary) and one full non-linear iteration. In between, skip until the next near-critical-point iteration with bivariate linear approximation.

Store tables in memory indexed by the exponent of the distance squared between z and each critical point, containing the number of iterations that can be skipped by bivariate linear approximation and the bivariate linear approximation coefficients.  Then the iteration loop becomes something like this:

Code: [Select]
c = coordinates of pixel - coordinates of reference
z = 0+0i
iteration = 0
reference iteration = 0
while (iterations < maxiters)
{
  /* do one full non-linear perturbed iteration */
  z := 2 (Z[reference iteration] + z) z + c
  iteration++
  reference iteration++
  /* check escape */
  if |Z[reference iteration] + z|^2  > escape radius^2
  {
    break
  }
  if |Z[reference iteration] + z|^2 < |z|^2
  {
     /* rebase */
     z := Z[reference iteration] + z
     reference iteration := 0
   }
  else
  {
    /* bivariate linear approximation */
    T := lookup table [ exponent(|z|^2) ]
    z := T.U * z + T.V * c + T.W
    iterations += T.iterations
    reference iterations += T.iterations
  }
}

I haven't tested this yet, so it could be nonsense...

Offline claude

  • 3f
  • ******
  • Posts: 2081
    • mathr.co.uk
Re: Another solution to perturbation glitches
« Reply #46 on: November 23, 2021, 11:56:33 AM »
I got bivariate linear approximation working in some test code. Speedup ranges from 50% to 27x compared to perturbation alone in a couple of test locations.  One reference, no need for multiple passes or risk of series approximation overskipping.  Implementation is double precision, rescaling to be investigated.

Version now https://code.mathr.co.uk/fractal-bits/tree/cb104c7f0a0ea43423a0ff99ac4e0b7d79a0a375:/mandelbla
Latest version https://code.mathr.co.uk/fractal-bits/tree/refs/heads/main:/mandelbla
Code: [Select]
git clone https://code.mathr.co.uk/fractal-bits.git
EDIT performance is not as good as I'd hoped: Dinkydau's Evolution of Trees at 1920x1080 takes 1m21s with kf-2.15.4 (23 refs), 37s with kf-2.15.5 wip (1ref), 6mins with mandelbla (only 3x speedup over plain perturbation).  kf uses ~30 SA terms at this resolution...

Perhaps a hybrid approach would work, using bivariate linear approximation to accelerate series approximation coefficient generation... but then overskipping becomes a risk again...

Probably I'm doing something wrong and I could skip more iterations using BLA somehow.  Candidate for an error is using this escape test for stopping BLA, it's ok as long as  |delta z_{m p}| < 2 / (product_k=1^{p-1} 2 Z_k)   for period p.  Maybe this radius is wrong...

EDIT2
for Fractal Universe's hard location in this thread, it seems BLA does better than non-subdivided SA could do, because the average BLA skip iterations ("bla iters per pixel") is larger than the minimum iterations in the image

Code: [Select]
ReferenceIterations = 43292335
Periods: 152 456 912 14896 44688 655424 4378360 43292334
[ 3.90239e-275 43292333   43292333   43292333   43292333   43292333   43292333   4378359   r r r r r r r r r r r r r r r r r r r 292266201 ]
...................................................................................................
291848352.000000 minimum iterations
2121324367.000000 maximum iterations
340542368.872444 iters per pixel
296402167.541570 bla iters per pixel
44140200.330874 ptb iters per pixel
44140208.067467 steps per pixel
7.736593 bla steps per pixel
44140200.330874 ptb steps per pixel
38311715.969618 iters per bla
speedup: 771.502%
time taken for 192x108 pixel image is about 7m20s, speedup of 7.7x corresponds to 87% of iterations being skipped compared to perturbation without any acceleration (ETA without acceleration is approximately 1 hour).
« Last Edit: November 23, 2021, 05:04:25 PM by claude, Reason: more perf »

Offline claude

  • 3f
  • ******
  • Posts: 2081
    • mathr.co.uk
Re: Another solution to perturbation glitches
« Reply #47 on: November 29, 2021, 04:16:09 PM »
So I have a hand-wavy estimate of when the 1-step BLA is valid:

\[ |z| < r = 0.001 \times \frac{|Z| - |B| |c|}{|A| + 1} \]

and a hand-wavy estimate of when combining two BLAs is valid:

\[ r_{y \circ x} = \min\left\{ r_x, \frac{r_y - |B_x| |c|}{|A_x|} \right\} \]

and that generated the attached images quite quickly (rendered at 19200x10800 and downscaled in GNU IMP).


The images seem plausible, but I'd like mathematical proof that the images are accurate, to which end I want to do backward error analysis to show that the error resulting in z from the BLA corresponds to a non-erroneous z resulting from an erroneous c, but with the error in c bounded so it's within the original c's pixel area.

I'm not good enough at this stuff yet to figure it out, though I have done the basic algebra to find the quadratic terms for a single step and for combining two adjacent quadratic forms.

\[ z_\text{new} = A z + B c + D z^2 + E z c + F c^2 \]

I think Taylor's theorem implies
\[ z_\text{new} = A z + B c + e_z \]
where
\[ |e_z| < R (|z|^2 + |z||c| + |c|^2) \]
where
\[ R = \max\left\{ |D|, |E|/2, |F| \right\} \]

but going from that to the error in c, then back again to bound |z|, is where I'm stuck, especially as I want to calculate it once per image, which means |c| is really a ball around the origin with a radius determined by the zoom factor of the view.  Any thoughts?

Offline claude

  • 3f
  • ******
  • Posts: 2081
    • mathr.co.uk
Re: Another solution to perturbation glitches
« Reply #48 on: November 30, 2021, 11:56:33 AM »
By the sound of it, it is likely due to the differences between MPC (MPFR based) and MPIR - I believe that MPIR seems to be faster.
if you use MPFR directly instead of MPC, you can share more subcomputations like X^2 and Y^2 for both Xn = X^2 - Y^2 + Cx and EscapeTest = X^2 + Y^2.  Also you can use Yn = (X+Y)^2 - (X^2 + Y^2) + Cy which can be faster than Yn = 2 X Y + Cy when the precision gets high (I believe squaring is about 1.5x faster than multiplication, and both are asymptotically faster than addition/subtraction which becomes negligible at higher precisions).


clip
Black dots and glitches in Kalle's Fraktaler

Started by PrinceOfCreation on Noob's Corner

3 Replies
290 Views
Last post September 08, 2020, 08:46:26 AM
by claude
clip
glitches with high order series approximation used for large images

Started by claude on Kalles Fraktaler

6 Replies
903 Views
Last post September 13, 2017, 01:51:54 PM
by knighty
xx
perturbation for Z := exp(Z) + C

Started by claude on Fractal Mathematics And New Theories

6 Replies
1304 Views
Last post May 20, 2019, 06:11:53 AM
by LionHeart
lamp
Perturbation formulas

Started by FractalAlex on Kalles Fraktaler

78 Replies
1777 Views
Last post July 03, 2020, 05:59:20 PM
by FractalAlex
xx
Perturbation theory

Started by gerrit on Fractal Mathematics And New Theories

213 Replies
13682 Views
Last post August 12, 2020, 07:38:03 AM
by gerrit