# Assignment: matrix multiplication

Download this crate for the fourth homework assignment. It contains some tests, benchmarks, and function prototypes.

## 1 Matrix data type

In this homework assignment, you will implement a small matrix data structure and some matrix operations. The provided Matrix struct wraps Vec to store the matrix data as a contiguously. When storing a matrix such as:

We can store data by row or by column:

row:    [1, 2, 3, 4, 5, 6, 7, 8, 9]
column: [1, 4, 7, 2, 5, 8, 3, 6, 9]


These are the row-major and column-major orders. You can find more information in the Wikipedia page about orders. The Matrix struct also has a field order that describes the storage order of the matrix.

### 1.1 Implement get/set

Implement the get/set methods of Matrix. These methods should get/set the matrix cell with the given row/column. The methods should take Order into account in mapping a matrix cell to the underlying Vec.

You can test your implementation using cargo test get and cargo test set.

Note: if the compiler fails because of inclusive ranges (..=), make sure that you are running Rust 1.26 or later. You can update Rust by running rustup update in a terminal.

### 1.2 Implement matmul

Implement the matmul function, which should compute the matrix multiplication $\mathbf{C}=\mathbf{A}\mathbf{B}$, where $\mathbf{A}$ is self and $\mathbf{B}$ is other. The cell $c_{ij}$ (row $i$, column $j$) of $\mathbf{C}$ is computed as

Implement the $\mathcal{O}(n^3)$ algorithm for matrix multiplication by filling every cell of $\mathbf{C}$ using this equation.

### 1.3 Implement frobenius_norm

Implement the frobenius_norm function, which should compute the Frobenius norm of the matrix:

This norm is often used as a penalty in machine learning to avoid extreme parameters.

# 2 Performance

### 2.1 Matrix orders

Run cargo bench matmul. This benchmarks matrix multiplications of matrices $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{200 \times 200}$ (that is, both matrices have 200 rows and columns) of the following orders:

• row-major, row-major
• row-major, column-major
• column-major, row-major
• column-major, column major

The running times for these should be nearly the same.

Now change the constants in benches/matrix.rs to M=1, N=4000, O=4000. This gives us matrices with dimensionalities $\mathbf{A} \in \mathbb{R}^{1 \times 4000}, \mathbf{A} \in \mathbb{R}^{4000 \times 4000}$. The running times should now differ (if they do not, try increasing 4000 to a larger number).

Explain the differences in running times in general and how they affect each combination of orders.

### 2.2 Order checks

Calls to get/set check the order of a matrix to compute the index. Describe the overhead as accurately possible. You could use cargo asm to inspect the machine code.

## Submission

• Submit your updated project, archived as a tar.gz or zip file.
• Include the first names of the team members in the archive name.
• Run cargo clean before archiving the project.
• Your answers to 2.1 and 2.2 must be included as a plain text file (not PDF, Word, etc.) in the main project directory.

The tar.gz or zip file should be uploaded through this page. The deadline is May 29 at 13:00.