Informações

Autores Erik-Jan Lingen, Matthias Möller
Prazo de entrega Sem prazo
Limite de submissão No limitation

Entrar

[MPI] Exercise 5 : Gram-Schmidt Algorithm

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.


Task

Implement a parallel program that executes the Gram-Schmidt algorithm to make the columns of an \(N \times N\) matrix \(\mathbf{A}\) orthonormal through a series of dot products and vector subtractions.

The pseudo-code of the Gram-Schmidt algorithm reads as follows:

\begin{align*} &\text{do }j=1,\dots,N\\ &\quad \text{do }k=1,\dots,j-1\\ &\quad\quad c_k := \mathbf{A}_j^\top \cdot \mathbf{A}_k\\ &\quad \text{end do}\\ &\quad \mathbf{A}_j := \mathbf{A}_j - \sum_{k=1}^{j-1} c_k \cdot \mathbf{A}_k\\ &\quad \mathbf{A}_j := \frac{\mathbf{A}_j}{\| \mathbf{A}_j \|}\\ &\text{end do} \end{align*}

Note that \(\mathbf{A}_{j}\) denotes the \(j\)-th column of the matrix \(\mathbf{A}\) and superscript \(\top\) stands for taking the transpose.

The code below show a serial implementation of the Gram-Schmidt algorithm.

In the parallel implementation of the Gram-Schmidt algorithm, the matrix \(\mathbf{A}\) is distributed row-wise over the processors:

05-gram-schmidt-mpi/row-wise-distribution-1.svg

This means that each process stores \(\frac{N}{p}\) rows, with \(p\) the number of processes.

Hints

Use the functions alloc_matrix and free_matrix to create and destroy a matrix with arbitrary dimensions.

Use a global reduction operation to implement a parallel dot product.

What performance do you get?


Questão 1: Gram Schmidt Algorithm
Questão 2: Number of MPI processes

Specify the number of MPI processes (1-64) that should be used for running your program (mpirun -np <nproc>)

Questão 3: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.