Candidate: Chongchong Liu
Title: Implementation Analysis of Strassen-Like Matrix Multiplication Algorithms Based on Block Decomposition
Date: February 21, 2019
Time: 10:00am
Place: EIT 3142
Supervisor(s): Hasan, Anwarul M.
Abstract:
Matrix multiplication is one of the most widely used operations in all computational fields of linear algebra. The complexity of the naive method for multiplying two nn matrices requires O() arithmetic operations over the ring in which the matrix entries lie. In 1969, Strassen proposed the first sub-cubic complexity algorithm for matrix multiplication. Strassen's algorithm (SA) multiplies two 22 matrices using 7 multiplications and 18 additions over the ring. Later Winograd proposed a variant of SA that requires 7 multiplications, but 15 additions over the ring. Algorithms that multiply two 22 matrices using 7 multiplications over the ring are called Strassen-like algorithms and have a complexity of O(). Although asymptotically better algorithms exist, Strassen-like algorithms are considered to be most widely used sub-cubic complexity algorithm.
Recently, Cenk and Hasan proposed techniques to reduce the arithmetic cost of Strassen-like algorithms. The main technique is to decompose Strassen-like algorithms into three blocks, namely, component matrix formation (CMF), component multiplication (CM), and reconstruction (R). Each block is a recursive operation. In this thesis, we study these building blocks and investigate three optimization methods: the linearity property of CMF and R, limited recursion, and block recombination.
In this thesis, software implementation and hardware simulation are also performed to support the theoretical analysis. For software implementation, experiment results show that WV is approximately 15% faster than SA. Cenk and Hasan's techniques yield an improved WV (IWV) that considerably reduces the matrix multiplication time in software. For hardware simulation, we conclude from the synthesis results that WV consumes about 7.5% less logic elements than SA. IWV for different matrix sizes are also tested to successfully reduce resource utilization and timing cost.