Home > Papers > Parallel Fractals
Introduction | Mandelbrot Set | Image Characteristics | Parallel Algorithm Design | Partitioning | Agglomeration | Output Synchronization | Token-Passing | Polling | Performance Analysis | Conclusion | Bibliography | Slides
Parallel Fractal Image Generation
The Mandelbrot Set
Fractals are generated by calculating certain formulas over and over again, feeding the results of one step back into the next step. For example, the Mandelbrot set, the most well-known fractal object first described by Benoit Mandelbrot, is created by iterating a simple formula over complex numbers.
A complex number C consists of two components – a "real" part Re C, and an "imaginary" part Im C. The imaginary part is multiplied by the constant i, defined as the square root of –1:
Although complex numbers look like an abstract mathematical contraption that has no connection with the real world, they are as realistic as the real number space that we are used to. In fact, complex numbers are routinely used by electrical engineers to design the devices we use every day, so they are indeed a valid means of describing the world. To make complex numbers a bit easier to grasp, we can visualize them as points with the coordinates (x, yi) on a plane, as shown in Figure 1:
The magnitude of a complex number, |C|, ist defined as that point's distance from the origin of the complex plane and calculated as
Now, to start creating a fractal image, we choose an arbitrary point C from the complex plane and plug it into the following simple iteration formula:
This is the formula Benoit Mandelbrot first described. It takes the current point Zn (for the first iteration, this is Z0, the origin), squares it, adds the constant C we chose before, and so arrives at a new point Zn+1. This point is again squared, C is added, and so on. We perform this iteration several times and see how the values of Z develop.
For example, if we choose C = –1.0 + 0.5i, we get the series of values of Z shown in Table 1:
Table 1: Iteration approaching infinity with C = –1.0 + 0.5i
We observe that Z moves out towards infinity within very few iterations. Somehow, this is what we might expect since we are constantly squaring and adding numbers.
However, if we try a different choice of C, for example C = 0.25 – 0.25i, we get the results in Table 2:
Table 2: Beginning iteration with C = 0.25 – 0.25i
Surprisingly, Z stays within close range of the origin. If we iterate some more, we find that Z actually converges to a certain point (Table 3):
Table 3: Converging iteration with C = 0.25 – 0.25i
Obviously, Z shows very different behaviour (converging vs. escaping to infinity) depending on our initial choice of C. To see how the two are related, we apply the iteration formula to every point C on the complex plane and color it according to the behavior if the iteration – if Z converges, we mark C black, and if Z escapes to infinity, we leave C white. The result is the graph shown in Figure 2:
We have plotted the Mandelbrot set – the set of all points for which the iteration formula does not escape to infinity after a certain maximum number of iterations. It is a fractal with a solid interior, but an extremely convoluted edge that shows infinite detail and self-similarity when we look at it more closely.
|© 2001 Matthias Book|