"Tree-codes" and "Multigrid" methods are both hierarchical, recursive algorithms for solving vector field equations, faster than traditional methods. If the methods are non-adaptive, then both Tree-codes and Multigrid methods require identical parallel communication strategies since they share the same internal structure.
This paper contains a description of Tree-codes followed by an overview of one Tree-code in particular, namely the Greengard-Rokhlin Fast Multipole Method in 2 dimensions. The parallel version of this method is then discussed at length with the presentation of two communication strategies; An "All-to-all" broadcast and a routine which enables neighbouring transputers to swap information in a predetermined sequence.
The computer used is the Meiko Computing Surface, a MIMD parallel computer employing T800 transputers running the CSTools communication harness using a SPMD (Single Program, Multiple Data), domain decomposition paradigm.
The 3D versions of the communication algorithms have also been implemented and are simple extensions of the 2D routines.
Keywords: Fast Multipole Method, Multigrid, message passing.