IC20 Homework 2 Solved

Exercise 1
-  Write a function that implements the Gaussian elimination method.

-  Write a script that calls the function on a sparse matrix (represented in the standard way, without using a compact representation), having a given sparsity value.

-  Use the command spy to visualize the sparsity pattern at each iteration of the Gaussian elimination algorithm and produce a movie to show how the final upper triangular matrix fills up.

-  Compute the sparsity at each iteration and show it on a graph.

 

Exercise 2
-  Write a function for two out of three pivoting technique for the Gaussian elimination method, that is function GEPP for Partial Pivoting, GECP for Complete pivoting, GERP for Rook Pivoting.

-  Write a script that calls each function on random generated matrices of size n= 50, and compute the execution time (using the same matrix for the two chosen techniques), averaging on a set of matrices large enough.

-  For each matrix compute the condition number for linear systems

-  Show on a graph the execution time for the Gaussian elimination without pivoting and for the two pivoting techniques.

 

 Exercise 3
-       Write a function that implements the Jacobi iterative method for a sparse matrix represented using a compact format at your choice.

-       Write a function that implements the Gauss-Seidel iterative method for a sparse matrix represented using a compact format at your choice.

-       Write a script that calls each function on random generated matrices of size n= 50, using the two following criteria for checking the convergence of the two methods:

-        E1: Error obtained by using the exact values (found with Exercise 1 or Matlab function): E1 e(k)  xx(k)   < ε

-        E2: Difference between two successive iterations: E2 e(k)  x(k) x(k1)   < ε

Show E1 and E2 on a graph (to compare the number of iterations needed to stop), averaging on a set of matrices.

 

Exercise 4
-  Implement the Jacobi iterative method for a sparse matrix, represented using a compact format at your choice, using the Parallel toolbox of Matlab.

-  Show on a graph the serial time, the parallel time and the overhead introduced by parallelization (see slides Matlab Part 2, pages 31-55) averaging on a set of matrices.