The fast multipole method (FMM) for N-body simulations is attracting much attention since it requires minimal communication between computing nodes. We implemented hardware pipelines specialized for the FMM on an FPGA device, the GRAPE-9. An N-body simulation with 1.6×107 particles ran 16 times faster than that on a CPU. Moreover the particle-to-particle stage of the FMM on the GRAPE-9 executed 2.5 times faster than on a GPU in a limited case.

Error analysis of the multilevel fast multipole algorithm is studied for electromagnetic scattering problems. We propose novel error prediction and control methods and verify that the computational error for scattering problems with over one million unknowns can be precisely controlled under desired digits of accuracy. Optimum selection of truncation numbers to minimize computational error also will be discussed.

In this study, we demonstrate an acceleration of flexible generalized minimal residual algorithm (FGMRES) implemented with the method of moments and the fast multipole method (FMM), based on a combined tangential formulation. For the implementation of the FGMRES incorporated with the FMM concept, we propose a new definition of the truncation number for the FMM operator within the inner solver. The proposed truncation number provides an optimal variable preconditioner by controlling the accuracy and computational cost of the inner iteration. Moreover, to further accelerate the convergence, we introduce the concept of a multistage preconditioner. Numerical experiments reveal that our new version of FGMRES, based on the proposed truncation number for the inner solver and the multistage preconditioner, achieves outstanding acceleration of the convergence for large-scale and practical electromagnetic scattering and radiation problems with several levels of geometrical complexity.

The conjugate gradient-fast multipole method (CG-FMM) is one of the powerful methods for analysis of large-scale electromagnetic problems. It is also known that CPU time and computer memory can be reduced by CG-FMM but such computational cost of CG-FMM depends on shape and electrical properties of an analysis model. In this paper, relation between the number of multipoles and number of segments in each group is derived from dimension of segment arrangement in four typical wiregrid models. Based on the relation and numerical results for these typical models, the CPU time per iteration and computer memory are quantitatively discussed. In addition, the number of iteration steps, which is related to condition number of impedance matrix and analysis model, is also considered from a physical point of view.

The electric fields inside and outside a car must be carefully determined when designing a wireless communication system to be employed in the car. This paper introduces an effective simulation method and a precise measurement method of electric field distributions in a cabin of a simplified scale car model. A 1/3 car model is employed for ease of measurement. The scaled frequency of 2859 MHz, 3 times 953 MHz, is employed. The use of a moment method simulator utilizing the multilevel fast multipole method allows calculations to be performed on a personal computer. In order to judge the accuracy of simulation results, convergence of simulation output in accordance with segment size (triangle edge length) changes is ensured. Simulation loads in the case of metallic body only and a metallic body with window glass are also shown. In the measurements, an optical electric field probe is employed so as to minimize the disturbances that would otherwise be caused by metallic feed cable; precise measurement results are obtained. Comparisons of measured and simulated results demonstrate very good agreement which confirms the accuracy of the calculated results. 3-dimensional electric field distributions in the car model are shown and 3-dimensional standing wave shapes are clarified. Moreover, calculated and measured radiation patterns of the car model are shown so the total electric field distributions around a car are clarified.

In order to support driving safety, TPMS (Tire Pressure Monitoring System) has been introduced in U.S.A. and Europe. In Japan, the AIRwatch system has been developed and commercialized. Some studies were made to clarify the electric field environment of this system. However, no detailed calculation of the electric field between the transmitter in the tire and the receiving antenna has been published. This paper clarifies the electric field environment of the Japanese system through electromagnetic simulations by a high performance MoM simulator that utilizes the MLFMM scheme. First of all, electric wave emissions from an antenna mounted in a tire are shown to be larger than that of the same antenna in free space. The tire rubber effects are also investigated. Next, electric field distributions on the windshield holding the receiving antenna are calculated. By comparing calculated electric field levels with those in the free space condition, car body interruptions are clarified. Because car body interruptions are not so severe, it is shown that the free space electric field levels can be used as rough design parameters. Moreover, electric field changes due to tire rotation are also clarified. Calculation accuracy is confirmed by the good agreement with measured data collected from a 1/5 scale car model. To permit estimations to be made in actual situations, the effects of the ground are also investigated. This simulation study introduces a lot of important data useful in TPMS system design.

In this research, a sub-array preconditioner is applied to improve the convergence of conjugate gradient (CG) iterative solver in the fast multipole method and fast Fourier transform (FMM-FFT) implementation on a large-scale finite periodic array antenna with arbitrary geometry elements. The performance of the sub-array preconditioner is compared with the near-group preconditioner in the array antenna analysis. It is found that the near-group preconditioner achieves a little better convergence, while the sub-array preconditioner can be easily constructed and programmed with less CPU-time. The efficiency of the CG-FMM-FFT with high efficient preconditioner has been demonstrated in numerical analysis of a finite periodic array antenna.

The computational error of the multilevel fast multipole algorithm is studied. The error convergence rate, achievable minimum error, and error bound are investigated for various element distributions. We will discuss the boundary between the large and small buffer cases in terms of machine precision. The needed buffer size to reach double precision accuracy will be clarified.

This paper describes an estimation of the computational and memory complexities of Greengard-Rokhlin's Fast Multipole Algorithm (GRFMA). GRFMA takes a quad tree structure and six calculation processes. We consider a perfect a-ary tree structure and the number of floating-point operations for each calculation process. The estimation for both complexities shows that the perfect quad tree is the best and the perfect binary tree is the worst. When we apply GRFMA to the computation of realistic problems, volume scattering are the best case and surface scattering are the worst case. In the worst case, the computational and memory complexities of GRFMA are O(Llog2 L) and O(Llog L), respectively. The computational complexity of GRFMA is higher than that of the multilevel fast multipole algorithm.

We describe elements of a fast integral equation solver for large periodic and partly periodic finite array systems. A key element of the algorithm is utilization (in a rigorous way) of a block-Toeplitz structure of the impedance matrix in conjunction with either conventional Method of Moments (MoM), Fast Multipole Method (FMM), or Fast Fourier Transform (FFT)-based Adaptive Integral Method (AIM) compression techniques. We refer to the resulting algorithms as the (block-)Toeplitz-MoM, (block-)Toeplitz-AIM, or (block-)Toeplitz-FMM algorithms. While the computational complexity of the Toeplitz-AIM and Toeplitz-FMM algorithms is comparable to that of their non-Toeplitz counterparts, they offer a very significant (about two orders of magnitude for problems of the order of five million unknowns) storage reduction. In particular, our comparisons demonstrate, that the Toeplitz-AIM algorithm offers significant advantages in problems of practical interest involving arrays with complex antenna elements. This result follows from the more favorable scaling of the Toeplitz-AIM algorithm for arrays characterized by large number of unknowns in a single array element and applicability of the AIM algorithm to problems requiring strongly sub-wavelength resolution.

The boundary element method (BEM), a representative method of numerical calculation of electromagnetic wave scattering, has been used for solving boundary integral equations. Using BEM, however, we finally have to solve a linear system of L equations expressed by dense coefficient matrix. The floating-point operation is O(L2) due to a matrix-vector product in iterative process. Greengard-Rokhlin's fast multipole algorithm (GRFMA) can reduce the operation to O(L). In this paper, we describe GRFMA and its floating-point operation theoretically. Moreover, we apply the fast Fourier transform to the calculation processes of GRFMA. In numerical examples, we show the experimental results for the computation time, the amount of used memory and the relative error of matrix-vector product expedited by GRFMA. We also discuss the convergence and the relative error of solution obtained by the BEM with GRFMA.