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:
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:
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?