Matrix Arithmetic Library and Strassen Algorithm Implementation

Posted on Edited on Views: Word count in article: 167 Reading time ≈ 1 mins.

This post details my project for the CSE203B course, Design and Analysis of Algorithms B1, in which I led a team of four students. Our main task was to implement Strassen algorithm, a classic example of recursion. To fully embrace this challenge, we opted to develop our own matrix library rather than relying on NumPy. This project was my first taste of Python OOP and magic methods -- and it was enjoyable!

Visit our GitHub repo to know more about this project. The following images are from the report we wrote.

Compared to the traditional approach, our algorithm achieved the expected speed up, with the runtime aligning closely with the theoretical \(O(n^{2.81})\).

Runtime comparison

Profiling the tool to identify performance bottlenecks:

Performance

As a side note, I achieved 100/100 on the final exam and for the course overall. Our project received a full scored of 30/30.

  1. CSE203B is the equivalent of CSE203 for non-CSE majors.↩︎