Implement a matrix multiplication algorithm for sparse matrices. Sparse matrices are matrices in which most of the elements are zero, and zero elements do not contribute to the individual dot products computed in the multiplication. The matrix representation is designed to hold only the non-zero elements, and the user can iterate over non-empty rows/columns (and elements of the selected row/column).

You may use Intel TBB, OpenMP, or any C++ STL features to implement the parallel version of the application.

### Implementation details

The framework, serial implementation, and the testing data are available on `parlab.ms.mff.cuni.cz` (SSH runs on port 42222) in the `/home/_teaching/para/labtest` directory. The serial implementation is in `serial.hpp` (the `operator()` of the `SerialImplementation` class). The parallel version should be implemented in `parallel.hpp`, and the `parallel.hpp` file **is the only file you should submit to ReCodEx**.

There are two versions of sparse matrix representations: `SparseMatrixRowMajor` and `SparseMatrixColumnMajor`. The former stores a vector of all rows, where each row is represented by a vector of pairs (column index and value). Only non-zero values are stored in the row vector and the pairs are sorted by column index. Additionally, the matrix holds a list of all row indices that are not empty. The row values are retrieved by the `getRow(rowIndex)` function, and the list of non-empty rows is retrieved by the `getNonEmptyRows()` function. The `SparseMatrixColumnMajor` class is analogous, but it stores columns instead of rows. The column values are retrieved by the `getColumn(columnIndex)` function, and the list of non-empty columns is retrieved by the `getNonEmptyColumns()` function.

Both types of matrices have `get()` and `set()` functions to retrieve and set individual values in the matrix. Additionally, the matrix has `merge(anotherMatrix)` method, which takes another matrix (with distinct non-zero elements) and merges it into the current matrix (efficiently moving elements when possible). This method is can be used to merge the results of parallel computations if individual threads/tasks compute partial results in separate sub-ranges of the output matrix. Please note that all these operations (including `merge`) are not thread-safe.

The first matrix is in the row-major format, and the second matrix is in the column-major format, which is the best representation for the multiplication. The result of the multiplication is a row-major matrix. Please refer to the serial implementation for more details on how to perform the multiplication.

### Evaluation

The datasets for the evaluation are available in `/home/_teaching/para/labtest/data`. The `debug-*` datasets are used for debugging only; ReCodEx testing and performance evaluation will use the three non-debug datasets: `2x3x4`, `4x6x5`, and `8x5x2` (the numbers represent the dimensions of the output matrix and the dot-product size, respectively, in hundreds of thousands). Each dataset has three files with the suffixes `-A`, `-B`, and `-C`, representing the first matrix, the second matrix, and the expected result of the multiplication, respectively. All files are in the `.coot` format, which is our custom text version of the COO sparse matrix representation.

As usual, the harmonic mean of the three speedups will be used to determine your points. The grading table is as follows:

-   7.5× or less: **0 points**
-   7.5× to 15×: **1 point**
-   15× to 25×: **2 points**
-   25× to 40×: **3 points**
-   40× or more: **4 points**

The solutions will be tested using 32 and 64 threads on a single worker, and the better of the two results will be graded.

For your convenience, you can use the `test.sh` script which internally executes (using `srun`) the make, serial, and parallel implementations (with 32 and 64 threads), verifies the correctness of the results, and calculates the (approximate) speedup. The script takes one argument -- the prefix of the dataset (e.g., `./test.sh 2x3x4` will invoke the first dataset). The final testing will be done using more elaborate scripts, but the `test.sh` script should provide a sufficient estimate of your performance.

### Hints

Remember that writing results to the output matrix is not thread-safe. You need to ensure mutual exclusion when calling `set()` from multiple threads or tasks.

Optionally, your solution may use privatization/reduction techniques on the output matrix. Check out the `merge()` method of the matrix, which may be useful for that. Remember that this method is also not thread-safe.