Reduced-Rank Approximations to the Far-Field Transform in the Gridded Fast Multipole Method

The fast multipole method (FMM) has been shown to have a reduced computational dependence on the size of finest-level groups of elements when the elements are positioned on a regular grid and FFT convolution is used to represent neighboring interactions. However, transformations between plane-wave expansions used for FMM interactions and pressure distributions used for neighboring interactions remain significant contributors to the cost of FMM computations when finest-level groups are large. The transformation operators, which are forward and inverse Fourier transforms with the wave space confined to the unit sphere, are smooth and well approximated using reduced-rank decompositions that further reduce the computational dependence of the FMM on finest-level group size. The adaptive cross approximation (ACA) is selected to represent the forward and adjoint far-field transformation operators required by the FMM. However, the actual error of the ACA is found to be greater than that predicted using traditional estimates, and the ACA generally performs worse than the approximation resulting from a truncated singular-value decomposition (SVD). To overcome these issues while avoiding the cost of a full-scale SVD, the ACA is employed with more stringent accuracy demands and recompressed using a reduced, truncated SVD. The results show a greatly reduced approximation error that performs comparably to the full-scale truncated SVD without degrading the asymptotic computational efficiency associated with ACA matrix assembly.     

Fast evaluation of Helmholtz potential on graphics processing units (GPUs)

This paper presents a parallel algorithm implemented on graphics processing units (GPUs) for rapidly evaluating spatial convolutions between the Helmholtz potential and a large-scale source distribution. The algorithm implements a non-uniform grid interpolation method (NGIM), which uses amplitude and phase compensation and spatial interpolation from a sparse grid to compute the field outside a source domain. NGIM reduces the computational time cost of the direct field evaluation at N observers due to N co-located sources from O(N²) to O(N) in the static and low-frequency regimes, to O(N log N) in the high-frequency regime, and between these costs in the mixed-frequency regime. Memory requirements scale as O(N) in all frequency regimes. Several important differences between CPU and GPU implementations of the NGIM are required to result in optimal performance on respective platforms. In particular, in the CPU implementations all operations, where possible, are pre-computed and stored in memory in a preprocessing stage. This reduces the computational time but significantly increases the memory consumption. In the GPU implementations, where handling memory often is a critical bottle neck, several special memory handling techniques are used to accelerate the computations. A significant latency of the GPU global memory access is hidden by implementing coalesced reading, which requires arranging many array elements in contiguous parts of memory. Contrary to the CPU version, most of the steps in the GPU implementations are executed on-fly and only necessary arrays are kept in memory. This results in significantly reduced memory consumption, increased problem size N that can be handled, and reduced computational time on GPUs. The obtained GPU–CPU speed-up ratios are from 150 to 400 depending on the required accuracy and problem size. The presented method and its CPU and GPU implementations can find important applications in various fields of physics and engineering.     

A direct O(N log N) finite difference method for fractional diffusion equations

Fractional diffusion equations model phenomena exhibiting anomalous diffusion that can not be modeled accurately by the second-order diffusion equations. Because of the nonlocal property of fractional differential operators, the numerical methods have full coefficient matrices which require storage of O(N²) and computational cost of O(N³) where N is the number of grid points.     

A New Version of the Fast Multipole Method for Screened Coulomb Interactions in Three Dimensions

We present a new version of the fast multipole method (FMM) for screened Coulomb interactions in three dimensions. Existing schemes can compute such interactions in O(N) time, where N denotes the number of particles. The constant implicit in the O(N) notation, however, is dominated by the expense of translating far-field spherical harmonic expansions to local ones. For each box in the FMM data structure, this requires 189p⁴ operations per box, where p is the order of the expansions used. The new formulation relies on an expansion in evanescent plane waves, with which the amount of work can be reduced to 40p²+6p³ operations per box.     

A fast directional algorithm for high-frequency electromagnetic scattering

This paper is concerned with the fast solution of high-frequency electromagnetic scattering problems using the boundary integral formulation. We extend the O(N log N) directional multilevel algorithm previously proposed for the acoustic scattering case to the vector electromagnetic case. We also detail how to incorporate the curl operator of the magnetic field integral equation into the algorithm. When combined with a standard iterative method, this results in an almost linear complexity solver for the combined field integral equations. In addition, the butterfly algorithm is utilized to compute the far field pattern and radar cross section with O(N log N) complexity.     

Simple recursive implementation of fast multipole method

In this paper we present an implementation of the well known “fast multipole” method (FMM) for the efficient calculation of dipole fields. The main advantage of the present implementation is simplicity—we believe that a major reason for the lack of use of FMMs is their complexity. One of the simplifications is the use of polynomials in the Cartesian coordinates rather than spherical harmonics. We have implemented it in the context of an arbitrary hierarchical system of cells—no periodic mesh is required, as it is for FFT (fast Fourier transform) methods. The implementation is in terms of recursive functions. Results are given for application to micromagnetic simulation. Complete source code is provided for an open-source implementation of this method, as well as an installer for the resulting program.     

Fast multipole accelerated boundary element method for the Helmholtz equation in acoustic scattering problems

We apply the fast multipole method (FMM) accelerated boundary element method (BEM) for the three-dimensional (3D) Helmholtz equation, and as a result, large-scale acoustic scattering problems involving 400000 elements are solved efficiently. This is an extension of the fast multipole BEM for two-dimensional (2D) acoustic problems developed by authors recently. Some new improvements are obtained. In this new technique, the improved Burton-Miller formulation is employed to over-come non-uniqueness difficultie...     

Fast and accurate point-based method for time-harmonic maxwell problems involving thin layer materials

We present a high-order hybrid boundary-finite elements method well-suited for solving time-harmonic electromagnetic scattering problems. Actually, this method is specially devoted to perfect electric conductors coated with a thin layer material. On such class of problems this method is shown to be fast and accurate. The fast feature is due to the joint use of finite elements of anisotropic order fitting the layer thickness, and of a point-based boundary element method on the skin. The accuracy is ensured, first by a discretization scheme satisfying the H_curl–H_div conformity required by the integro-differential equation and, secondly, by an adaptive technique of integration based on the detection of some local potential trouble on the geometry such as sharp edges or high dilatation of the elements. This algorithm does not need further information from the user and does not deteriorate the computation time. Numerical examples confirm the efficiency of this approach.     

A Fourier-series-based kernel-independent fast multipole method

We present in this paper a new kernel-independent fast multipole method (FMM), named as FKI-FMM, for pairwise particle interactions with translation-invariant kernel functions. FKI-FMM creates, using numerical techniques, sufficiently accurate and compressive representations of a given kernel function over multi-scale interaction regions in the form of a truncated Fourier series. It provides also economic operators for the multipole-to-multipole, multipole-to-local, and local-to-local translations that are typical and essential in the FMM algorithms. The multipole-to-local translation operator, in particular, is readily diagonal and does not dominate in arithmetic operations. FKI-FMM provides an alternative and competitive option, among other kernel-independent FMM algorithms, for an efficient application of the FMM, especially for applications where the kernel function consists of multi-physics and multi-scale components as those arising in recent studies of biological systems. We present the complexity analysis and demonstrate with experimental results the FKI-FMM performance in accuracy and efficiency.     

A new single-image fog removal algorithm based on physical model

Based on the physical model of atmospheric scattering and the optical reflectance imaging model, three major factors which affect the effect of fog removal are discussed in detail, dark channel phenomenon is explained via the optical model, and an approach for solving the parameter in the atmospheric scattering model is rigorously derived from a new perspective. Using gray-scale opening operation and fast joint bilateral filtering techniques, the proposed algorithm can effectively obtain the global atmospheric light and greatly improve the speed and accuracy of atmospheric scattering function solving. Finally, the scene albedo is recovered by inverting this model. Compared with existing algorithms, complexity of the proposed method is only a linear function of the number of input image pixels and this allows a very fast implementation. The simulation results show that the processing time of images with a resolution of 576*768 is only 1.7 s; Results on a variety of outdoor foggy images demonstrate that the proposed method achieves good restoration for contrast and color fidelity, resulting in a great improvement in image visibility.     

复杂地表条件下快速推进法地震波走时计算

为获得计算复杂地表条件下地震波走时的方法,对常规快速推进法(Fast marching method,简写为FMM)做了两点改进:①引入不等距差分格式,用于地表和界面处的局部走时计算;②增加新的网格节点类型,用于实现不规则边界条件下的窄带技术.通过对算法的计算精度、效率及实例的分析可得,算法计算精度高,其中反射波走时计算的精度高于初至波;不会因为处理不规则边界而引入过多额外的计算量;能灵活稳定地处理各种强起伏复杂地形、近地表及地下复杂介质等问题.计算结果满足复杂地表条件下地震波的传播规律.     

Adaptation and performance of the Cartesian coordinates fast multipole method for nanomagnetic simulations

An implementation of the fast multiple method (FMM) is performed for magnetic systems with long-ranged dipolar interactions. Expansion in spherical harmonics of the original FMM is replaced by expansion of polynomials in Cartesian coordinates, which is considerably simpler. Under open boundary conditions, an expression for multipole moments of point dipoles in a cell is derived. These make the program appropriate for nanomagnetic simulations, including magnetic nanoparticles and ferrofluids. The performance is optimized in terms of cell size and parameter set (expansion order and opening angle) and the trade off between computing time and accuracy is quantitatively studied. A rule of thumb is proposed to decide the appropriate average number of dipoles in the smallest cells, and an optimal choice of parameter set is suggested. Finally, the superiority of Cartesian coordinate FMM is demonstrated by comparison to spherical harmonics FMM and FFT.     

Three particles in a finite volume

Within the non-relativistic potential scattering theory, we derive a generalized version of the Lüscher formula, which includes three-particle inelastic channels. Faddeev equations in a finite volume are discussed in detail. It is proved that, even in the presence of the three-particle intermediate states, the discrete spectrum in a finite box is determined by the infinite-volume elements of the scattering S -matrix up to corrections, exponentially suppressed at large volumes.     

A multilevel Cartesian non-uniform grid time domain algorithm

A multilevel Cartesian non-uniform grid time domain algorithm (CNGTDA) is introduced to rapidly compute transient wave fields radiated by time dependent three-dimensional source constellations. CNGTDA leverages the observation that transient wave fields generated by temporally bandlimited and spatially confined source constellations can be recovered via interpolation from appropriately delay- and amplitude-compensated field samples. This property is used in conjunction with a multilevel scheme, in which the computational domain is hierarchically decomposed into subdomains with sparse non-uniform grids used to obtain the fields. For both surface and volumetric source distributions, the computational cost of CNGTDA to compute the transient field at N_s observation locations from N_s collocated sources for N_t discrete time instances scales as O(N_tN_slogN_s) and O(N_tN_slog²N_s) in the low- and high-frequency regimes, respectively. Coupled with marching-on-in-time (MOT) time domain integral equations, CNGTDA can facilitate efficient analysis of large scale time domain electromagnetic and acoustic problems.     

多层快速多极子算法中的两步插值技术

多层快速多极子算法(MLFMA)在快速多极子算法(FMM)的基础上按多层聚集、层间转移和多层扩散的思路以达到优化矩阵向量积的运算的目的,其中多层聚集和多层扩散过程,随着层数递增,角谱积分采样点数逐层递增,为了快速计算角谱积分,需要采用插值技术和反插值技术以提高计算效率.应用两步插值技术替代传统的单步插值技术,大幅提高了多层快速多极子层间插值反插值操作的计算效率,对于应用普通个人计算机求解特大电大尺寸问题,具有重要意义.     

A kernel-free boundary integral method for elliptic boundary value problems

This paper presents a class of kernel-free boundary integral (KFBI) methods for general elliptic boundary value problems (BVPs). The boundary integral equations reformulated from the BVPs are solved iteratively with the GMRES method. During the iteration, the boundary and volume integrals involving Green’s functions are approximated by structured grid-based numerical solutions, which avoids the need to know the analytical expressions of Green’s functions. The KFBI method assumes that the larger regular domain, which embeds the original complex domain, can be easily partitioned into a hierarchy of structured grids so that fast elliptic solvers such as the fast Fourier transform (FFT) based Poisson/Helmholtz solvers or those based on geometric multigrid iterations are applicable. The structured grid-based solutions are obtained with standard finite difference method (FDM) or finite element method (FEM), where the right hand side of the resulting linear system is appropriately modified at irregular grid nodes to recover the formal accuracy of the underlying numerical scheme. Numerical results demonstrating the efficiency and accuracy of the KFBI methods are presented. It is observed that the number of GMRES iterations used by the method for solving isotropic and moderately anisotropic BVPs is independent of the sizes of the grids that are employed to approximate the boundary and volume integrals. With the standard second-order FEMs and FDMs, the KFBI method shows a second-order convergence rate in accuracy for all of the tested Dirichlet/Neumann BVPs when the anisotropy of the diffusion tensor is not too strong.     

High frequency fast magnetoacoustic modes in the plasma core

Fast magnetoacoustic modes (FMM) [known also as compressional Alfvén eigenmodes (CAE) and magnetosonic modes] with frequencies exceeding or equal the ion gyrofrequency are considered. It is shown that edge-localized FMM, which presumably are responsible for the superthermal ion cyclotron emission (ICE) observed in many experiments on tokamaks and stellarators, represent a particular case of these modes. In general, FMMs with frequencies above/about the ion gyrofrequency have different radial locations and structures. They can extend over a large part of the plasma cross section and even can have maximum amplitudes at the magnetic axis. Modes with the same frequency and the same poloidal mode number are multiple, having different radial structures. These results are obtained in the approximation of cylindrical plasma with one-ion species.     

Evaluation of numerical scattering in finite volume method for solving radiative transfer equation by a central laser incidence model

The numerical scattering caused by spatial discretization in finite volume method is discussed. Based on an analysis of the generation process of numerical scattering, a physical model of central laser incidence to a two-dimensional rectangle containing semitransparent medium is established to validate the numerical scattering, with Monte Carlo method as benchmark, in which numerical scattering does not exist. Numerical scattering will be affected by spatial grid number, spatial differential schemes and spectral absorption coefficient. With the spatial grid number increasing, numerical scattering will be decreased. The accuracy of the diamond scheme is the highest, and the exponential scheme is a bit lower, the lowest accuracy of the three schemes is the step scheme. The tendency of numerical scattering is reverse, i.e., the step scheme produces minimum numerical scattering, and exponential scheme produces more, while the diamond scheme produces maximum among three methods. When the bias of absorption efficient is high, the numerical scattering cannot be eliminated only by increasing the grid number. If we set the direction of laser incidence as central axis, it can be seen that numerical scattering distributed symmetry along the axis, which can be called as symmetrical cross-scattering. All of the three schemes show symmetrical cross-scattering.