The Parallellization And Implementation Of Mlfma For The Accurate Solution Of Electromagnetic Scattering By Large Complex Objects

The fast analysis and calculation of electrically large complex electromagnetic scattering problems is widely used in the radar system design and radar target identification, the radar stealth and anti-stealth technology, and the modern electric systems'Electro Magnetic Compatibility (EMC) analysis. It is efficient and accurate for the electromagnetic simulation on the computer. Particularly, the successful development of the Multilevel Fast Multipole Algorithm (MLFMA) on electromagnetic fields immensely increases the ability of the electromagnetic simulation. Meanwhile, accurate solutions of the large scale electromagnetic scattering problems require discretisations with millions of unknowns, which cannot be solved easily by the sequential implementations of MLFMA running on a single processor. With the development of the computer cluster technology and the parallel computation technology, the parallelization of MLFMA for solving the electromagnetic scattering is an effective way to enlarge the simulation scale and improve the simulation efficiency.For electromagnetic scattering problems with the complicated boundary, the key of parallelizing MLFMA is distributing the computer resources equally, reducing data communication among processors, optimizing the space complexity and the computing complexity in every link of the software design, which will influence the parallel efficiency and the computing ability of the algorithm. In order to solve the above problems, the computing domain in MLFMA is divided into the data domain and the angular spectrum domain. Toward the different characteristics of two domains, a high-performance parallel MLFMA is proposed and implemented and the numerical performance of which is analyzed. The main innovation points of the thesis are as follows:The load balancing algorithm of the distributed tree is proposed. In the data domain, the load balancing of the parallel MLFMA is mainly embodied by the division of the distributed tree. For the traditional method, the boxes are usually partitioned equally at the finest level of the distributed tree among processors, and then the distributed tree is constructed with bottom-up. To the symmetrical object, this tree has a good load balancing, whereas to the complex objects in the real life which have an unsymmetrical shape, this method made the load balancing very badly. Therefore, a new division algorithm of the distributed tree is applied to improve the load balancing, which partitions some layers (non-final layer) equally to construct the distributed tree.The angular spectrum domain decomposition algorithm with the block method of the interpolation and anterpolation operation is proposed to reduce the data communication among processors. Generally, the load balancing at the angular spectrum domain is better than that at the data domain, but the communication of the interpolation and anterpolation operation between shared levels cannot be avoided. The key of the angular spectrum domain decomposition is to reduce the communications and increase the number of the shared levels. Although the traditional strip scheme can make the communications between the right and left processors, it can also restrict the workable processors. So the block method of the interpolation and anterpolation operation is adopted to reduce communication burden and enlarge the parallel scales, which makes the communications available among the adjacent processors.In the preprocess phase of the parallel-MLFMA, the correlative data structure which includes the interpolation (or anterpolation) matrix, the translation matrix, the near-neighbor impedance matrix and so on are considered for their computing complexities and storage requirements. The interpolation (or anterpolation) matrix is first computed in the sequential algorithm, and then distributed in the parallel algorithm. The translation matrix is stored using some compressed scheme during the computation process and uncompressed during the distribution process. The distribution of the near-neighbor impedance matrix is different from that of the far field, which is computed with the local priciple of data.The topology structures of communications for the translation operation and the interpolation and anterpolation operation are also established in order to improve the communication efficiency during its iterative process. During the communications of the translation operation, the outgoing queue and the recipient queue are set up to improve the communication efficiency, which can exchange data for one time among processors. According to the theory of the interpolation and anterpolation operation, this topology structure of communications is created by the Cartesian virtual topology. A clever communication order of columns and rows is designed to realize communications among the adjacent processors.Many experiments have been done on the efficiency, accuracy and capability of the parallel MLFMA with all kinds of complex objects. Experimental results manifest the significant performance improvement of the parallel-MLFMA. This high-performance parallel MLFMA has successfully computered scattering with over ten millions unknowns and has been applied in the practical engineering.