Description
In this lab you will implement a method for solving a group of linear equations using MPI.
What will your program do?
Given a set of n equations with n unknowns (x1 to xn), your program will calculate the values of x1 to xn within an error margin of e%. The format of the file is:
- line1: #unknowns
- line2: absolute relative error
- Initial values for each unknown
- line 3 till end: the coefficients for each equation. Each equation on a line. On the same line and after all the coefficients you will find the constant of the corresponding equation.
For example, if we want to solve a system of 3 linear equations, you can have a file like this one: 3
0.01
2 3 4
5 1 3 6
3 7 2 8
3 6 9 6
The above file corresponds to the following set of equation:
5X1 +Â Â Â X2Â + 3X3 = 6
3X1 + 7X2Â + 2X3 = 8
3X1 + 6X2Â + 9X3 = 6
The third line in the file tells us that the initial values for X1 is 2, for X2 is 3, and for X3 is 4. Those values may not be the solution, or are very far from the solution that must be within 1% of the real values (as given by the 0.01 in line 2).
How will your program do that?
You will use Gaussian-Seidel method. OK, I think you don’t know it, do you? Let me be nice and tell you about it.
We start with a set of n equations and n unknowns, like this:
You are given all aij and b1 Â to bn. You need to calculate all Xs.
Here are the steps:
- Rewrite each equation such has the left-hand-side is one of the unknowns.
Note: The Cs above refer to the constants, which are the b1 Â to bn.
In general: Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â n
ci ï€ïƒ¥aij xj        jj1i     xi       aii  ,i 1,2,K,n.
- Remember that you were also given some initial values for the Xs in the input file. The absolute relative error is:
ï‚´100
Therefore, our goal is to reduce absolute relative error for each unknown to make it less or equal to relative error given in the input file (2nd line). Note: You need to multiply the error given in the file by 100 to match it with the above equation, or to not multiply the above equation by 100.
- Substitute the initial values in the equation of X1 to get new value for X Use that new value as well as the other initial values for X2 to Xn to get new value for X2. Then use the new values for X1 and X2 and the rest of the initial values to get X3, and so on.
- Now we have a new set of Xs.
- Calculate the absolute relative errors for each X.
- If all errors are equal or less the given number (2nd line in the file) then you are done.
- Otherwise go back to step 3 with the set of new Xs as Xold.
What is the input to your program?
The input to your program is a text file named xxxx.eq where xxxx can be any name. We already discussed the file format.
What is the output of your program?
Your program must output to stdout (the screen) the value of each unknown. The output must look like:
2
3
4
Where 2 correspond to the value of X1, 3 corresponds to X2, and 4 corresponds to X3, … . In the last line of the output show the number of iterations as: total number of iterations: 5
What do I do after I finish my program?
We have provided you with a reference program gsref so you can check the correctness of your code. We will test your submission against this reference.
After you finish the parallel version of your program, compile it with:
mpicc -o gs gs.c
Where gs.c is your code. We provide a skeleton file to help you start.
After you compile your program and check its correctness do the following:
- Measure the time of your program (using time command) for 1, 2, 4, 8, 16, 32, and 64 processes. You may need to measure the time few times (~ 5) for each and take the average. Do the following with small.txt, medium.txt, and large.txt.
- Draw a graph where the x-axis is the number of processes and the y-axis is the time. There must be 3 curves on the same graph.
- What are your conclusions?
- Draw another graph that shows the speedup (again 3 curves are expected).
- What are your conclusions?
- Include the two graphs and your conclusions in a single pdf file that has your name and titled lab1 submission
