Electromagnetics Computations Using the MPI Parallel Implementation of the Steepest Descent Fast Multipole Method (SDFMM).

Abstract

The computational solution of large-scale linear systems of equations necessitates the use of fast algorithms, but is also greatly enhanced by employing parallelization tachniques. The objective of this work is to demonstrate the speedup achieved by the MPI-based parallel implementation of the Steepest Descent Fast Multipole Method (SDFMM). Although this algorithm has already been optimized to take advantage of the structure of the physics of scattering problems, there is still the opportunity to speed up the calculation by dividing component tasks into pieces and using multiple processors to solve them in parallel. The SDFMM has three bottlenecks ordered as (1) filling the sparse impedance matrix associated with the near field moment method interactions, (2) the matrix vector multiplications associated with this sparse matrix (3) the far field interactions associated with the fast multipole method. The parallel implementation task is accomplished basically using a thirty-one node Intel Pentium Beowulf cluster and is also validated on a 4-processor Alpha workstation. The Beowulf cluster consists of thirty-one nodes of 350MHz Intel Pentium IIs with 256 MB of RAM and one node of a 4x450MHz Intel Pentium II Xeon shared memory processor with 2GB of RAM with all nodes connected to a 100 BaseTX Ethernet network. The Alpha workstation has a maximum of four 667MHz processors. The parallelized computer code is tested for different cases of the anti-personnel landmine detection application. Our numerical results show linear speedup in filling the sparse impedance matrix that tremendously reduced the overall code’s runtime. Using the 32-processors on the Beowulf cluster lead to achieve a 7.2 overall speedup and significant reduction in the runtime is gained using the 4-processors on the Alpha workstation.