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.