Assignment set #1 - PHYD57 - Adv. Comp. Methods for Physics
===========================================================
Due 1 Feb 2022 (5pm = start of tutorial, place: Assignments on Quercus)
Notice: You can submit PHYD57 assignments in one of several forms, for instance
handwriting--> (number pages & add the ending of your student #)
-->snapshots--> place in one .pdf
or
typset in one of the text editors, add illustrations (if any) ---> put in 1 .pdf
There can be multiple files if needed in Qurcus assignments. Avoid posting copies
of separate pages, if you can.
Set #1 of assignments can be done in Python, unless you are ahead of the
schedule and already know C/Fortran. Please include .py (or other) source
file(s).
Programs must be very thoroughly commented by you personally in the file.
Every important instruction must be explained. That is going to show that
you wrote and understand the program, and that it hasn't been copied from
somewhere else. The work must be indivdual and original (not from a friend
or from internet). Close similarity with other student's work will trigger
a deeper scrutiny.
Even if your program works and interactively displays plots of results on your
system, do not assume that 100% of time we will be able to run your program
successfully (we will try!). Hence, please include the screenshots of your
graphical results in your answer, and the printout of text results if there
is no graphics.
Problem 1.1 [30 pt] - Numerical differential calculus
_____________________________________________________
We often have to numerically find the precise rate of change of something that
varies. Notice for instance that, if we can find a zero of a derivative, we
will know the extrememum or at least the inflection point of the variable.
One simple and widespread way to evaluate the first derivative of quantity y(x)
at a given real point x=const, is to evaluate this symmetric estimator at
point x:
Y'(x) = [y(x+h) - y(x-h)]/(2h)
where h is a sufficiently small deviation from x.
Y' is a capital letter, because this is not an exact y'(x). The difference is known as
truncation error (method's error), because one follows from the use of a truncated
Taylor expansion.
By using the Taylor series expansion of the function y(x) in the form
y(x) = y(z) + y'(z) h + (1/2!) y''(z) h^2 + (1/3!) y'''(z) h^3 +...
where x = z + h, and z = const. is the point at which we want to evaluate the derivative,
demonstrate that the estimator Y'(x) deviates from y'(x) by an error of order h^2.
Provide explicit expression for the truncation error, containing the constant of
proportionality between h^2 and truncation error.
There is also another source of numerical error: roundoff error and machine accuracy.
Roundoff errors are due to finite precision of both arithmetic representation and of
elementary operations +-/*. Provide your estimate of the value of error (deviation)
in the language and precision you are using. If you want you can find it numerically
by writing a tinly program. Divide, say, number 0.00001 by two repeatedly, add that
diminishing number to 1., and compare with 1.
When the program thinks the two values are equal, the small number is equal machine
accuracy or epsilon (real number representation limit of mantissa, not the exponent).
Program a function that evaluates y for every input x:
y(x) = exp(-x) - (x-1)^3/4.
You are going to evaluate the derivative y'(0), i.e. at x=0.
What's the exact value given by calculus?
Using Y' estimator, find and plot on a log-log graph how the error of the estimate
depends on h, the half-width of the estimator stencil. Use 400 points spaced uniformly
on a logarithmic axis between h=1e-9 and h=1e-1. (Plot results as a set of points, not
a line.) Overplot with a thin line the theoretical prediction of
(i) truncation error, (ii) roundoff error, also on the log-log scale, as a function of
h. Briefly interpret the results: is the expected order of the method seen in numerics?
In other words, is the absolute value of error diminishing with h^2?
(is the slope on log-log plot -2?).
Problem 1.2 [20 pt] - Higher order differentiation
___________________________________________________
Repeat all the calculations in prob. 1.1 with a less accurate,
asymmetric estimator
Y'(x) = [y(x+h) - y(x)]/h (which order method is that?)
and overplot results on the same figure (using different color, maybe.)
Finally, replace Y' with a more sophisticated estimator and if the plot
isn't too cluttered yet, overplot and its theorethical error predictions as well.
(If it is too crowded, present results on a separate plot.)
Y'(x) = [y(x-2h) -8 y(x-h) +8 y(x+h) -y(x+2h)]/(12h) (which order method is it?)
Demonstrate analytically that this formula is a 4th order in h.
Based on the experience you've gained, what value of h would you recommend for
each of the above methods, in order to minimize the error. What accuracy is
achievable?
Problem 1.3 [25 pt] - Toronto poll
__________________________________
This problem introduces the idea of parallel or concurrent calculation.
It does not require writing a working program. Provide a clear description
of your method(s) with diagrams.
Everybody in Toronto has an integer number of siblings. N people
(N = 1 million, all of whom can text & have online access to a phone book)
volunteer to share the data and work to derive a precise average number
of siblings among them.
How will you organize the work to optimize the speed, and how long
will the poll take, when optimally organized? Develop a math formula
for the estimated time as a function of numerical parameters,
show a sketch of data flow and operations, and only then substitute the
values of parameters (such as N) mentioned in the problem.
Technical details:
(i) composing a message, finding a phone number, dialing & transferring
a message to a recipient takes a combined time t_out = 12 s, on average;
(ii) reading a message and doing math with the contents takes
t_in = 9 s, on average. A person analyzes, and sends the data in series,
i.e. one message at a time.
* * *
Will the pattern of data flow between volunteers change if step (ii) takes
t_in = 3 sec, or 18 sec? How?
* * *
Is there a further possibility to optimize? Consider a case where the
averages are not representative, since there is a large dispersion
around the mean ratio t_out/t_in. Describe changes to pre-planned
workflow that could shorten the polling time.
Problem 1.4 [25 pt] - What are FPGAs?
____________________________________
In the last two decades, processors called FPGA gained a niche popularity.
These machines are thought by some to be a possible winner in the
competition for the future fast computing platforms. But not everybody
shares that opinion.
What are FPGAs? Are they going to ever dominate general computing?
Why/Why not? Do a quick research online, write 3/4 page summarizing
your findings. Cite at least 2 different sources.