Large-Scale Scattering Problem Using Fast Numerical Algorithms

With the development of computers and fast numerical methods, large-scale scattering problems have attracted many researchers'attentions. The radio wave propagations over one-dimensional (1-D) terrain and urban building profile are important issues in the study of wireless communication, in which characteristics are calculated by using large-scale profiles. 2-D random rough surface scattering is an important problem in active and passive microwave remote sensing. In Monte Carlo simulation, a surface with finite area is generated to calculate its scattering, however, the real surface is infinite, then the generated surface should large enough so that it can converge on the real surface. Matrix equations of these large-scale problems cannot be solved directly unless memory requirement and computational complex become small by using fast numerical algorithms. The common methods include sparse-matrix canonical grid method (SMCG) based on Fast Fourier Transform (FFT), and the multilevel fast multipole method (ML-FMM). Recently the multilevel UV method, based on rank and interpolation technology, has also been used. These methods all divide original impedance matrix into near field (strong field) and far field (weak field). Elements in near field are calculated directly by MoM, and that in far field are calculated by fast numerical algorithms. For the case with large rms height, SMCG and FMM are still effective in calculating far field interactions with small memory requirement, however, memory requirement and computational complex in near field become intensive because of larger near field. The multilevel UV method can effectively apply to the case with large rms instead of with large slope. If surface's slope is large, the UV interpolation needs denser sampling, which results in large memory requirement in far field in spite of still small memory requirement in near field. In this paper two hybrid methods are developed for combining the multilevel UV method with SDFMM, and for combining the multilevel UV method with SMCG method. The UV method, the hybrid UV/SDFMM, and the hybrid UV/SMCG methods are used to accelerate method of moments (MoM) solution, respectively, for the case of terrain propagation, for the case of urban environment, and for the case of 2-D surface scattering with the least memory and computational complex. Simulation results are analyzed in the end. Computations of all cases are performed with a single processor of CPU speed of 2.66 GHz.Specifically, the following procedures are developed:1. The multilevel UV method is applied to a long terrain profile with large height but with small slope. Its original impedance matrix can be compressed drastically. In the multilevel UV method, it is used fast coarse-coarse sampling to search rank of each block, and construct matrix U and V to compress each block based on interpolation technique. The accuracy of the UV method is controllable by varying the threshold, which is corresponding to blocks'ranks. Considering propagation over a region of 14.42 km, maximum height difference of 160 m at 1500 MHz that has 720 896 MoM surface unknowns, the total CPU time include preprocessing are 100 minutes with 92 iterations and 50.9 seconds CPU time per iteration, and with memory 1300 MB. Simulation results show deep fading in vally regions.2. For the case of a long urban building profile with large buildings'heights based on Monte Carlo simulation, the slope on the wall of buildings is infinite. It needs large memory in far field by the UV method alone, and large memory and large computational complex in near field by SDFMM alone. The SMCG method cannot be applied to the case because of the sharp rise in surface height, then the hybrid UV/SDFMM is used to handle near and intermediate field interactions in the multilevel UV method and far field in the SDFMM. The hybrid UV/SDFMM is effective in replacing the intensive computational complex of both the SDFMM in near field and the UV method in far field. Considering a problem over 2.3 km with building heights of 18 m for 90 112 MoM surface unknowns at 900 MHz, the CPU time per iteration is about 35.9 seconds, the total CPU time is about 180~314 minutes with about 281~488 iterations, and with memory 1050 MB. Based on the simulation, fast fading, slow fading, and range dependence with distance are studied. The results are compared with the Rayleigh, Ricean, and lognormal distributions.3. Rough Surface scattering effects are important problems in microwave remote sensing of soil and snow. In remote sensing of soils from 1.5 GHz to 19 GHz, the rms heights can vary from a fraction of a wavelength to 1 ~ 2 wavelengths. In active and passive microwave remote sensing of snow from 5 GHz to 37 GHz, the rms height of the rough interface between snow and ground can vary from a fraction of a wavelength to several wavelengths. To use a single physical model over such a wide frequency range with a single set of physical parameters of rms height and correlation function, we have used Numerical Maxwell Model based on 3-D simulations of Maxwell equations (NMM3D).When the rms height of the rough surface increases, the applicability of the SMCG method depends on the memory storage or the efficiency of computing the near interactions and the accuracy of the Taylor series expansion of the far interactions. Therefore, the SMCG method is only suitable for surfaces up to a moderate roughness. The rank in the UV method will increase with increase of level number in 3-D problems. Then the memory requirement at higher levels becomes larger in spite of considerable compression.In this paper a procedure is developed for combining the multilevel UV method with the SMCG method in the computation of 3-D wave scattering from rough surface. It handles near and intermediate field interactions in the multilevel UV method and far field interactions in the SMCG method. This hybrid UV/SMCG method removes large memory requirement of both the UV method in far field and the SMCG method in near field. The computational complexity for the UV/SMCG method is still O(NlogN). The tradeoff between UV part and SMCG part is controlled by selecting a neighborhood distance rd . By choosing a larger neighborhood distance, only a small number of Taylor's expansion terms is required in the far field SMCG part. This means that a large surface area problem with a large rms height can be solved by the hybrid UV/SMCG method.The UV/SMCG technique is demonstrated in 3-D scattering problem of Gaussian random rough surface with exponential correlation function and with Gaussian correlation function. The frequency dependences of scattering using a single set of physical parameters are illustrated in the simulations. The numerical simulation results are compared with the small perturbation method (SPM) and the Kirchhoff approximation (KA). It is shown that the SPM can only apply to surfaces with small rms height; for exponential correlation function surfaces, the KA is neither applicable at low frequency nor at high frequency. This is contrary to the traditional belief that the KA is applicable at high frequency. For a surface area of 44×44 square wavelengths with rms of 1 wavelength and 123,904 surface unknowns, the UV/SMCG method requires CPU of 52.2 seconds per iteration with total CPU of 46.6 minutes for 22 iterations on a single processor of CPU speed of 2.66 GHz. In this paper the hybrid UV/SDFMM is only applied to 2-D problem of urban environment. In 3-D problem it is not used the hybrid UV/FMM but the hybrid UV/SMCG method because the FMM is not easy to parallelize, however, the SMCG is FFT based and has been parallelized, though parallel implementation has not been implemented in this paper.