Convergence of Iterations

The provided content appears to be a series of numerical values, likely representing the results of an iterative process. The numbers are grouped into 50 sets (It=1 to It=50) with each set having four values (x[0], x[1], x[2], and x[3]). The purpose of this data is unclear, but it may be related to a mathematical or computational problem.

U08079 Coursework 2017
Optimizing a solution to a modelling problem
For the coursework you are required to design, implement and optimise a
program to solve resistor networks.
A basic example Jacobi program is provided but this program is inefficient and
you are required to improve it. You should make use of a range of code
optimisation techniques and verify their effectiveness using benchmarking.
You may need to create and solve some reasonably large resistor networks to
demonstrate the effectiveness of some of the optimisations.
In addition to optimising the program on a single PC, you are also required to
implement a version of your program on the department HAC cluster using
message passing with MPI in order to investigate possible speedup and other
optimisations by employing multiple processes running on multiple
processors.
The Problem
A resistor is an electronic component that reduces the current and voltage of
an electrical signal. The diagram below shows a number of resistors forming
an electronic circuit. The green boxes represent resistors and the lines
represent wires (or nodes) connecting them together. Each resistor has a
value, in ohms, showing how powerful a resistor it is. More ohms means a
more powerful resistor, which resists more, and thus lowers voltage further.
The problem is to calculate the voltages at nodes v2 and v3. Note the left
node is connected to a fixed 6 volt supply and the right node is connected to
fixed 0 volts. There are two relevant electrical laws we can use to solve this
problem:
Kirchhoff’s Law: the net current at a node is zero, so current in must equal
current out at each circuit node. (Note that current is not the same as voltage.)
Ohm’s Law: If a resistor has a resistance of R ohms, and the voltage across
the resistor (i.e. the difference between the input and output voltages) is V
volts, then the current flowing through the resistor is I=V/R amps.
You can also utilise the fact that current flows from points of high voltage to
points of low voltage.
C Cox 21.2.2017
1 6
3
36v V2 V3 0v 



Using these laws, we can derive a system of equations which we can then
solve to give the voltages v2 and v3.
Hand calculation for the above example:
Node v2 has an input from the 1 ohm resistor.
By Ohm’s law the current in from this resistor is (6-v2)/1 (6 is the input
voltage, v2 is the node voltage which we want to find, and 1 is the ohm rating
of the resistor.)
Node V2 outputs to the 6 ohm and the 3 ohm resistor.
By Ohm’s law the current out to the 6 ohm resistor is (v2-v3)/6,
and the current out to the 3 ohm resistor is (v2-v3)/3.
By Kirchhoff’s law the current at the inputs and outputs of V2 must be the
same, so (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3
At node v3 we consider the inputs and outputs similarly:
The two input resistors will have currents of (v2-v3)/6 and (v2-v3)/3
and the output resistor will have a current of (v3-0)/3.
So (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.
Now we have two equations to solve simultaneously:
(6-v2)/1 = (v2-v3)/6 + (v2-v3)/3
(v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.
Simplifying the first equation:
Start with (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3
Dividing by one does nothing (6-v2) = (v2-v3)/6 + (v2-v3)/3
Multiply all by 6 to remove /6 6(6-v2) = (v2-v3) + 2(v2-v3)
Carry out multiplications 36 – 6v2 = v2-v3 + 2v2 – 2v3
Collect terms 36 – 6v2 = 3v2 – 3v3
Add 6v2 to both sides, to move it 36 = 9v2 – 3v3
Divide through by 3 to lower numbers 12 = 3v2 – v3
Same with the second equation:
Start with (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3
Subtracting 0 does nothing (v2-v3)/6 + (v2-v3)/3 = v3/3
Multiply all by 6 to remove /6 (v2-v3) + 2(v2-v3) = 2v3
Carry out multiplications v2-v3 + 2v2 – 2v3 = 2v3
Collect terms 3v2 – 3v3 = 2v3
Subtract 2v3 from both sides 3v2 – 5v3 = 0
We now have two equations of the form:
3v2 – 1v3 = 12
3v2 – 5v3 = 0
Which we can easily solve as a simultaneous equation as v2=5 and v3=3
Notice that for a general resister network:
 We will end up with one equation per node;
 Each of these equations will have one v term for each node voltage.
C Cox 21.2.2017

So if we had 4 nodes, we would obtain four equations, each of the form
?v2 + ?v3 + ?v4 + ?v5 = ?.
This would be much more difficult to solve manually, hence the need for the
Jacobi algorithm.
Thus the complexity of solving the equations increases with each extra node
in the system, which is why this problem requires optimization.
The Jacobi algorithm can be used to solve sets of equations of this type. To
use it we first represent the equations as a matrix multiplication, actually to
multiply an nxn matrix by a vector of size n. In our example n=2:
Note that the elements of the matrix correspond to the coefficients in the
equations.
3v2 – 1v3 = 12
3v2 – 5v3 = 0
The Jacobi algorithm is based on guessing an initial solution (all nodes set to
1 volt in the example program) and then refining it over a number of iterations.
Here is the C source code for a simple implementation. Note the coefficients
from the above equations as values of matrix m and vector b:
Note we use a 2-D n x n array for the matrix m and a 1-D array size n for the
vector b.
#include <stdio.h>
// Number of nodes
#define n 2
int main()
{ // Matrix of coefficients
const double m[n][n]={{3.0,-1.0}, {3.0,-5.0}};
// Vector of results
const double b[n]={12.0,0.0};
// Arrays used for storing guesses
double x[n], new_x[n];
double sum;
// How many iterations to do – the more the better the answer
const int MaxIts=30;
int Its,i,j;
// Start with all guesses at 1
for(i=0;i<n;i++) x[i]=1.0;
// Perform MaxIts iterations
for(Its=1;Its<=MaxIts;Its++)
{ // Print out the iteration we are on
printf("Its=%d",Its);
// This is the actual Jacobi algorithm
// Calculate our next round of guesses in max_i[]
for(i=0; i<n; i++)
{ sum=0.0;
for(j=0;j<n;j++)
C Cox 21.2.2017

if(i!=j)sum+=m[i][j]*x[j];
new_x[i]=(b[i]-sum)/m[i][i];
}
// Update current guesses for the new round and print them out
for(i=0;i<n;i++)
{ x[i]=new_x[i];
printf(" x[%d]=%12.8f",i,x[i]);
}
printf("\n");
}
return 0;
}
Here is an example of this program running on the problem above:
Its=1 x[0]= 4.33333333 x[1]= 0.60000000
Its=2 x[0]= 4.20000000 x[1]= 2.60000000
Its=3 x[0]= 4.86666667 x[1]= 2.52000000
Its=4 x[0]= 4.84000000 x[1]= 2.92000000
Its=5 x[0]= 4.97333333 x[1]= 2.90400000
Its=6 x[0]= 4.96800000 x[1]= 2.98400000
Its=7 x[0]= 4.99466667 x[1]= 2.98080000
Its=8 x[0]= 4.99360000 x[1]= 2.99680000
Its=9 x[0]= 4.99893333 x[1]= 2.99616000
Its=10 x[0]= 4.99872000 x[1]= 2.99936000
Its=11 x[0]= 4.99978667 x[1]= 2.99923200
Its=12 x[0]= 4.99974400 x[1]= 2.99987200
Its=13 x[0]= 4.99995733 x[1]= 2.99984640
Its=14 x[0]= 4.99994880 x[1]= 2.99997440
Its=15 x[0]= 4.99999147 x[1]= 2.99996928
Its=16 x[0]= 4.99998976 x[1]= 2.99999488
Its=17 x[0]= 4.99999829 x[1]= 2.99999386
Its=18 x[0]= 4.99999795 x[1]= 2.99999898
Its=19 x[0]= 4.99999966 x[1]= 2.99999877
Its=20 x[0]= 4.99999959 x[1]= 2.99999980
Its=21 x[0]= 4.99999993 x[1]= 2.99999975
Its=22 x[0]= 4.99999992 x[1]= 2.99999996
Its=23 x[0]= 4.99999999 x[1]= 2.99999995
Its=24 x[0]= 4.99999998 x[1]= 2.99999999
Its=25 x[0]= 5.00000000 x[1]= 2.99999999
Its=26 x[0]= 5.00000000 x[1]= 3.00000000
Its=27 x[0]= 5.00000000 x[1]= 3.00000000
Its=28 x[0]= 5.00000000 x[1]= 3.00000000
Its=29 x[0]= 5.00000000 x[1]= 3.00000000
Its=30 x[0]= 5.00000000 x[1]= 3.00000000
Note that a reasonably accurate solution is obtained here within 30 iterations.
This basic program simply limits the number of iterations, but it would be
preferable to loop until a specified convergence accuracy level is achieved.
You should also be aware of the limited precision of floating point or double
precision values stored on a computer.
Coursework Specification
Your program should solve resistor networks using the Jacobi algorithm. It
must be written in C++ and should demonstrate good software development
and programming practice. It should also be optimised as far as possible to
give fast but reliable performance.
C Cox 21.2.2017

The Jacobi algorithm can be implemented as a stand-alone program, as a
single program which creates multiple threads, or as a distributed program in
which the processing is shared between several computers as follows.
A basic implementation is suggested first. This will:
 Input, or create, data for a resistor network to obtain a matrix of
coefficients and a vector of target values. It is allowed to have the data
hard-wired into your program, or input from a file, or the data could be
computed as needed.
 Implement the Jacobi algorithm as a single process. You should
confirm that it returns the correct solution and you should also add a
method to detect convergence as well as confirm its effectiveness.
 There is no need, or extra marks awarded, for a graphical user
interface. Therefore a command line interface is acceptable.
A locally parallel implementation should then be implemented, which uses
threading and messaging to make optimal use of multiple processor cores on
a single machine.
A distributed implementation should then be implemented using MPI on the
department HAC cluster. Initially as a single process, then as a multiprocess
implementation in which the processing of matrix rows is distributed between
several processes across several processors.
An distributed optimised version should consider optimising:
1. The Jacobi code itself
2. The number of processes and processors
3. Message passing to optimise speedup
4. Finally by devising a sparse data structure to store matrix data the
performance as well as memory requirements could be improved.
What is required?
In Week 9 you must demonstrate a basic implementation and a single
computer version using threads during the practical session. You will also be
interviewed about your code and about how it works, and how well you have
optimised it. This demonstration is worth 20% of the coursework mark. You
will be given feedback in the session. The marks will be assigned as:
successful compilation and demonstration 5 marks, software design 5 marks,
explanation of code 5 marks, and code optimisation 5 marks.
In week 11 you must demonstrate a distributed version running on the cluster
using MPI. You will also be interviewed about your code, and about how it
works, and how well you have optimised it. This demonstration is worth 20%
of the coursework mark.
You may also demonstrate your single computer version again at this time, if
you have improved it based on your feedback from week 9. If your mark is
C Cox 21.2.2017

higher than the mark from week 9 you will be awarded the higher mark.
However you cannot be awarded more than double the mark you were given
in week 9. If you did not demonstrate the single computer version in week 9
you will be unable to gain any marks by demonstrating it in week 11.
By the end of week 11 you should submit a final report containing the
following sections:
 Description of the problem and design, especially discussing how you
broke it into parts for parallelism (10%)
 Description of message passing and MPI distributed program design
(10%)
 Discussion of the locally parallel and distributed implementations (10%
each, total 20%)
 Testing and test results including timed benchmarks for both versions
(5%)
 Analysis of the optimisations implemented showing how effective they
have been based on your testing (15%)
You should submit a printed copy of your report to the lecturer or to the
U08079 postbox and an electronic copy uploaded to the Turnitin link.
Additionally all your documentation, code and data should be uploaded as a
single zip file to U08079 Moodle.
The deadline is 5pm Friday 28th April 2017.
A second worked example
Resistor network (a linear chain of 1 ohm resistors)
Equations
At v1: 5-v1 = v1-v2 so -2v1 + v2 = -5
At v2: v1-v2 = v2-v3 so v1 – 2v2 +v3 = 0
At v3: v2-v3 = v3-v4 so v2 – 2v3 + v4 = 0
At v4: v3-v4 = v4-0 so v3 – 2v4 = 0
Matrix and vector
C Cox 21.2.2017
15v V1
1 1 1 1
V2 V3 V4 0v

Notice the regular structure of this matrix. This may provide a clue to
automatically generating matrix data for large networks.
Unoptimized program
(This is the same as the previous program with different data loaded)
#include <stdio.h>
#define n 4
int main()
{ const double m[n][n]={{-2.0,1.0,0.0,0.0}, {1.0,-2.0,1.0,0.0},
{0.0,1.0,-2.0,1.0}, {0.0,0.0,1.0,-2.0}};
const double b[n]={-5.0,0.0,0.0,0.0};
double x[n], new_x[n];
double sum;
const int MaxIts=50;
int Its,i,j;
for(i=0;i<n;i++) x[i]=1.0; /* initialise */
for(Its=1;Its<=MaxIts;Its++)
{ printf("It=%d",Its);
for(i=0; i<n; i++)
{ sum=0.0;
for(j=0;j<n;j++)
if(i!=j)sum+=m[i][j]*x[j];
new_x[i]=(b[i]-sum)/m[i][i];
}
for(i=0;i<n;i++)
{ x[i]=new_x[i];
printf(" x[%d]=%9.7f",i,x[i]);
}
printf("\n");
}
return 0;
}
Result (note v1 is x[0] through to v4 is x[3])
$ ./jacobi
It=1 x[0]=3.0000000 x[1]=1.0000000 x[2]=1.0000000 x[3]=0.5000000
It=2 x[0]=3.0000000 x[1]=2.0000000 x[2]=0.7500000 x[3]=0.5000000
It=3 x[0]=3.5000000 x[1]=1.8750000 x[2]=1.2500000 x[3]=0.3750000
It=4 x[0]=3.4375000 x[1]=2.3750000 x[2]=1.1250000 x[3]=0.6250000
It=5 x[0]=3.6875000 x[1]=2.2812500 x[2]=1.5000000 x[3]=0.5625000
It=6 x[0]=3.6406250 x[1]=2.5937500 x[2]=1.4218750 x[3]=0.7500000
It=7 x[0]=3.7968750 x[1]=2.5312500 x[2]=1.6718750 x[3]=0.7109375
It=8 x[0]=3.7656250 x[1]=2.7343750 x[2]=1.6210938 x[3]=0.8359375
It=9 x[0]=3.8671875 x[1]=2.6933594 x[2]=1.7851562 x[3]=0.8105469
It=10 x[0]=3.8466797 x[1]=2.8261719 x[2]=1.7519531 x[3]=0.8925781
It=11 x[0]=3.9130859 x[1]=2.7993164 x[2]=1.8593750 x[3]=0.8759766
It=12 x[0]=3.8996582 x[1]=2.8862305 x[2]=1.8376465 x[3]=0.9296875
It=13 x[0]=3.9431152 x[1]=2.8686523 x[2]=1.9079590 x[3]=0.9188232
It=14 x[0]=3.9343262 x[1]=2.9255371 x[2]=1.8937378 x[3]=0.9539795
It=15 x[0]=3.9627686 x[1]=2.9140320 x[2]=1.9397583 x[3]=0.9468689
It=16 x[0]=3.9570160 x[1]=2.9512634 x[2]=1.9304504 x[3]=0.9698792
It=17 x[0]=3.9756317 x[1]=2.9437332 x[2]=1.9605713 x[3]=0.9652252
It=18 x[0]=3.9718666 x[1]=2.9681015 x[2]=1.9544792 x[3]=0.9802856
It=19 x[0]=3.9840508 x[1]=2.9631729 x[2]=1.9741936 x[3]=0.9772396
It=20 x[0]=3.9815865 x[1]=2.9791222 x[2]=1.9702063 x[3]=0.9870968
It=21 x[0]=3.9895611 x[1]=2.9758964 x[2]=1.9831095 x[3]=0.9851031
It=22 x[0]=3.9879482 x[1]=2.9863353 x[2]=1.9804997 x[3]=0.9915547
C Cox 21.2.2017

It=23 x[0]=3.9931676 x[1]=2.9842240 x[2]=1.9889450 x[3]=0.9902499
It=24 x[0]=3.9921120 x[1]=2.9910563 x[2]=1.9872369 x[3]=0.9944725
It=25 x[0]=3.9955282 x[1]=2.9896744 x[2]=1.9927644 x[3]=0.9936185
It=26 x[0]=3.9948372 x[1]=2.9941463 x[2]=1.9916465 x[3]=0.9963822
It=27 x[0]=3.9970731 x[1]=2.9932418 x[2]=1.9952642 x[3]=0.9958232
It=28 x[0]=3.9966209 x[1]=2.9961687 x[2]=1.9945325 x[3]=0.9976321
It=29 x[0]=3.9980843 x[1]=2.9955767 x[2]=1.9969004 x[3]=0.9972663
It=30 x[0]=3.9977884 x[1]=2.9974924 x[2]=1.9964215 x[3]=0.9984502
It=31 x[0]=3.9987462 x[1]=2.9971049 x[2]=1.9979713 x[3]=0.9982107
It=32 x[0]=3.9985525 x[1]=2.9983587 x[2]=1.9976578 x[3]=0.9989856
It=33 x[0]=3.9991794 x[1]=2.9981052 x[2]=1.9986722 x[3]=0.9988289
It=34 x[0]=3.9990526 x[1]=2.9989258 x[2]=1.9984670 x[3]=0.9993361
It=35 x[0]=3.9994629 x[1]=2.9987598 x[2]=1.9991309 x[3]=0.9992335
It=36 x[0]=3.9993799 x[1]=2.9992969 x[2]=1.9989967 x[3]=0.9995655
It=37 x[0]=3.9996485 x[1]=2.9991883 x[2]=1.9994312 x[3]=0.9994983
It=38 x[0]=3.9995941 x[1]=2.9995398 x[2]=1.9993433 x[3]=0.9997156
It=39 x[0]=3.9997699 x[1]=2.9994687 x[2]=1.9996277 x[3]=0.9996717
It=40 x[0]=3.9997344 x[1]=2.9996988 x[2]=1.9995702 x[3]=0.9998139
It=41 x[0]=3.9998494 x[1]=2.9996523 x[2]=1.9997563 x[3]=0.9997851
It=42 x[0]=3.9998261 x[1]=2.9998029 x[2]=1.9997187 x[3]=0.9998782
It=43 x[0]=3.9999014 x[1]=2.9997724 x[2]=1.9998405 x[3]=0.9998593
It=44 x[0]=3.9998862 x[1]=2.9998710 x[2]=1.9998159 x[3]=0.9999203
It=45 x[0]=3.9999355 x[1]=2.9998510 x[2]=1.9998956 x[3]=0.9999079
It=46 x[0]=3.9999255 x[1]=2.9999156 x[2]=1.9998795 x[3]=0.9999478
It=47 x[0]=3.9999578 x[1]=2.9999025 x[2]=1.9999317 x[3]=0.9999397
It=48 x[0]=3.9999513 x[1]=2.9999447 x[2]=1.9999211 x[3]=0.9999658
It=49 x[0]=3.9999724 x[1]=2.9999362 x[2]=1.9999553 x[3]=0.9999606
It=50 x[0]=3.9999681 x[1]=2.9999638 x[2]=1.9999484 x[3]=0.9999776
Note that convergence (to more than 5 significant digits) was not reached
within 50 iterations in this case.
C Cox 21.2.2017