Final Exam Questions

Question 1

In the context of computational science, describe verification

Answer 1

1. Process of checking that a computational model is solving the equations it was designed to solve.
2. Checks if the model is correctly implemented.
3. Involves checking the consistency + correctness of code with respect to the underlying mathematical + physical models.
4. Does not guarantee model is accurate, only that it is implemented correctly.

Question 2

In the context of computational science, describe validation

Answer 2

• Process of checking that a computational model accurately represents the real-world phenomenon it is intended to model.
• Involves assessing the uncertainties associated with the model predictions + the experimental data used for validation.

Question 3

In the context of computational science, distinguish carefully between verification and validation.

Answer 3

Verification - ensures code is implemented correctly.
Validation - ensures that the model accurately represents reality.

Question 4

Write down a finite difference approximation to the Laplacian operator.

Answer 4

Question 5

Explain how the accuracy of a finite difference approximation to the Laplacian operator can be characterised

Answer 5

1. Grid spacing: Δx and Δy. As they become smaller, approximation becomes more accurate
2. Approximation is exact in the limit as Δx and Δy approach 0.
3. Order of finite difference scheme. Higher-order scheme = more accurate results. Need more function evaluations and computationally more expensive.
4. Truncation error
5. Round-off error. Error introduced by finite precision of computer arithmetic

Question 6

Suppose an exact solution is known to a problem involving the Laplacian operator of the previous question. Explain how to demonstrate that a computed solution converges to this exact solution.

Answer 6

1. Convergence to an exact solution at the expected rate is the strongest possible test of a computer code.
2. Method of manufactured solutions:
3. Exact solution is known + is used to derive the RHS of differential equation.
4. RHS is then used as input to numerical method being tested + resulting solution is compared to known exact solutions.
   a. write down model equation
   b. write down a manufactured solution (any function satisfying boundary conditions)
   c. Construct the manufactured source term M
   d. Show that the computer code under test converges as expected (with M included) to the manufactured solution. Then the code is deemed verified.
   e. Set M to 0
   f. Proceed to calculations of practical interest.

Question 7

Explain the role of uncertainty quantification in a validation procedure:

Answer 7

1. Helps to estimate the level of confidence in computational results.
2. Helps to compare the computed results with experimental data / other models to determine the accuracy.
3. Helps to identify the sources of uncertainty in the computational model + assess their impact on the results.
4. Helps to determine the range of values that the computed results can take due to uncertainty in the input data / model parameters.
5. Helps to improve the accuracy of the computational model by identifying the areas that require more accuracte data / parameter values.

Question 8

In the context of verifying a computer simulation program, outline the concept of a manufactured solution

Answer 8

1. Manufactured solution = analytic function used to test the accuracy of a computer simulation program.
2. Chosen to satisfy the differential equation being solved, as well as any necessary boundary conditions.
3. Used to compute the RHS of differential equation, which is then used as input to simulation program.
4. Simulation program is run using manufactured solution & resulting numerical solution is compared to manufactured solution to compute the error.
5. error can be calculated at each point or using the L2 error norm

Question 9

In the context of verifying a computer simulation program, explain how a manufactured solution can be used as part of a correctness test.

Answer 9

• Manufactured solution can be used to test the accuracy of the simulation under different conditions (different boundary conditions, nonlinearities, other sources of complexity)
• can also be used to verify the order of accuracy of the simulation program (rate at which the error decreases as the grid spacing is decreased)

Question 10

Consider a mass, m, connected to a spring with force constant, k, with a nonlinear perturbation characterised by a parameter, α, such that:
F(x) = -kx(1+αx^3)
Write down the equation(s) of motion for this mass, and suggest a suitable numerical procedure for finding a solution.

Answer 10

Equation of motion - derived from newtons second law.
F(x) = -kx (1 + ax^3)
m d^2x/dt^2 = -kx - k α x^4
m d^2x/dt^2 + kx + kαx^4 = 0

Can be solved using 4th order Runge Kutta method: (RK-4)

Question 11

Suggest a suitable manufactured solution for this nonlinear problem, and derive the required manufactured source term. Hence write down the modified equations of motion to be solved in a verification exercise using the method of manufactured solutions.

Answer 11

Question 12

This question deals with concepts relating to High Performance Computing.
Describe the Strong scaling used to assess parallel performance. State what it reveals about an application.

Answer 12

Strong scaling
1. Run time for a given problem size vs number of processors.
2. Size of problem is fixed, number of processors increased.
3. Reveals how well the parallel algorithm can solve a problem faster as the number of processors is increased
4. Ideally, computation time should decrease as the number of processors increases.
5. Reveals the degree of parallelisation efficiency

Question 13

This question deals with concepts relating to High Performance Computing.
Describe the weak scaling used to assess parallel performance. State what it reveals about an application.

Answer 13

Weak scaling
1. problem size is increased proportionally with the number of processors.
2. ideally, computation time should remain constant as the number of processors increases.
3. reveals the stability of an application

Question 14

What function call must be made before a call to MPI_Bcast?

Answer 14

Before MPI_Bcast, MBI_Init must be called to initialise the MPI environment

Question 15

Describe the operation of MPI_Bcast ensuring that the function definition is referred to in the answer.

Answer 15

MPI_Bcast - collective communication routine in MPI library.
- broadcasts a message from the process with rank ‘root’ to all other processes in the communicator ‘comm’

Function arguments:
- buffer - pointer to the buffer containing the data to be broadcasted,
- count - number of data items to broadcast
- datatype - datatype of each data item
- root - rank of the process sending the message
- comm - communicator that defines the group of processes involved in the broadcast.

MPI_Bcast operation works as follows:
1. process with rank ‘root’ copies the data into the buffer to its own local buffer
2. the root process sends this local buffer to all other processes in the communicator ‘comm’
3. Each receiving process receives the broadcasted data and stores it in its local buffer

Question 16

Why might this be used in place of MPI_Send and MPI_Recv operations.

Answer 16

Can be used in place of MPI_Send and MPI_Recv when the same data needs to be sent from one process to all other processes in the communicator, reducing the amount of code needed.

Question 17

Explain the concept of granularity.

Answer 17

• Computation to Communication ratio
• Level of detail in a simulation / computation.
• Determines the accuracy and computational cost of a simulation.
• Can also refer to level of parallelism in computation (size of work units assigned to different processors in a parallel algorithm)

Question 18

Discuss fine grained applications

Answer 18

1. Frequent communication
2. Opportunity for load balancing
3. Limited potential for optimisation
4. Have small units of work that can be executed independently and concurrently by multiple processing elements.
5. Suitable for problems with a high degree of parallelism, such as particle simulations or numerical integration.
6. Can achieve high levels of concurrency and potentially good load balancing.
7. Require frequent communication between processing elements, which can limit scalability and efficiency.
8. May have limited potential for optimisation due to the overhead of communication and synchronisation.
9. May require more low-level programming and synchronisation

Question 19

Discuss coarse-grained applications

Answer 19

1. High computation to communication
2. Load balancing difficult
3. Optimisation more efficient
4. Have larger units of work that are assigned to fewer processing elements.
5. Are suitable for problems with a lower degree of parallelism, such as large-scale simulations or data analytics.
6. Have a higher computation-to-communication ratio, which can improve scalability and efficiency.
7. May have more challenging load balancing requirements, especially if the workload is not evenly distributed.
8. May have more opportunities for optimisation, such as cache optimisation or vectorisation.
9. May be more amenable to high-level programming models such as OpenMP or MPI.

Question 20

Describe the 2 types of communication available in the Message Passing Interface and give an example of each with a brief explanation of its use POINT-TO-POINT COMMUNICATION

Answer 20

• Communication between specific pairs of processes, known as the source and destination processes.
• Can be used for sending / receiving data from one process to another.
• Examples MPI_Send and MPI_Recv functions
• Usage: Process A can use MPI_Send to send data to process B, and process B can use MPI_Recv to receive the data from process A
• e.g. In a molecular dynamics simulation - each process may represent a different portion of the system. Processes need to exchange information about positions and velocities of the particles at regular time steps to update the simulation.

Question 21

Describe the 2 types of communication available in the Message Passing Interface and give an example of each with a brief explanation of its use COLLECTIVE COMMUNICATION

Answer 21

• Involves communication among a group of processes collectively.
• Can be used for broadcasting data to all processes, reducing data across processes, or gathering data from all processes.
• Examples - MPI_Bcast, MPI_Reduce, MPI_Gather
• Usage - Process A can use MPI_bcast to broadcast data to all other processes in the group, or process B can use MPI_Reduce to reduce data across all processes in the group.
• e.g. In a large scale parallel simulation of fluid dynamics - each process may compute local properties of the fluid in its subdomain. At certain time steps, the processes need to exchange boundary data with their neighbours to compute the global properties of the fluid, such as pressure or velocity.

Question 22

Distinguish, with exampes, between parametric uncertainty and parametric variability. PARAMETRIC UNCERTAINTY

Answer 22

– Parametric uncertainty A parameter has a definite value, but we don’t know what that value is (e.g. a rate constant)

• Refers to the lack of knowledge or precision in determining the values of input parameters
• Can arise from measurement errors, limited data, or assumptions in a model
• Often described using probability distributions or ranges of possible values for a parameter
• Requires probabilistic methods to quantify and propagate the uncertainty through the simulation

EXAMPLE - In a computational fluid dynamics simulation, the viscosity of a fluid is an input parameter that affects the behaviour of the flow. The viscosity may be measured with some uncertainty, and this uncertainty can propagate through the simulation, leading to uncertainty in the results.

Question 23

Distinguish, with exampes, between parametric uncertainty and parametric variability. PARAMETRIC VARIABILITY

Answer 23

– Parametric variability We are simulating an experimental situation that is not exactly reproducible (the normal situation). So some parameters do not have well-defined values

• Refers to the inherent variability or randomness in the values of input parameters
• Can arise from physical or biological variability in a system or process
• Often described using statistical distributions that reflect the variability in the parameter values
• Requires stochastic methods to account for the variability in the simulation

EXAMPLE - In a population dynamics model, the birth rate of a species is an input parameter that can vary across individuals or populations. The birth rate may be modeled using a statistical distribution that reflects the variability in the parameter values, and the simulation can be run multiple times with different values of the parameter to account for the variability.

Question 24

Discuss how a Monte Carlo procedure could be used to estimate the influence of parametric uncertainty on the outcome of a computer simulation procedure?

Answer 24

”” “” by randomly sampling values from the input parameter distributions and running the simulation multiple times. The results from the simulation runs can then be analyzed to estimate the uncertainty and variability in the simulation output due to the uncertainty in the input parameters.

1. Define the input parameter distributions: For each uncertain input parameter, specify the probability distribution or range of possible values based on available information, such as experimental data or expert knowledge.
2. Generate random samples: Use a random number generator to generate a large number of random samples from each input parameter distribution. The number of samples should be large enough to achieve a desired level of statistical accuracy.
3. Run simulations: For each set of input parameter values, run the computer simulation to generate the corresponding output.
4. Analyze results: Calculate statistics such as mean, standard deviation, and percentiles for the simulation output over all the runs. 5. These statistics can be used to estimate the uncertainty and variability in the simulation output due to the uncertainty in the input parameters.
5. Sensitivity analysis: Conduct a sensitivity analysis to determine which input parameters have the greatest influence on the simulation output. This can be done by calculating the correlation coefficients between each input parameter and the simulation output.

Question 25

Answer 25

Question 26

2 types DECOMPOSITION

Answer 26

2 types: Task parallelism & data parallelism

Task parallelism: used to parallelise the independent algorithms A, B and C by running them concurrently on 3 different processes. Each process performs a different task, and the tasks are executed in parallel, thus reducing the overall execution time.

Data Parallelism: Used to parallelise the matrix operation in D. The matrix is partitioned into smaller sub-matrices, and each sub-matrix is processed by a different process in parallel. This approach allowed multiple processes to work on different parts of the matrix simultaneously, which can significantly reduce the overall execution time.

Question 27

Explain the concept of ranking of uncertain parameters.

Answer 27

1. Process of identifying and prioritising the most important parameters in a simulation model that have the greatest impact on the output.
2. An important tool for uncertainty quantification and sensitivity analysis in computational physics.
3. The ranking of uncertain parameters helps to reduce the dimensionality of the problem by focussing on a subset of parameters that have the greatest impact.
4. This approach can simplify the calibration, validation, and optimisation of the simulation model and improve its accuracy and reliability.

Question 28

Explain the usefulness of ranking of uncertain parameters:

Answer 28

1. This method economises on the number of model evaluations, and guarantees to generate an elementary effect for each uncertain parameter
2. helps to identify the most important parameters in a simulation model, guiding researches to focus their efforts and resources on the parameters that have the highest impact on the output of the model.
3. Increases the transparency and credibility of the Simulation model, allowing researchers to explain and justify the choices and assumptions made in the model calibration and validation process.
4. Can help to identify areas of the model that need improvement or further investigation, such as parameters that have high uncertainty or that are highly sensitive to changes in the model.
5. Can help to improve the accuracy and reliability of the simulation model, as the focus is on the parameters that have the greatest impact on the output.

Question 28

Outline how the Morris Method may be used to establish a parameter ranking.

Answer 28

1. Morris method identifies important parameters in a simulation model.
2. It requires defining ranges of uncertain parameters and generating parameter sets.
3. Model output is evaluated for each parameter set and elementary effects are calculated.
4. Morris indices are calculated from the average and standard deviation of elementary effects to rank parameters.
5. Robustness of rankings is checked by performing the method on multiple independent sets of parameter samples.

Question 29

WILL A FUNCTIONAL DECOMPOSITION STRATEGY WORK FOR THIS PROBLEM?

Answer 29

May not be the most effective approach because algorithm A, B and C cannot themselves be parallelised.

In a functional decomposition strategy, the problem is decomposed into a set of functions or subroutines that can be executed in parallel.

In this case, the independent algorithms A, B, and C cannot be further decomposed into smaller functions that can be executed independently.

Question 30

Answer 30

– Fraction of the code that can be parallelised is now 1/4, since only D is left to be parallelised.
– Assuming perfect parallelism for D, this means that the parallel portion of the code can be run in 1/8th of the original time (since there are 8 processes available)
– Therefore, the maximum theoretical parallel speedup can be calculated using Ahmdals law as:
Maximum speedup = 1/[(1-1/4) + (1/4)/8] = 1/(3/4 + 1/32) = 1/(25/32) = 1.28

So the maximum theoretical parallel speedup for the new application is 1.28

Question 31

Answer 31

Question 32

Answer 32

Question 33

DESIRABLE PROPERTIES

Answer 33

1. it is symplectic - preserves the Hamiltonian structure, and hence the energy conservation property of the system.
2. It is time-reversible - can be run forwards / backwards in time with equal accuracy.
3. It is second-order accurate in time - error in integration decreases quadratically with decreasing time step size.
4. It is computationally efficient, requiring only one function evaluation per time step size.

Question 34

Better suited to problems that have what characteristics

Answer 34

1. the system is conservative - energy is conserved over time.
2. The system has a periodic / oscillatory behaviour.
3. The system has a well-defined Hamiltonian structure (can be described in terms of its position and momentum)

Compared to Runge-Kutta methods, Leapfrog is advantageous for long-term problems / those that require high accuracy. It is therefore more computationally efficient better with long term stability properties

Question 35

Answer 35

Question 36

How does the numerical solution behave if this constraint is violated?

Answer 36

If the constraint ω_0Δt > 2 is violated, then the numerical solution behaves in the following ways:

1. The numerical solution becomes unstable and oscillates with an amplitude that grows with time.
2. The solution may diverge to infinity or oscillate with an amplitude that is not physically realistic.
3. The energy of the system may increase with time, which is not possible for a conservative system.
4. The numerical solution may fail to converge or converge slowly, leading to inaccurate results.

Question 37

The leapfrog method may be used as a building block in more complex simulations, where ω_0 represents some characteristic frequency of the system, but the phenomena of interest involve much smaller frequencies. In effect, the system is stiff. Explain briefly why stiffness is a problem in this context.

Answer 37

1. Stiffness is a problem because the time step required to accurately resolve the stiff dynamics is often much smaller than the tilmestep requires to resolve other, non-stiff dynamics in the system.
2. This means that using a fixed time step for the entire simulation can result in very slow simulations, since the time-set must be set to the size required by the stiff dynamics.
3. Alternatively, if a larger time step is used, the numerical solution may become useable and diverge from the true solution due to numerical error.
4. Stiffness can also make the simulation more difficult to parallelise, since different processes may meed to use different time steps to accurately resolve the dynamics.

Question 38

The leapfrog method may be used as a building block in more complex simulations, where ω_0 represents some characteristic frequency of the system, but the phenomena of interest involve much smaller frequencies. In effect, the system is stiff. What solution is usually adopted in such a case?

Answer 38

1. Implicit methods - treat the stiff terms implicitly and the non-stop terms explicitly. They are generally more stable and can handle larger time steps than explicit methods.
2. Operator splitting - splits the system of equations into stiff and non-stiff parts and treats each part separately using appropriate numerical methods.
3. Extrapolation and deferred correction - use multiple evaluations of a less accurate method to approximate a higher-order method, allowing for larger time steps to be taken, especially useful in cases where the stiffness varies over time

Question 39

INVESTIGATE STABILITY

Answer 39

Question 40

COMMENT ON SUITABILITY OF METHOD IN CONTEXT

Answer 40

1. In the context of solving stiff differential equations, an implicit integration scheme can be beneficial as it can handle stiffness better than explicitly schemes.
2. However the stability of this specific implicit leapfrog scheme is limited by the value of ω_0Δt.
3. if the stiffness of the problem is such that ω_0Δt > 2, this method would not be suitable, and an alternative implicit scheme should be considered for better stability

Question 41

Answer 41

Question 42

Answer 42

1. The backward Euler method for integrating the ODE dy/dx = -y is given by the equation y_{n+1} = y_n - Δx y_{n+1}, where y_{n+1} is the value of y at the next time step and y_n is the value of y at the current time step.
2. The backward Euler method is an implicit method, meaning that y_{n+1} appears on both sides of the equation and needs to be solved for iteratively.
3. The backward Euler method is unconditionally stable, meaning that it is always stable for any choice of Δx.
4. Unlike the forward Euler method, which becomes increasingly unstable as Δx is increased, the backward Euler method remains stable for any Δx. However, it may become computationally expensive as Δx is decreased, as more iterations are required to solve for y_{n+1}.

Question 43

Explain the concept of stiffness in a system of ordinary differential equations.

Answer 43

1. refers to a situation where the solution of a system of differential equations changes very rapidly in some variables but very slowly in others.
2. It occurs when the system has widely different characteristic time scales.
3. The can cause numerical integration methods to become unstable or require very small time steps to maintain stability, leading to slow convergence and computational inefficiency.

Question 44

With reference to your answers to the forward Euler part and the backward Euler part, explain why an implicit integration scheme is desirable when dealing with stiff systems.

Answer 44

Forward Euler method:
1. An explicit integration method that can be unstable for stiff systems.
2. The algorithms behaviour for various step sizes is dependent on the size of the time step, with the solution becoming more unstable as the step size increases.

Backward Euler method:
1. An implicit integration method that can be more stable for still systems than explicit methods.
2. The algorithm is unconditionally stable for any step size, but its accuracy decreases as the step size increases.

Desirability of simplicity integration:
1. They are unconditionally stable and can handle large step sizes, unlike explicit methods.
2. Use the current time step and the next time step to compute the solution, making them less sensitive to the system’s stiffness.

Question 45

Comment on the difficulties involved in implementing an implicit solver for stiff systems.

Answer 45

1. Require solving a system of nonlinear equations at each time step, which can be computationally expensive.
2. The convergence of the iterative solution of the nonlinear system can be slow, particularly when the stiffness is severe.
3. The choice of the initial guess for the iterative solver can be critical for achieving convergence.
4. The stiffness can vary over time, making it challenging to select the best algorithm and time step sizes.