
Research > Parallelization of MLFMA
Parallelization of MLFMA
Fast and accurate solutions of largescale scattering problems involving threedimensional closed conductors
with arbitrary shapes using the multilevel fast multipole algorithm (MLFMA). With an efficient parallelization of MLFMA,
scattering problems that are discretized with tens of millions of unknowns are easily solved on a cluster of computers. We
extensively investigate the parallelization of MLFMA, identify the bottlenecks, and provide remedial procedures to improve the
efficiency of the implementations. The accuracy of the solutions is demonstrated on a scattering problem involving a sphere of
radius 110 wavelenghts discretized with 41,883,638 unknowns, the largest integralequation problem solved to date. In addition to canonical problems, we also present the solution of reallife problems involving complicated targets with large dimensions.
Tree size and the number of nearfield interactions for the solutions of the sphere problems using topdown strategy to construct the multilevel tree.
Major parts of MLFMA and their computational requirements.
Communications performed in each MVM to match the nearfield and farfield partitioning schemes.
Alltoall communications performed at LoD to change the farfield partitioning scheme from the distributed levels to the shared levels.
Interpolations in the shared levels involving onetoone communications.
Processor pairing for the translations in the distributed levels.
Anterpolations (transpose interpolations) in the shared levels involving onetoone communications.
Communications required in the matrixvector multiplications by parallel MLFMA.
Parallelization efficiency for the solution of a scattering problem involving a sphere of radius 24 wavelenghts discretized with 2,111,952 unknowns.
Processing time and parallelization efficiency for various categorized parts of the MVMs for the solution of a scattering problem involving a sphere of radius 24 wavelenghts discretized with 2,111,952 unknowns.
Solutions of large sphere problems with MLFMA parallelized into 16 processes.
Time diagrams for the solution of a scattering problem involving a sphere of radius 80 wavelenghts discretized with 23,405,664 unknowns. (a) Overall time includes the input and clustering parts , calculation of the translation matrices, calculation of the nearfield interactions, calculation of the radiation
and receiving patterns, and the iterative solution. (b) Matrixvector multiplications include the nearfield stage, aggregation in the distributed levels, alltoall communications in the level of distribution (LoD), aggregation in the shared levels, translations without communications, translations with communications, disaggregation in the shared levels, and disaggregation in the
distributed levels followed by the receiving operation. In the diagrams, white areas correspond to waits before the operations that require synchronization.
For more information:
 Please see the full article published in the IEEE Transactions on Antennas and Propagation in 2008.
How to cite this paper:
 Ö. Ergül and L. Gürel, "Efficient parallelization of the multilevel fast multipole algorithm for the solution of largescale scattering problems," IEEE Trans. Antennas Propagat., vol. 56, no. 8, pp. 23352345, Aug. 2008.
