Search

In this paper, we analyze the communication pattern and study the scalability of a distributed memory implementation of the multilevel fast multipole algorithm (MLFMA) called ScaleME. ScaleME uses the message passing interface (MPI) for communication between processors. The parallelization of MLFMA uses a novel a hybrid scheme for distributing the workload across the processors. We study the communication and computational behavior and demonstrate the effectiveness of the parallelization scheme using realistic problems.

This paper reviews the recent progress of fast integral equation solvers at the Center for Computational Electromagnetics and Electromagnetics laboratory, University of Illinois at Urbana-Champaign. We will demonstrate the ability to solve a variety of electromagnetic problems for complex structures and low-frequency structures as well as large scale scattering problems with over 10 million unknowns.

At the Center for Computational Electromagnetics at the University of Illinois, we recently solved a very-large-scale electromagnetic scattering problem. We computed the bistatic radar cross-section of a full-size aircraft at 8 GHz, involving the solution of a dense matrix equation with nearly 10.2 million unknowns. We regarded this as the "ultimate test" of a massively parallel implementation of the multilevel fast multipole algorithm (MLFMA), called ScaleME. In this paper, we narrate the technical difficulties faced and the experience gained from a very informal point of view. We describe the various methods developed for surmounting each of the obstacles.

The fast inhomogeneous plane wave algorithm has been developed to accelerate the solution of three-dimensional electromagnetic scattering problems in free space. By expanding the kernel of the Green's function using the Weyl identity and choosing a proper steepest descent path, the diagonalization of the translation matrix is achieved after the interpolation and extrapolation techniques are applied. The proposed algorithm is implemented on top of the scalable multipole engine, a portable implementation of the dynamic multilevel fast multipole algorithm for distributed-memory computers. The computational time per matrix vector multiplication is reduced to O(NlogN) and the memory requirement is reduced to O(N), where N is the number of unknowns in the discretized integral equation. The algorithm is validated by applying it to the solution of the electromagnetic scattering from the perfect electric conducting scatterers. This approach can be easily extended to more general problems with complicated Green's function expressed in terms of the plane wave spectral integrals, such as the ones encountered in the multilayered medium studies.

A higher order multilevel fast multipole algorithm (MLFMA) is presented for solving integral equations of electromagnetic wave scattering by three-dimensional (3-D) conducting objects. This method employs higher order parametric elements to provide accurate modeling of the scatterer's geometry and higher order interpolatory vector basis functions for an accurate representation of the electric current density on the scatterer's surface. This higher order scheme leads to a significant reduction in the mesh density, thus the number of unknowns, without compromising the accuracy of geometry modeling. It is applied to the electric field integral equation (EFIE), the magnetic field integral equation (MFIE), and the combined field integral equation (CFIE), using Galerkin's testing approach. The resultant numerical system of equations is then solved using the MLFMA. Appropriate preconditioning techniques are employed to speedup the MLFMA solution. The proposed method is further implemented on distributed-memory parallel computers to harness the maximum power from presently available machines. Numerical examples are given to demonstrate the accuracy and efficiency of the method as well as the convergence of the higher order scheme.

A new fast evanescent wave algorithm (FEWA) is introduced in the two-dimensional (2-D) case. It expands the Green's function into propagating waves and directional evanescent waves. Applying the evanescent wave correction technique, a procedure similar to the traditional MLFMA can be expedited. No buffer region is necessary anymore, and fewer translators are needed. Numerical examples are given to show the features of this method. © 2001 John Wiley & Sons, Inc. Microwave Opt Technol Lett 31: 460–465, 2001.

Programmable graphics processor units (GPU), such as the NVIDIAR Geforce 8800 series, offer a raw computing power that is often an order of magnitude larger than even the most modern multicore CPUs, making them a relatively inexpensive platform for high performance computing. In this paper, we report the development of two Krylov subspace solvers, the generalized minimal residual (GMRES) and the quasi-minimal residual (QMR) algorithms, on the GPU using the NVIDIA CUDAR programming model. The algorithms have been implemented as a stand-alone library. We report a speed-up of up to 13 times, on a single GPU, in our preliminary experiments with the classic problem of computing the capacitance of conductors using an integral equation method.

In this paper, we summarize the results of our efforts in developing a scalable distributed memory fast electromagnetic integral equation solver. The massively parallel scattering code, called LSSP, is based on a Galerkin discretization of the combined field integral equation (CFIE) using the RWG basis functions. The resulting matrix equation is then solved using a parallel GMRES solver. It uses the distributed memory parallel MLFMA library called ScaleME for evaluating matrix-vector products and Message Passing Interface (MPI) for inter-processor communication. Furthermore. once the solution is obtained, the bistatic RCS is computed using a parallelized, MLFMA based far field evaluation algorithm. The objective of this paper is to present some recent results demonstrating the scalability of the code for solving realistic problems.

In this paper, we report the development and performance of a parallel combined field integral equation solver, which uses ScaleME as its accelerator. Using this new code, we have been able to solve problems of a much bigger size than that was possible with previously available ones. Indeed, we have been able to solve a 3.1 million unknown problem using 8 nodes of an SGI Origin 2000 super computer. We have also been able to solve a 600,000 (at 1.8G Hz) unknowns problem on an Orion cluster of 16 personal computers running Linux. We formulate the CFIE in a form suitable for the parallel library we have developed. We then report the numerical results on accuracy, a comparison of its performance with the best known sequential code in a single processor systems and results on scaling.

In this paper, we have presented the major features and some preliminary results from the parallel fast multipole library, ScaleME (scalable multipole engine). We have briefly outlined the major features of the library and its applications.

In this paper, we present a higher-order multilevel fast multipole algorithm (MLFMA) for solving integral equations of electromagnetic wave scattering by three-dimensional conducting objects. We first employ higher-order parametric elements to provide an accurate modeling of the scatterer's geometry and then higher-order interpolatory vector basis functions for an accurate representation of the electric current density on the scatterer's surface. The resultant numerical system of equations is then solved using the MLFMA with a reduced computational complexity. Appropriate preconditioning techniques are employed to speedup the MLFMA solution.