Dense matrix operations on a torus and a boolean cube
S. Lennart Johnsson · AFIPS conference proceedings · 1985
Algorithms for matrix multiplication and for Gauss-Jordan and Gaussian elimination on dense matrices on a torus and a boolean cube are presented and analyzed with respect to communication and arithmetic complexity. The number of elements of the matrices is assumed to be larger than the number of nodes in the processing system. The algorithms for matrix multiplication, triangulation, and forward elimination have 100% processor utilization, except for a latency period proportional to the diameter of the system. The constant of proportionality is small. Distributed one-to-all routing algorithms that guarantee completeness and uniqueness, and terminate after k steps for a k-cube are also given.