1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
---
title: "HPC Complex Fractal Generation"
author:
- "JP Appel"
- "David Marrero"
---
# Prerequisite Knowledge
## Complex Numbers
$$i^2 = -1$$
$$z = x + iy$$
::: notes
* complex numbers are an extension of real numbers, stemming from the square root of $-1$
* a complex number is just a pair of two real numbers (x,y) with different ways to add and multiply
* in computer science we model real numbers with a single float or double, so we will need 2 floats or doubles to model a complex number
:::
. . .
### Addition
$$z_1 + z_2 = (x_1 + x_2) + i (y_1 + y_2)$$
::: notes
* addition behaves as you expect
* multiplication involves multiplying then distributing, and using the fact that $i^2 = -1$
* so adding two complex numbers is 2 float additions
* and multiplying them is 4 multiplications and 2 additions
:::
### Multiplication
$$z_1z_2 = (x_1x_2 - y_1y_2) + i(x_1y_2 + x_2y_1)$$
## What is the Mandelbrot Set
. . .
$$z_n = z^2_{n-1} + z_0$$
::: notes
* this sequence is used to generate the mandelbrot set
* if for some complex number $z_0$ the sequence remains bounded as it $n$ approaches infinity then $z_0$ lies within the mandelbrot set
* there are many recursive sequences related to this, where you modify that happens with the recursive term
:::
## Fractals
::::: {.columns}
:::: {.column width=40%}
* infinite self-similar geometric shape
* have "fractional dimension"
::::
:::: {.column width=60%}
{ width=80% }
::::
:::::
. . .
The Mandelbrot set is a fractal in the complex plane
::: notes
* fractals are a infinite self-similar geometric shape
* so if you zoom in on any one part it will look like the entire object
* the Sripenski triangle is an example of a fractal
* the mandelbrot set forms a fractal in the complex plane
:::
## Fractal in Nature
{ width=50%}
::: notes
* fractals often show up in nature
:::
## Escape Time Algorithm
::: incremental
* Inputs
* Maximum Number of iterations
* Upper bound
1. Create a grid of points to sample
2. For each point in the sample space
1. Compute the next term in the sequence
2. if greater than the upper bound return the number of iterations
3. else repeat until the maximum number of iterations and return
:::
::: notes
* to compute the complex sets we used an escape time algorithm
* in general it takes in a maximum number of iterations, an initial value, and an upper bound
* the escape time algorithm is as follows (read of the slides)
* note that each sampled point is completely independent of any other point
* this hints to us that the problem will parallelize well
* for most of the sets we looked at, there is a proven bound
* ie if the sequence is ever larger than a value we know it diverges
:::
# Implementation
## Program Structure
::: notes
* the translation units are roughly as pictured here
* black ellipses are for serial code, color is for parallel
* each version of the program fills in an array with the number of iterations it took the sequence to grow too large
* that array along with some extra data is a grid object, which can be serialized and deserialized
* the main fractals unit handles cli argument parsing for the sampling resolution, fractal type etc
* a separate renderer program handles creating images from the `.grid` file
* the `.grid` file format is really simple, it's a magic number, the grid dimensions, the maximum number of iterations, the lower left and upper right most points of the region, and then the data
:::
## Mandelbrot
::: notes
* when mandelbrot initially tried to have this printed, the printers kept removing the "dust" thinking it was an error in their printing process
:::
## Tricorn
## Burning Ship
## Multibrot
## Multicorn
## Julia
## Serial Animation
## Shared Animation
## CUDA Animation
# Analysis
##
[Interactive Plots](../analysis/analysis.html)
|
