Loading...
Please wait, while we are loading the content...
Similar Documents
Architecture-eecient Strassen's Matrix Multiplication: a Case Study of Divide-and-conquer Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Pauca, Paul |
| Copyright Year | 1997 |
| Abstract | Many fast algorithms in arithmetic complexity have hierarchical or recursive structures that make eecient implementations on high performance computers with memory hierarchies non-trivial. In this paper we present our ndings on eecient implementation of Strassen's algorithmm17] 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 the use of algorithmic operators and leads to automatic optimization for a class of recursive algorithms. We present experimental results and comparisons with the corresponding subroutine in BLAS and the recursive version of Strassen's algorithm. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
