Architecture-efficient Strassen's Matrix Multiplication: A Case Study of Divide-and-Conquer Algorithms

Many fast algorithms in arithmetic complexity have hierarchical or recursive structures that make efficient implementations on high performance computers with memory hierarchies non-trivial. In this paper we present our findings on efficient implementation of Strassen's algorithm[17] for the ubiquitous operation of matrix multiplication as a model for a class of recursive algorithms. In comparison to the conventional multiplication algorithm, Strassen's algorithm requires more storage space and exhibits poorer data locality. Although recent years have seen better representation and better implementations of the algorithm, the characterization of the optimization in implementation issues and hence the automatic optimization strategies are lacking. We present our schemes for optimizing data locality and reducing storage space in an increased scope of computation sequences with arithmetic and numerical constraints. Moreover, our characterization of the optimization schemes are based on th..