Giter Club home page Giter Club logo

mandelbrot-area-via-the-b-ttcher-series's Introduction

Mandelbrot set area via the Böttcher series

Let $\mathbb{C}$ be the complex plane, $M$ the Mandelbrot set, and $D$ the closed unit disk. There is an analytic Böttcher map

$$\phi : \mathbb{C} - D \to \mathbb{C} - M$$

$$\phi(z) = z + \sum_n b_n z^{-n}$$

and the area of the Mandelbrot set is

$$\mu(M) = \pi \left(1 - \sum_n n b_n^2\right)$$

Bittner et al. 2014 computed 5M terms of this series, resulting in the bound

$$\mu(M) \le 1.68288$$

We can compute out to $2^{27} = 134,217,728$ terms in a couple hours on an A100, producing

$$\mu(M) \le 1.651587035834859$$

We use expansion arithmetic, representing numbers as unevaluated sums of double precision numbers, as computing in double runs out of precision around $2^{23}$ terms.

Alas, the series approach isn't the fastest

The fastest of the mostly trustworthy methods I've seen for Mandelbrot area is Fisher and Hill 1993, who use the Koebe 1/4 theorem to prove (up to double precision) that quadree cells are either entirely outside or entirely inside the set. Their bounds are

$$1.50296686 < \mu(M) < 1.57012937$$

Worse, accurate extrapolation of the series seems out of reach: out to $2^{26}$ terms the area contribution locally averages to a noisy power law fit with exponent -1.08, but as shown by Bielefeld et al. 1988 this would violate non-Hölder continuity at the boundary. Attempts at extrapolating from our results out to infinity produce area estimates around 1.59 or 1.60, which is already contradicted by Fisher and Hill.

Explanation, analysis, and downloads

This colab has more explanation of the methods used, and some plots of the computed series. For example, here is a plot of the locally averaged area contributions vs. the illusory -1.08 power law fit:

For an .npy file with the series coefficients out to $2^k$ terms, set $k to 1, 2, ..., 26, or 27 and download

  • https://storage.googleapis.com/mandelbrot/numpy/f-k$k.npy

The shape will be [2^k, 2] corresponding to expansion arithmetic with 2 doubles; sum across the last axis if you want a single double.

Building

We use the Meson build system, and the excellent high precision arithmetic library Arb for bootstrapping. We also depend on clang even when compiling CUDA, to allow more recent C++ features. To install dependencies:

# On Mac
brew install meson arb cmake pkg-config openssl

# On Debian Buster
echo deb http://apt.llvm.org/buster/ llvm-toolchain-buster-13 main | sudo tee -a /etc/apt/sources.list
echo deb-src http://apt.llvm.org/buster/ llvm-toolchain-buster-13 main | sudo tee -a /etc/apt/sources.list
sudo apt-get install clang-13 libc++-13-dev libc++abi-13-dev libomp-13-dev \
    python3 python3-pip python3-setuptools python3-wheel ninja-build \
    libmpfr-dev libflint-dev libflint-arb-dev libssl-dev
pip3 install --user meson

Then build and test with

./setup
cd build/release  # Or build/debug
meson compile
meson test

For CUDA profiling, use

# https://developer.nvidia.com/nsight-systems
# https://docs.nvidia.com/nsight-systems/UserGuide/index.html#example-single-command-lines
nsys profile --stats=true ./build/release/area_cuda_test

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.