Description

 

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.

 

 

Sparse matrices collection

Sparse matrices can be found in the SuiteSparse Matrix Collection at the link: https://sparse.tamu.edu/

 

The SuiteSparse Matrix Collection (formerly known as the University of Florida Sparse Matrix Collection), is a large and actively growing set of sparse matrices that arise in real applications. The Collection is widely used by the numerical linear algebra community for the development and performance evaluation of sparse matrix algorithms.

Note that you can search square matrices or example filtering by keyword “linear systems” and set the constant vector b as a vector of ones (or zeros).