Performance Evaluation of Strassen Matrix Multiplication algorithms

[SergeyKostrov]

*** Performance Evaluation of Strassen Matrix Multiplication algorithms *** [ Abstract ] In 1969 a German mathematician Volker Strassen has invented a recursive algorithm for multiplication of two square matrices with asymptotic complexity O( n^2.807 ). That was the first matrix multiplication algorithm with asymptotic complexity less than O( n^3 ). Note: 2.807 = log2(7). Two Classic well known Compute Schemas ( CS ) of the algorithm are as follows: Strassen A4B4C4M4T2 ( or ABCMT2 ) Strassen-Winograd A4B4C4S4T4P7U7 ( or ABCST4PU7 ) These algorithms use temporary matrices to store intermediate results and, for example, classic Strassen algorithm uses two T-matrices ( denoted as T2 ). Classic versions of Strassen matrix multiplication algorithm could be classified as Recursive Stack Based ( RSB ) and at every recursion memory for subdivided, or partitioned, temporary matrices is allocated from the stack. Performance of two Heap Based versions of Strassen matrix multiplication algorithm is evaluated. That is, Strassen Heap Based Incomplete ( SHBI ) and Strassen Heap Based Complete ( SHBC ) algorithms with a highly optimized memory usage and Compute Schema A2B2M7 ( or AB2M7 ) without any temporary matrices to store intermediate results. Unofficially, on the ScaLib for BDP project, it is called as Strassen-Kostrov Compute Schema and denoted as A2B2M7. As a reference, performance one of the fastest algorithms for matrix multiplication from Intel MKL ( CBLAS function SGEMM ) is evaluated for every test case. Additional high level technical details about SHBI and SHBC algorithms will be provided. To learn more about Volker Strassen please follow these web-links: . http://www.math.uni-konstanz.de/~strassen http://www.math.uni-konstanz.de/~strassen/publ.html http://www.math.uni-konstanz.de/~strassen/kollegen.html

[SergeyKostrov]

Note / Correction: This is very strange because I've typed a Compute Schema for Classic Strassen as A4B4C4M7T2 but after I've pressed the Submit button it was changed (!) to Strassen A4B4C4M4T2 ( ...M7... was changed to ...M4... ).

[SergeyKostrov]

Attention: The thread is closed - Do Not post anything! The thread is closed and a new one will be created some time later. This is because Intel does Not allow editing of initial post ( Post #1 ) and some corrections are needed. Once again, I decided to close the thread and a new one will be created. Do Not post anything here since I won't follow up that thread and wait for a new thread with the same name. Attention: The thread is closed - Do Not post anything!