Matrix Transpose on Meshes: Theory and Practice

Abstract

We consider the problem of matrix transpose on mesh-connected processor networks. On the theoretical side, we present the first optimal algorithm for matrix transpose on two-dimensional meshes.  Then we consider issues on implementations, show that the theoretical best bound cannot be achieved and present an alternative approach that really improves the practical performance. Finally, we introduce the concept of orthogonalizations, which are generalization of matrix transposes.  We show how to realize them efficiently and present interesting applications of this new technique.