In this paper we report on the development of an efficient and portable implementation of Strassen's matrix multiplication algorithm for matrices of arbitrary size. Our technique for defining the criterion which stops the recursions is more detailed than those generally used, thus allowing enhanced performance for a larger set of input sizes. In addition, we deal with odd matrix dimensions using a method whose usefulness had previously been in question and had not so far been demonstrated. Our memory requirements have also been reduced, in certain cases by 40 to more than 70 percent over other similar implementations. We measure performance of our code on the IBM RS/6000, CRAY YMP C90, and CRAY T3D single processor, and offer comparisons to other codes. Finally, we demonstrate the usefulness of our implementation by using it to perform the matrix multiplications in a large application code.

Abstract Matrix multiplication is a key primitive in block matrix algorithms such as those found in LAPACK. We present results from our study of matrix multiplication algorithms on the Intel Touchstone Delta, a distributed memory message‐passing architecture with a two‐dimensional mesh topology. We analyze and compare three algorithms and obtain an implementation, BiMMeR, that uses communication primitives highly suited to the Delta and exploits the single node assembly‐coded matrix multiplication. Our algorithm is completely general, i.e. able to deal with various data layouts as well as arbitrary mesh aspect ratios and matrix dimensions, and has achieved parallel efficiency of 86 %, with overall peak performance in excess of 8 Gflops on 256 nodes for an 8800 × 8800 matrix. We describe BiMMeR's design and implementation and present performance results that demonstrate scalability and robust behavior over varying mesh topologies.

The universality of iterated multistage interconnection networks on N = Y inputs is examined by representing them as directed 2-graphs on N/2 nodes.The shuj?e-exchange network is generalized, by allowing any invertible linear operator T, over GF(2), to replace the perfect shujle and any nonzero translation v H v + Q to replace the exchange operation.It is shown that a pair (T, a] gives rise to a universal network if and only if the vectors a, Ta, T2CY, . . . .Tn-la are linearly independent, and that the 2-graph for any such pair is isomorphic to the de Brui'n graph.Thus, a pair (T, a) is either useless, because its network is not connected, or as good as the shujj?e-exchange network.This provides a wide range of design alternatives for networks that can pass all N! permutations with 2n-1 identical stages.