CMDA 3634 SP2020 The Wave Equation with C Project 02
Project 02: The Wave Equation with C
Version: Current as of 2021-02-27 11:01:25
Due:
– Preparation: 2021-02-27 23:59:00
– Coding & Analysis: 2021-03-12 23:59:00 (24 hour grace period applies to this due date.)
Points: 100
Deliverables:
– Preparation work as a PDF, typeset with LaTeX, through Canvas.
– All code through code.vt.edu, including all LaTeX source.
– Project report and analysis as a PDF, typeset with LaTeX, through Canvas.
Collaboration:
– This assignment is to be completed by yourself.
– For conceptual aspects of this assignment, you may seek assistance from your classmates. In your submission
you must indicate from whom you received assistance.
– You may not assist or seek assistance from your classmates on matters of programming, code design, or
derivations.
– If you are unsure, ask course staff.
Honor Code: By submitting this assignment, you acknowledge that you have adhered to the Virginia Tech
Honor Code and attest to the following:
I have neither given nor received unauthorized assistance on this assignment. The work I am presenting
is ultimately my own.
References
C:
– Introduction to C https://www.cprogramming.com/tutorial/c-tutorial.html
The Wave Equation:
– General overview
https://en.wikipedia.org/wiki/Wave_equation
https://mathworld.wolfram.com/WaveEquation.html
OpenStax: Mathematics of Waves (link)
– Standing Waves (especially in 2D with a rectangular boundary)
https://en.wikipedia.org/wiki/Standing_wave
– Chapter 5.1 of Gilbert Strang’s course notes “5.1 Finite Difference Methods”
https://math.mit.edu/classes/18.086/2006/am51.pdf
– Chapter 5.3 of Gilbert Strang’s course notes “5.3 The Wave Equation and Staggered Leapfrog”
https://math.mit.edu/classes/18.086/2006/am53.pdf
LaTeX:
– Writing pseudo-code in Latex: https://en.wikibooks.org/wiki/LaTeX/Algorithms
– General topics: https://www.overleaf.com/learn
1
CMDA 3634 SP2020 The Wave Equation with C Project 02
Code Environment
For this project, use a terminal-based programming environment.
– Use a terminal-based editor such as Vim, Emacs, or nano.
– Compile your project from the terminal with make.
– In particular, do NOT use IDEs such as Visual Studio or Eclipse.
All necessary code must be put in your class Git repository.
Your Git repository must have the following structure:
cmda3634/
projects/
proj02/
code/
data/
report/
Data and any scripts which are necessary to recreate your data, must be in the data directory.
DO NOT INCLUDE LARGE NUMBERS OF IMAGE FILES OR LARGE VIDEO FILES IN YOUR
GIT REPOSITORY!
Your tex source for project preparation and final report go in the report directory.
Remember: commit early, commit often, commit after minor changes, commit after major changes. Push
your code to code.vt.edu frequently.
You must separate headers, source, and applications.
You must include a makefile.
You must include a README explaining how to build and run your programs.
2
CMDA 3634 SP2020 The Wave Equation with C Project 02
Requirements
Preparation (20%)
1. Write a work plan for completing this project. You should review the coding and analysis sections, as well
as the remaining assignment schedule between now and the due date. Your work plan should include a
description of the steps you think will be necessary to complete the required tasks, how you plan to test
that task, and an estimate of the time that each task will take. Be sure to account for ARC resource
requirements. You may need to submit some batch jobs to TinkerCliffs (rather than interactive jobs) to get
data. To properly answer this question, you will need to take some time and think through the remainder
of the assignment. A quality answer should require at least half of a page of detail.
2. A solution to Project 1 has been provided in the cmda3634 materials repository. Review this solution and
compare it to the one you submitted. Give at least three (3) specific bullet points describing differences in
implementation and overall design.
You should consider things that you learned by making the comparison, what the consequences of different
design decisions are, and how seeing a different solution may influence your future approach. You should
consider aspects of structure, style, and syntax.
Try not to focus entirely on small, line-by-line, decisions and try not to focus entirely on large-scale design
decisions. Remember, there is more than one way to do things and just because I do things one way, doesn’t
mean yours is necessarily wrong. The purpose of this question is for you to learn other ways to think about
program design, which you cannot do without looking at other examples of code.
3. In our Python, we likely stored the entire solution history in memory. By my estimate, for n = 301, this
required approximately 1.43 gigabytes of memory to store. To arrive at this estimate, I used the following:
The total data that I needed to store was nt × nx × ny, where nt was determined using the same
formula as the last project.
T = 5 and nt = b
T
δt c. The expression bxc denotes the the floor function and is same as rounding x
down to the nearest integer.
I assumed that each piece of data was a single 64-bit floating point number.
I converted the total bytes required to gigabytes by dividing by 10243
.
Fill in the following table:
n nt Storage Size A) Feasible in memory? B) Feasible on disk?
11
101
301 2121 1.43 GB
501
1001
2501
10001
The final two columns are answers to the questions:
A) Will it be feasible to store the entire solution history in memory?
B) Will it be feasible to store the entire solution history on disk?
Some further useful information:
The interactive jobs you have requested (so far) limit you to 2 GB of total memory, but a node on
TinkerCliffs has to 256 GB of memory.
Technically, per ARC policy, each user has the ability to store 14 TB for short term purposes.
3
CMDA 3634 SP2020 The Wave Equation with C Project 02
4. Consider the array and pointer created by the following lines of code:
int* ptr;
int arr[] = {3,6,9,12,15,18,21,24,27};
ptr = arr;
After running this code, the memory stack can be represented by the following table.
Address 0xA00 0xA08 0xA10 0xA14 0xA18 0xA1C 0xA20 0xA24 0xA28 0xA2C 0xA30
Value 0xA10 0xA10 3 6 9 12 15 18 21 24 27
Name ptr arr
C treats stack arrays and pointers a little differently. This exercise is about the true pointer variable ptr,
but it is convenient to initialize ptr with the array called arr.
For each of the C code fragments below, determine if it is a valid expression. If it is, what is the data type
of the result (e.g., int, int*, . . . ) and what is the value of the expression? (Remember, if the expression
is a pointer, the value is an address.) If it is not, why not?
Feel free to put any of these fragments into a small C program to test the result. Note that the memory
locations in the table are arbitrary. If you try to run the code, you will get different memory locations.
(a) ptr
(b) ptr[3]
(c) 3+ptr
(d) 3*ptr
(e) 3**ptr
(f) *(3+ptr)
(g) *ptr+3
(h) (ptr+3)*
(i) &(ptr+3)
(j) (ptr+3)&
(k) 3[ptr]
(l) &(ptr[3])
(m) ptr[3][3]
(n) (ptr+3)[3]
(o) *ptr
(p) ptr*
(q) &ptr
(r) ptr&
5. When 2D data is stored on a computer, it is often stored in contiguous memory either row-by-row (as in
NumPy and C) or column-by-column (as in R, MatLab, and Fortran). These orderings are called row-major
and column-major, respectively.
From mathematical notation, you are probably used to accessing 2D data using two indices, e.g., (j, i) to
indicate the row and column. We will store our 2D data as a single, large 1D array. For example, if our 2D
data is ny × nx, then the 1D array will have length nynx. Your C program will need to compute a pointer
to the data in the linear memory. Consider U, an ny × nx matrix, (1)
If U is stored in row-major form, the equivalent 1D array is given below, with the linear indices shown under
each entry.
[u0,0 u0,1 · · · u0,nx−1 u1,0 u1,1 · · · u1,nx−1 · · · uny−1,0 uny−1,1 · · · uny−1,nx−1]
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
0 1 nx − 1 nx nx + 1 2nx − 1 (ny − 1)nx (ny − 1)nx + 1 nynx − 1
(a) If the user wants to access the (j, i) entry of U, the corresponding linear index in row-major form is
kr = jnx + i. Justify this expression. You may want to draw a small diagram, scan it, and include it
in your report.
(b) Assume that kr is known but (j, i) is not. Give expressions for the (j, i) pair that corresponds to the
linear index kr.
4
CMDA 3634 SP2020 The Wave Equation with C Project 02
Coding (60%)
This project is to be written in the C language. You may base your solution off of your solution to Project 1 or
off of the provided solution to Project 1.
1. The source code for your solution is to be submitted via GitLab.
2. For this project:
DO NOT INCLUDE LARGE IMAGE FILES OR VIDEO FILES IN YOUR GIT REPOSITORY!
Your repository should only include the images that are used in your report (a small number of them).
Be sure to save images to PNG format so that LaTeX can use them.
You can submit videos directly through Canvas.
Git does not handle large files well.
Avoid pushing large outputs by including their file extensions or names in your .gitignore file.
3. You must use proper separation of source, header, and program files.
4. You must include a Makefile in your code directory. This makefile should include targets for each executable
you are required to produce, a target to compile all executables, and a clean target to remove intermediate
build files and executables.
5. Some code is provided to you in the in-class code repository.
simple data io.py contains an example code for loading a data file created with the described
specification.
– You may need to borrow from or modify this code, depending on how to choose to store or name
the files.
6. You may want to write other functions or break the assigned functions into smaller parts. This is encouraged.
Tasks:
1. Design a C data structure for storing two-dimensional float data. The structure should support arbitrary
ny × nx (rows by columns) 32-bit floating point data. For the sizes of problems we will test, it will be
necessary to store the underlying data as a single 1D array. (See task 5 of the preparation.) For this data
structure, you must provide a clean API for the following:
(a) Allocation and deallocation
(b) Initialization
(c) Copying (deep copy)
(d) Saving to disk
When saving the array to disk, the first two entries in the file must be unsigned integers giving the numbers
of rows (ny) and columns (nx) in the array and the remainder of the file should contain ny × nx 32-bit
floating point data. All files must be binary, not ASCII.
2. Implement a function that evaluates the standing wave solution to the wave equation on a grid and stores
the data using your 2D array structure.
3. Implement a function that computes one time step of the wave equation simulation.
4. Implement a function that, given the final simulation time T, the grid size n, and the number of stationary
nodes mx and my, computes and returns nt iterations of the simulation.
While your array data structure must support ny different from nx, we will still assume that ny =
nx = n for the purposes of the simulation.
For numerical reasons, use δt = αδx/√
2, for α = 1.
The simulation should be initialized by the standing wave solution at for u
−1
and u
0
.
5. Write a main program that takes n, mx, my, α, and T as command line arguments to run various
simulations. You should write multiple versions of the main program to complete the different analysis
tasks in the next section. Each main function needs to be in a separate .c file. Be sure to document
the main functions and their files in your README and include targets in your makefile. To complete the
analysis phase, you will need to:
5
CMDA 3634 SP2020 The Wave Equation with C Project 02
Use clock() in time.h to time various components of the simulation.
– When timing, it is very important that you time only the relevant component. For example, if
you are asked to time how long a single iteration of the simulation takes to run, you should be
careful to not include the time it takes to save the wavefield (u) to an image.
– It is also important that your timing is the average of multiple runs, as anomalies can occur.
Produce images of some solutions.
– I strongly suggest that you save data files to separate directories based on the experiment you are
running. To make filenames unique, the filenames should include the iteration number.
– It may be helpful to look into the capabilities of C format strings.
6
CMDA 3634 SP2020 The Wave Equation with C Project 02
Analysis (20%)
Your report for this project will be submitted via Canvas. Tex source, images, videos, and final PDFs should be
included in your Git repositories.
Unless otherwise specified, use T = 2.5, mx = 3, and my = 4.
Tasks:
1. Use the clock() function to time your simulation for 11, 51, 101, 201, 301, 501, 1001, and 2501.
Show your runtimes in a table and use Python to plot your runtimes as a function of N = n × n.
Create a plot showing the average run-time per time step as a function of N = n × n. Include your
results from Python in Project 1, as a separate line in the plot.
Estimate how long it will take to run just 100 iterations for n = 100, 000.
How do the times and estimates compare to those from the Python version in Project 1?
2. For n = 501, save the simulated solutions (u) closest to t = 0.0, 0.5, 1.0, 1.5, 2.0, and 2.5 seconds. Also,
save solutions for evaluating the standing wave solution at those times. Evaluating the standing wave
function will get you the true solution. Plot the simulated solution, the true solution, and their difference.
Describe what you see.
3. Extra Credit: Use Matplotlib to create a video file of the evolution of simulations for T = 5, n = 101, mx =
2, my = 3. You will need to adapt the Python code to load the sequence of ∼700 data files to create the
animation.