You need to log in to make submissions.
Please read the general instructions for this exercise first. Here are the additional instructions specific to this task:
Try to use Strassen's algorithm to speed up matrix multiplication. Reimplement your solution to CP3b so that it uses the basic idea of Strassen's algorithm. It is sufficient to use the basic idea of Strassen's algorithm (adapted to our task as needed) in the topmost levels of recursion; you can then fall back to the naive algorithm. A pure implementation of the naive algorithm, even if its is sufficiently fast, is not a valid solution for this exercise. Care is needed with rounding errors; you may need to resort to double-precision arithmetic to pass the tests.
I will first run all kinds of tests to see that your code works correctly. You can try it out locally by running ./grading test, but please note that your code has to compile and work correctly not only on your own computer but also on our machines.
If all is fine, I will run the benchmarks. You can try it out on your own computer by running ./grading benchmark, but of course the precise running time on your own computer might be different from the performance on our grading hardware.
| Name | Parameters |
|---|---|
| benchmarks/1 | nx = 1000, ny = 1000 |
| the input contains 1000 × 1000 pixels, and the output should contain 1000 × 1000 pixels | |
| benchmarks/2a | nx = 1000, ny = 4000 |
| the input contains 4000 × 1000 pixels, and the output should contain 4000 × 4000 pixels | |
| benchmarks/2b | nx = 1000, ny = 4000 |
| the input contains 4000 × 1000 pixels, and the output should contain 4000 × 4000 pixels | |
| benchmarks/2c | nx = 999, ny = 3999 |
| the input contains 3999 × 999 pixels, and the output should contain 3999 × 3999 pixels | |
| benchmarks/2d | nx = 1001, ny = 4001 |
| the input contains 4001 × 1001 pixels, and the output should contain 4001 × 4001 pixels | |
| benchmarks/3 | nx = 6000, ny = 6000 |
| the input contains 6000 × 6000 pixels, and the output should contain 6000 × 6000 pixels | |
| benchmarks/4 | nx = 9000, ny = 9000 |
| the input contains 9000 × 9000 pixels, and the output should contain 9000 × 9000 pixels | |
In this task your submission will be graded using benchmarks/4: the input contains 9000 × 9000 pixels, and the output should contain 9000 × 9000 pixels.
The point thresholds are as follows. If you submit your solution no later than on Sunday, 02 June 2024, at 23:59:59 (Helsinki), your score will be:
| Running time | Points |
|---|---|
| ≤ 8.000 sec | 1 |
| ≤ 4.500 sec | 2 |
| ≤ 3.000 sec | 3 |
| ≤ 2.200 sec | 4 |
| ≤ 1.500 sec | 5 |
If you submit your solution after the deadline, but before the course ends on Sunday, 02 June 2024, at 23:59:59 (Helsinki), your score will be:
| Running time | Points |
|---|---|
| ≤ 4.000 sec | 1 |
| ≤ 2.500 sec | 2 |
| ≤ 1.500 sec | 3 |