# M3C 2017 Homework 3¶

**Due date/time:** 30/11/2017, 23:59 GMT

**Getting Started:** If needed, update your local copy of the course repo (*sync* and *pull*). The homework/hw3/ directory contains the files,
*hw3_template.py*, *hw3_template.f90*, and *hw3_main.f90*.
Make a new directory outside of the course repo, and place *dev* copies of the template files named in this new directory.
Ultimately, the final files that you submit should be titled *hw3.py* and *hw3.f90*.
Browse through the three files provided; the template files contain a number of function/subroutine headers, and
you will have to add code as described below.
First, however, you should *add your name and 8-digit college id to the docstring/comment at the top of each file.*

In this assignment, we will consider a modified version of the random network model implemented in
HW1. We now consider random walks in *d* dimensions as follows. A seed node is placed at \(x^{(i)}=0\), \(i=1,2,...,d\).
A new node is introduced at \(x^{(d)}=H\) with \(x^{(i)}=0\), \(i=1,2,...,d-1\), and this node then
undergoes a random walk with each step governed by:

where \(\mathcal{P}^{(i)}_j\) are random numbers (independent for all values of *i* and *j* considered). For \(i<d\),
\(\mathcal{P}^{(i)}_j\) takes on the values *-1* or *1* with equal probability. For *i=d*, \(\mathcal{P}^{(d)}_j\) is either
*-1* or *0* with equal probability. A random walk terminates when either 1) a node reaches \(x^{(d)}=0\) or 2) the new node
is sufficiently close to one or more “old” nodes such that: \(\min(\Delta X) \leq 1\) where
\(\Delta X = \{|X^{(1)}-Y^{(1)}|, |X^{(2)}-Y^{(2)}|, ..., |X^{(d)}-Y^{(d)}|\}\), \(X^{(i)}\) is the position
of the new node and \(Y^{(i)}\) is the position of a node that has already been added to the network. New nodes continue to be introduced (after the
previous node has been added to the network) until there are a total of *N* nodes in the network. The *height* of a network corresponds
to the largest value of \(X^{(d)}\) in the network.

Note: As you work through the tasks below, you may add module variables and additional subroutines and functions as needed. Do not remove module variables or modify input/output of existing complete routines without first asking for permission.

1.(20 pts) *Performance*
You have been provided with Python and Fortran routines named *rwnet* that implement the model described above.
Complete the function *performance1* in *hw3_dev.py* so that it analyzes how the model simulation time varies with the
total number of nodes in the network. You may keep *H* fixed and constrain *d* to be *2* and *3* (though you can examine
a broader parameter space if desired). You should also compare the performance of the Fortran and Python routines.
The function should create one or more figures illustrating the most important trends, and these trends should be concisely discussed
and analyzed in the function docstring.

2. (35 pts) *Ensemble averages and parallel performance*
i) You will now develop a Fortran subroutine parallelized with OpenMP which simulates *m* realizations of a network for a given set of
input parameters. The routine should output: 1) the node coordinates for all *m* networks, 2) The maximum and 3) minimum network heights
and 4) the average height of the *m* networks.
The subroutine should be carefully parallelized with OpenMP. You should avoid generating nested
parallel regions, but otherwise, your OpenMP implementation should be both sensible and thorough.
The number of threads used within any parallel regions should correspond to the input variable,
*numthreads*. Add a comment below the subroutine header concisely explaining your approach to parallelization.

ii) Analyze the parallel performance of *simulate_m* for the case *H=600*, *d=2*. Add code to *performance2* in *hw3_dev.py* which
assesses the speedup and makes one or more figures illustrating the most important trends. Clearly and concisely discuss and explain these trends
in the docstring of the function. You are not required to run calculations with more than 2 threads.

3. (30 pts) *Network analysis*
i) Analyze the dependence of the network height on the total number of nodes. Add code to *analyze1* in *hw3_dev.py*
which generates one or more figures illustrating the most important trends. Clearly and concisely discuss and explain these trends
in the docstring of the function. You should consider both *d=2, H=200* and *d=3,H=100*.

ii) You will now compute the *fractal dimensions* of simulated networks.
The fractal dimension, \(\delta_f\), can be defined as follows for networks with *N* total nodes. Let \(N_\epsilon\) denote the total number of pairs of nodes within a distance,
\(\epsilon\), of each other. Then \(C(\epsilon) \sim \epsilon^{\delta_f}\) where \(C(\epsilon) = lim_{N\rightarrow \infty}\frac{N_\epsilon}{N^2}\),
. Complete *analyze2* in *hw3_dev.py* so that it estimates \(\delta_f\)
for *d=2, H=400* and *d=3,H=100*. You may base your estimate on a single network (for each *d*) with sufficiently large *N*.
For a given network, you should allow \(\epsilon\) to vary between *2* and half of the network height.
The function should return your estimates for \(\delta_f\) in a 2-element tuple. The function should also generate one or more figures illustrating how well the simulation
data fits the assumed form for \(C(\epsilon)\).

4. (15 pts) *Visualization*
Complete the function *visualize* in *hw3_dev.py* so that it generates an animation illustrating the generation of a network.
It is sufficient to consider the case *H=200*, *N=500*, *d=2*, but feel free to explore larger networks and *d=3*.
Submit your animation file with the filename *hw3movie.xxx* with *xxx* replaced as appropriate (e.g. *mp4*).

You also have the option of entering a movie in the 1st annual M3C animation festival. The class will vote on a winner who will receive a non-lucrative prize, and the top vote-getters and the instructor will have their movies shown during the final lecture this term.

*Notes:*¶

1. All figures created by your code should be well-made and properly labeled. The title of each figure should include your name and the name of the function which created it.
**Submit figures files corresponding to all of the figures generated by the *performance* and *analyze* functions with your codes.**
If you are submitting more than 10 figures in total, please think carefully about presenting your results more concisely.

2. It is expected that your python functions will take several minutes to run. It is suggested that you start out with smaller problem sizes and then move to larger sizes as your code develeops and as you prepare to generate your final figures. If a function is taking more than an hour to run, check with the instructor to see if this is ok.

3. Your Fortran codes should run to double-precision accuracy.

4. The code in the *name==main* section of your python script should call your *performance* and *analyze* functions
and generate the figures you are submitting.

5. You may use any python routines in *numpy*, *scipy*, *matplotlib*, and *time*. Check first if you would like to utilize
other modules.

## Submitting the assignment¶

To submit the assignment for assessment, go to the course blackboard page, and click on the “Assignments” link on the left-hand side of the page, and then click on Homework 3. Click on “Write Submission” and add the statement: “This is all my own unaided work unless stated otherwise.”

Click on “Browse My Computer” and upload your final files, *hw3.f90*, *hw3.py*, *hw3xx.png*, and *hw3movie.xxx*.
Finally, click “Submit”.