Lab 03: Visualizing the Mandelbrot Set

using vector operations to perform Mandelbrot calculations quickly

DUE: Friday, March 24, Monday, March 27, 11:59 pm

Background

The Mandelbrot set

The Mandelbrot set is among the most widely depicted mathematical objects. In order to define the Mandelbrot set (and understand how to draw it), we need to start with the complex numbers and the complex plane.

Complex numbers

Complex numbers are numbers of the form \(a + b i\) where \(a\) and \(b\) are real numbers, and \(i\) is the imaginary number satisfying \(i^2 = -1\). Complex numbers can be added and multiplied:

  • \[(a + b i) + (c + d i) = (a + c) + (b + d)i\]
  • \[(a + b i) (c + d i) = (a c - b d) + (a d + b c) i\]

Further, complex numbers have a modulus defined by

  • \[| a + b i | = \sqrt{a^2 + b^2}\]

The complex plane consists of the set of all complex numbers represented as points in a plane: each \(a + b i\) corresponds to the point \((a, b)\) in the plane.

Mandelbrot definition

Given a complex number \(c = a + b i\), consider the sequence of complex numbers \(z_1, z_2, \ldots\) defined by the following recursive formula:

  • \[z_1 = c\]
  • for \(n > 1\), \(z_n = z_{n-1}^2 + c\).

For each starting point \(c\), one of two things can happen:

  1. the sequence \(z_1, z_2, \ldots\) remains bounded—i.e., there is a positive (real) number \(M\) such that \(\mid z_n \mid \leq M\)
  2. the sequence \(z_1, z_2, \ldots\) is unbounded—\(\mid z_1 \mid , \mid z_2 \mid , \ldots\) grows without bound.

The Mandelbrot set is defined to be the set of complex numbers \(c\) for which the sequence \(z_1, z_2, \ldots\) remains bounded. For example, \(c = 1\) is not in the Mandelbrot set because its corresponding sequence is \(1, 2, 5, 26, \ldots\) which grows without bound. On the other hand, \(c = -1\) is in the Mandelbrot set because its corresponding sequence is \(-1, 0, -1, 0, \ldots\) which remains bounded.

Computing the Mandelbrot set

In general, it might be difficult to determine if a given sequence \(z_1, z_2,\ldots\) remains bounded analytically. To visualize the Mandelbrot set it is enough to determine if the sequence is bounded empirically. Specifically, we can choose two parameters: a modulus bound \(M\) and an iteration bound \(N\). We then proceed as follows. Starting from a complex number \(c\), compute \(z_1, z_2, \ldots\) as required. For each \(z_n\), compute \(\mid z_n\mid\) and do the following:

  1. if \(\mid z_n\mid \geq M\), stop and report that \(c\) is not in the Mandelbrot set,
  2. if \(n = N\), stop and report that \(c\) is in the Mandelbrot set
  3. otherwise, continue.

Following this procedure, we can obtain this following image of the Mandelbrot set.

The image above depicts the region of the complex plane with real part (\(x\)-coordinates) between \(-2\) and \(1\), and imaginary part (\(y\)-coordinates) between \(-1.5\) and \(1.5\). The image is 1024 by 1024 pixels, where each pixel represents an point in the complex plane. Each pixel is colored black if it is (empirically) in the Mandelbrot set, and white otherwise. For points \(c\) not in the Mandelbrot set (i.e., for which case 1 above occurs), the first iteration \(n\) at which \(\mid z_n \mid \geq M\) is called the escape time. In order to generate a color image such as the image below, the color is determined by the escape time.

Specifically, the color of a point \(c\) is determined by a color map applied to the escape time for the point. In the image above, brighter colors indicate shorter escape times. You can read about different methods for coloring the Mandelbrot set at the following link:

Vector Operations in Java

For given parameters \(M\) and \(N\) as above, determining the escape time of a single complex value \(c\) is straightforward. Thus, images as above can be computed by simply iterating over all pixels sequentially and computing the escape time of the point corresponding to each pixel. For the \(1024 \times 1024\) pixel images above, this requires about a million individual escape time computation, and each escape time requires up to \(N\) iterations to compute. The calculations for coloring different pixels, however, and independent of one another. Thus we may be able to employ parallelism to compute escape times faster. In this lab, we will explore how vector operations can speed up escape time calculations by performing arithmetic operations for multiple points in parallel.

Vector operations are single instruction, multiple data (SIMD) operations. This means that they perform the same elementary operation on multiple primitive values in parallel. In newer versions of Java (16+), SIMD instructions are supported via the Vector package. The Vector package provides support for SIMD operations on primitive datatypes. Here are links to the relevant documentation:

Program description

For your assignment, you will write a program that uses vector operations to compute escape times for Mandelbrot set operations. To get started, download the following archive:

The program includes four files, Mandelbrot.java, MandelbrotTester.java, MandelbrotViewer.java, and run-test.sh.

  • Mandelbrot.java defines a class that stores parameters to describe a region in the complex plane, as well as methods for computing escape times for points in that region. It defines a baseline method, escapeTimesBaseline as well as a(in incomplete) escapeTimesOptimized method. Your task is to complete the escapeTimesOptimized method.

  • MandelbrotTester.java defines methods for testing your escapeTimesOptimized method. The method correctnessTest verifies that your optimized and the baseline implementation provide the same escape times, while two performance test methods compare the running times of baseline and optimized implementations.

  • MandelbrotViewer.java draws the Mandelbrot set in a specified region using the escape time calculations from Mandelbrot.java. This file is not required for the assignment, but is included so that you view the output of your program and experiment with finding interesting regions of the Mandelbrot set.

  • run-test.sh is a shell script for running your program on the HPC cluster. Once your completed files are on the cluster, you can run the tests using sbatch run-test.sh. When the tests complete (typically in about five minutes), the program will write a file mandelbrotTest.txt that includes the results of the test.

Your task is to complete the method escapeTimesOptimized in Mandelbrot.java. You should only complete this method. You should not modify any other methods in Mandelbrot.java or anthing in MandelbrotTester.java. Your implementation of escapeTimesOptimized should be a single-threaded method that employs Vector operations to perform the escape time operations more quickly than the escapeTimesBaseline method (provided in Mandelbrot.java).

What to turn in

To complete the assignment, turn in only your completed Mandelbrot.java file.

Grading

Your programs will be graded on a 10 point scale according to the following criteria:

  • Correctness (3 pts). Your program compiles and completes the task as specified in the program description above. The program passes the correctness test in MandelbrotTester.java.

  • Style and Vectors (3 pt).
    • Coding style: code is reasonably well-organized and readable (to a human). Variables, methods, and classes have sensible, descriptive names. Code is well-commented.
    • The program correctly applies Vector operations in order to perform the operations in escapeTimesOptimized. No multithreading or other performance enhancements should be used.
  • Performance (4 pts).
    • 2 pts. The optimized method is faster than the baseline for at least 3 of the 5 performance tests.
    • 3 pts. Additionally, the optimized method is at least 2 times faster than baseline for one of the tests.
    • 4 pts. The optimized method is at least 3 times faster than the baseline for one of the tests.

Extensions

There are a lot of directions you can go with this assignment! Here are a few:

  1. Make a color map that makes things look much better than mine, and use it to make some nice images. (You can submit image files if you’d like.)
  2. Modify the MandelbrotViewer to do an infinite zoom into an interesting portion of Mandelbrot set. If you do this, have the program print the framerate to the console.
  3. Draw other fractals! The Mandelbrot set is but one fractal in a large family of fractals produced using similar methods. For example, you could draw Newton fractals or other Julia sets.