In this assignment you will design and implement a distributed parallel matrix vector multiplication which is a well-known fundamental procedure in the scientific applications. You will implement your algorithm in C, C++ or Python programming language with MPI Library.

In general, matrix vector multiplication is shown in the following form;

y = A * x, or

y=Ax,

where A is a matrix, y and x are the 1-dimensional vectors.

In the parallel environment, each Process P_i may own a row-block of matrix A. For the safe of simplicity, you do not need to partition x vector so that each process may have all elements of x. The resulting vector y will be scattered among all processes, therefore process P_i will be the owner of subvector y_i. After computation of y_i sub-vectors on all processes, P_1 should collect them and write the y vector to a file.

For 4 processes, the vectors y and x, and matrix A can be partitioned as:

You are going to implement 3 programs.

1. Sequential program: Without using any MPI functions, implement a sequential program that multiply a matrix and a vector. Measure the time just for the multiplication and print the elapsed time.

2. Parallel point-to-point Multiplication: By using only point-to-point MPI communication functions, implement a parallel matrix-vector multiplication. Measure the time just for the multiplication and print the elapsed time.

3. Parallel Collective Multiplication: By using only collective MPI communication functions, implement a parallel matrix vector multiplication. Measure the time just for the multiplication and print the elapsed time.

Each program takes 2 inputs for the file name of the matrix and vector.

Each program prints the elapsed time, and write the y vector to the file named y.txt.

You will run your algorithm in multi-processors environment which can be distributed or shared memory.

X P1 P2 P3 w P4