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.
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
You can test your implementation using
cargo test get and
cargo test set.
Note: if the compiler fails because of inclusive ranges (
sure that you are running Rust 1.26 or later. You can update Rust by running
rustup update in a terminal.
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.
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.1 Matrix orders
cargo bench matmul. This benchmarks matrix multiplications of matrices (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
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
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.
- Submit your updated project, archived as a
- Include the first names of the team members in the archive name.
cargo cleanbefore 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.
zip file should be uploaded through this page. The deadline is May 29 at 13:00.