Investigation of efficient methods for the determination of Strassen-type algorithms for fast matrix multiplication

Abstract

Fast matrix multiplication algorithms such as the Strassen algorithm allow for the multiplication of matrices with fewer multiplications than would normally be needed, thus making the calculations more efficient. We introduce an efficient and highly parallelizable method for searching for Strassen-type fast matrix multiplication algorithms for multiplying two 2 x 2 matrices, and discuss its application in searching for algorithms that perform fast matrix multiplies for the 3 x 3 case. Searching for these algorithms is difficult, because the search space of possible algorithms is extremely large. The method introduced in this thesis, for the 2 x 2 case, makes use of a grid representation for the matrix multiplication algorithms, making it easier to view patterns in the algorithms and prune the search space effectively. The method is implemented in the Scilab language and is able to find all Strassen-type fast matrix multiplication algorithms in about 90 minutes of computing time on an Intel Core i7 6700k CPU. Based on the insight we gain from the 2 x 2 case, we provide suggestions for an efficient search method for the 3 x 3 case.