Abstract:

The finest level data building of a distributed tree is a foundation of parallel multi-level fast multi-pole algorithm (MLFMA). Whether the finest level data is distributed equally or not will affect load balancing of the whole algorithm and its parallel efficiency. This paper studies building methods of the finest level data for the parallel MLFMA. Instead of parallel bucket sort recommended by some authors, a scheme using parallel regular sampling sort algorithm to construct the finest level data of the distributed tree is presented. Experimental results on some common scattering objects with different numbers of processors show that, in most cases, the improved algorithm can achieve better performance than the original one.

Key words: multi-level fast multi-pole algorithm (MLFMA); distributed tree; parallel regular sampling sort; parallel bucket sort; message passing interface (MPI)