Microsoft PowerPoint – Performance-3 [Compatibility Mode]
High Performance Computing
Course Notes
Performance III
Dr Ligang He
2Computer Science, University of Warwick
Time for sending a message
Tmsg=ts+tw * L
Question: How to determine ts and tw
3Computer Science, University of Warwick
Curve fitting
• Suppose that we obtained a set of measurement values,
{(x0, y0), (x1, y1), …, (xn, yn)}, which is called the
measurement sample
• The goal is to obtain a “fitting function”, f(x), that is the
best fit to the data
• The quality of the fitting lies in the residuals:
{ri=yi-f(xi), i=0, 1, …, n}
4Computer Science, University of Warwick
LEAST SQUARES FITTING
5Computer Science, University of Warwick
Linear function
Finding the straight line (slope and intercept) that best fits a set of
data points
So,
6Computer Science, University of Warwick
Polynomial function
Finding the polynomial function that best fits a set of data points. In
this case, the fitting function has the form
f(x)=a0+a1x+a2x
2+…+anx
n
7Computer Science, University of Warwick
Solving partial differential equations
8Computer Science, University of Warwick
Partial differential equations
• Fluid flow can be modelled as partial differential equations
where the velocity potential function is related to the flow
velocity by
• The aim is to find the numerical solution for
9Computer Science, University of Warwick
Numerical solution for partial differential
equations
First, approximating continuous space with a set of discrete
points
Then, finding the value of the function of interest at each
discrete point
The finer points the continuous space is partitioned into, the
more accurate the solution will be
In some situations, it is adequate to partition the space into
a regular grid where the distance between points is uniform
When we need to get more accuracy in certain areas (e.g.
the function changes rapidly), we need to place more points
in those areas
10Computer Science, University of Warwick
Finite volume method for solving
differential equations
A continuous space is broken down into a set of
volumes (cells)
A cell surrounds one of the discrete points
Using these cells to solve φ in the fluid flow problem,
expressed as differential equations
The net flow into a cell has to be zero
We can set up a linear equation for each cell to
express the above relationship
The unknown variables in a linear equation are the
values of the function φ at the points
For n cells, there are n unknown variables and n
equations
11Computer Science, University of Warwick
How to set up the linear equations
Consider this example:
The linear equation for cell 5 can be setup as
We can write similar equations for each of the nine cells, then we get a
set of equations of the form AΦ=b, A is the matrix of the coefficients in
the equations, Φ is the vector with the value of φ to be calculated at
each point
12Computer Science, University of Warwick
Using the iterative method to solve the
linear equations
Aim: solve AΦ=b
Method: repeating iterative steps and each step generates
a better approximation of the solution
Step 1: Guess a initial solution Φ0
Step 2: Check if convergence is reached by checking the
residual b-AΦi
13Computer Science, University of Warwick
Successive Over-Relaxation(SOR)
The SOR method can speed up convergence
For a set of linear equations
let A=D+U+L, where D, L and U denote the diagonal, strictly
lower triangular, and strictly upper triangular parts of A,
respectively
The successive over-relaxation (SOR) iteration is defined by the
recurrence relation
Where values of w > 1 are used to speedup convergence of a
slow-converging process, while values of w < 1 are often help to
establish convergence of diverging iterative process