Proceed to Safety

Bivariate Linear Approximation    

Robert P. Munafo, 2023 Jul 3.

"Bivariate linear approximation" (BLA), also called "bilinear approximation", is a method to extrapolate "deltas" from two sets of reference point calculations performed using the derivative extrapolation method.

It is effectively a "series" approximation of degree 1 (linear) in two variables, using coefficients that can be iterated based on the iterated "deltas" of each of the two input iterations.

The model is "bivariate" because two deltas are used: one for the parameter c which remains constant through all iterations of a pixel (the ∂ in the cubic deltas method), and a delta representing the difference added to the reference (high-precision) z value when "rebasing".

A "rebasing" test (actually two tests, one for a c delta and one for a z delta) was introduced by "Zhuoran" on Fractal Forums in 2021 Dec.

BLA is most useful for deep zooming tasks that require a very high dwell limit, typically for dwell limits in the millions or higher. It requires an existing derivative extrapolation implementation, but need not be implemented if high dwell limits are not considered important. It is used in the more recent versions of Kalles Fraktaler and contemporaneous deep zooming programs.

The Model

Given existing iterates Zn of a reference point (preperiod plus limit cycle) that is known to be periodic (a nucleus or Misiurewicz point) and relatively close to the rest of the pixels we want to draw, the z and c values for the points to be iterated via approximation are called zn=Zn+Δzn and cn=c+Δc respectively.

A bivariate linear model (a polynomial of degree 1 in two variables) is used to approximate each Δzn in terms of an earlier Δzm (with m=0 initially and increased when needed to refresh Δzn. This "rebasing" repairs the errorneous low bits in Δzn that have occurred because of accumulating roundoff error, by recalculating it from the known Zn that was derived from high-precision iteration; this is necessary only when Zn+Δzn has gotten close to the origin.

Because of this use of two subscripts m and n we define a third amount l which is their difference:

n = m + l

Then the bivariate linear model is:

Δzn = Al Δzm + Bl Δc      (1)

The iteration process for iterating (Al, Bl) is modeled by expanding the initial conditions "z0=0" with (1) giving A0=1, B0=0; and expanding the recurrence "zn+1 = zn2+cn" by substituting in zn=Zn+Δzn and cn=C+Δc, and then substituting (1) making sure to notice that the subscripts change from n to m (Δzn changes to Δzm).

In that process, terms get generated for Δzn2, ΔznΔc, and Δc2; but there are no coefficients for those in the bilinear model so we ignore them.

The result is:

A0 = 1
B0 = 0
Al+1 = 2 Zn Al          (3)
Bl+1 = 2 Zn Bl + 1      (4)

Converting the Modeled Iteration to Code

If we didn't have the bilinear model and just wanted to perform iterations on (Z+Δz), it would just be:

f(Z+Δz) = (Z+Δz)2+C+Δc = Z2 + 2ZΔz + Δz2 + C + Δc

The "Z2" and "C" have been precomputed at high precision for the reference point, so we just need to compute the new residual, which is:

f(Z+Δz)-f(Z) = 2ZΔz + Δz2 + Δc        (5)

In the bilinear model above there is no coefficient "Cl" for an Δz2 term, so we didn't try to derive the expression to calculate for this "Cl" and therefore no way to translate it into code.

But it turns out that the coefficients Al and Bl are not needed either, as we can show this with some algebraic manipulation.

Start with (1), but substitute in n+1 for n on the left, and l+1 for l on the right:

Δzn+1 = Al+1 Δzm + Bl+1 Δc

Use (3) and (4) to replace Al+1 and Bl+1:

Δzn+1 = 2 Zn Al Δzm + (2 Zn Bl + 1) Δc

Distribute the Δc:

Δzn+1 = 2 Zn Al Δzm + 2 Zn Bl Δc + Δc

Un-distribute the 2 Zn:

Δzn+1 = 2 Zn (Al Δzm + Bl Δc) + Δc

Use (1) to replace the A and B part with Δzn:

Δzn+1 = 2 Zn Δzn + Δc

Here we have agreement with (5), except for the Δz2 part which wasn't being modeled. So we didn't need coefficients Al and Bl and so there's no problem simply using (5) for the iteration of Δzn.

Therefore the code for the main iteration step is simply:

/* Calculate new dz */ dz := 2 * Z[n] * dz + dz * dz + c;

This matches the two published implementations (computer code). Zhuoran's code has:

dz = 2 * dz * Reference[RefIteration] + dz * dz + dc;

Claude Heiland-Allen's code is refactored slightly to save one multiplication (here with my comments added):

Z = Z_ptr[m]; // Z_ptr is the precomputed array of reference iterates z = (2 * Z + z) * z + c; // "z" is their name for Δz

BLA is discussed in this thread on FractalForums. Read through the whole thread for links to earlier discussions that are relevant to BLA.

revisions: 20230620 first version; 20230622 add model equations and derivations of iteration 20230703 rewrite and move differential estimation content to its own article

From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2024.

Mu-ency main pageindexrecent changesDEMZ

Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jul 03. s.27