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 , where is self and is other. The cell (row , column ) of is computed as

Implement the algorithm for matrix multiplication by filling every cell of 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 (that is, both matrices have 200 rows and columns) of the following orders:

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 . 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

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