Brief Announcement: Fine-Grained Computation in 3-Space: Matrix Multiplication, Paths, and Mazes

Optimal algorithms are given for matrix multiplication and problems involving graphs and mazes, where calculations are done in 3-dimensional space. Whatever the technology is, a bit requires a minimum volume and communication travels at a bounded speed. Thus multiplying n × n matrices over a ring takes Ω(n2/3) time, and we show that this can be achieved by a 3-d mesh of n2 processors. No previous algorithms fully considered the implications of volume and bounded communication speed. Multiplication of matrices not over a ring requires only Θ(n3/4) time by expanding to a larger mesh. In 2-d (such as the surface of a chip) this approach is useless and Θ(n) systolic algorithms are optimal. For path and maze problems there are approaches useful in 3-d but not 2-d.