[Solved] CSCIUA0480 Lab 1

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 (x₁ to x_n), your program will calculate the values of x₁ to x_n 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 X₁ is 2, for X₂ is 3, and for X₃ 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 dont 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 a_ij and b₁ to b_n. You need to calculate all Xs.

Here are the steps:

1. 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 b₁ to b_n.

In general: n

ci aij xj jj1i x_i aii ,i 1,2,K,n.

2. 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.

3. Substitute the initial values in the equation of X₁ to get new value for X Use that new value as well as the other initial values for X₂ to X_n to get new value for X₂. Then use the new values for X₁ and X₂ and the rest of the initial values to get X_3, and so on.
4. Now we have a new set of Xs.
5. Calculate the absolute relative errors for each X.
6. If all errors are equal or less the given number (2nd line in the file) then you are done.
7. Otherwise go back to step 3 with the set of new Xs as X_old.

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 X₁, 3 corresponds to X_2, and 4 corresponds to X_3, . 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