Better-than-Cubic Complexity for Matrix Multiplication in Rust
Years ago, I wrote an implementation of the Strassen matrix multiplication algorithm in C++, and recently re-implemented it in Rust as I continue to learn the language. This was a useful exercise in learning about Rust performance characteristics and optimization techniques, because although the algorithmic complexity of Strassen is superior to the naive approach, it has a high constant factor from the overhead of allocations and recursion within the algorithm’s structure.
- The general algorithm
- Transposition for better performance
- Sub-cubic: How the Strassen algorithm works
- Parallelism
- Benchmarking
- Profiling and performance optimization
The general algorithm
The general (naive) matrix multiplication algorithm is the three nested loops approach everyone learns in their first linear algebra class, which most will recognize as O(n³)
0 Comments