SIMD algorithms for matrix multiplication on the hypercube

Presents a new algorithm for n×n matrix multiplication on a hypercube of p processors, which outperforms, in terms of time complexity, the best algorithms known in the literature, due to Dekel, Nassimi and Sahni (1981). These authors presented algorithms of O[n^λ/p^(λ-1/2)], with 2⩽λ<3 and 1⩽p⩽n², and O[log(p/n²)+n³/p], for n²⩽p⩽n ³. The MMM₁ algorithm presented in this paper is O[(n²/p^2/3)log p + n^λ/p^λ/3], where 1⩽p⩽n³ . It can be shown that MMM₁ is better for 1⩽p⩽n ³/log³n. The algorithm is derived by using the matricial visualization of the hypercube, suggested by Nassimi and Sahni (1982)