Partial strassen algorithm speeds up matrix multiplication with less memory
Part of the Strassen algorithm can speed up matrix multiplication in a parallel pebbling game
Distributed, Parallel, and Cluster Computing
Summary
Matrix multiplication is a key operation in many computer tasks but can be slow and require lots of memory. The authors introduce a new twist on a well-known method called Strassen’s algorithm that only does part of its complex steps, making it both faster and less memory-heavy. Their tests show this partial approach runs quicker than widely used methods and uses memory more efficiently, especially for large matrices. They also provide open source code so others can use and try it on different matrix sizes.
What this means in practice
- •For high-performance computing engineers: Implement faster and more memory-efficient matrix multiplication for large-scale parallel computing tasks.
- •For machine learning infrastructure teams: Optimize matrix operations in training and inference workflows to reduce computational time and memory usage.
Authors
Aaron Dayton, Thomas E. Baker
Abstract
We present a novel variant of the Strassen algorithm called the Partial Strassen algorithm, which uses a fraction of the Strassen steps to perform matrix multiplication in less time than traditional implementations. The memory footprint required to implement this algorithm is provably small whether used with a single thread or in a multi-threaded context. Data comparing the Partial Strassen algorithm at depths one, two, and three with BLAS matrix multiplication show that the three-level Partial Strassen algorithm is able to perform matrix multiplication in $80\%$ the time of BLAS with $2.25$ times the memory requirement, with a theoretical improvement of $75\%$ for sufficiently large matrices. The Partial Strassen algorithm is also compared against an implementation of the traditional Strassen algorithm, and is shown to be more performant with increasing matrix size due to decreased memory consumption. An open source implementation of the Partial Strassen algorithm for arbitrary depth and rectangular matrix multiplication is also included.