"Reliable affine arithmetics"

I have a number of images for which I would like to detect interior and cycles with the TSA, however as they are relatively high-degree for cell-mapping and IA overestimation, so far that proved unsuccessful.

Here I implemented my own library of reliable affine arithmetics (dealing with rounding errors by introducing new noise symbols), to see if the promise of respecting linear dependencies between the real and imaginary coordinate of the bounding box (which IA does not), leads to a better convergence and interior detection (the final goal).

I tested this (on selected points, not a full image yet) with f(z)=z^8+A*z+c with A=(-778325-33669899*i)*2^-25 and c=(-2568192+14110720*i)*2^-25. The point-sampled Julia set is the rightmost part in the picture below. The current status of the TSA in the middle - without interior detected by IA.

Left is a (typical I hope) bounding box for f(B). Here for the complex square B=[a..a+d]+[b..b+d] with a=691/1024, b=256/1024 and d=2^-14, which was randomly selected and seems - by point-sampling - to be interior.

There was quite a big improvement when using affine arithmetics. The classic IA produces the red bounding box (absolute sizes are arbitrary). AA output the green rectangle, which is much smaller and seems to fit tightly to the presumed true image of f(B) (gray, B was gridded and each individual grid point was numerically, non-rounding controlled, mapped to get a rough visual on how the true image looks). So classic IA has quite a large overestimation - and all the pixels that bbx intersects with are influencing the cell-mapping's backpropagation of color to the initial complex square B.

I hope this reduction suffices to detect interior in the next implementation step.

The principal output of AA is a convex polygon, symmetric around a central point. Here I plan on using AA in a naive, black-box like way: Enter a complex square, transform it into an affine form, perform the calculations in AA and convert the resulting affine form back to an axis-parallel rectangle (a complex interval).

This leads to a loss of information as I still have to check pixels that are probabgly outside the actual AA polygon, but this is a project for the farer futere as I would need to change the bbx-routine altogether (I am currently trying to get a visual on that polygon for some non-trivial examples).

Currently I implemented only addition, subtraction (rounding introduces a new noise symbol) and multiplication (a new noise symbol both covers rounding and an upper bound on the non-linear (in AA's affine form) terms).

Has anyone tried different upper bounds on that non-linear term? From the bbx's so far visualized, the AA complex interval seems to be quite tight (so a smaller upper bound might not provide a big decrease in width?).

My implementation is based on:

- J. Stolfi, LH de Figueiredo. Self-validated numerical methods and applications. 1997.
- F. Messine, A. Touhami. A general reliable quadratic form: an extension of Affine Arithmetics. Reliable Computing, 2006.