The black-box fast multipole method

A new O(N)$O(N)$ fast multipole formulation is proposed for non-oscillatory kernels. This algorithm is applicable to kernels K(x,y)$K(x\text{,}y)$ which are only known numerically, that is their numerical value can be obtained for any (x,y)$(x\text{,}y)$. This is quite different from many fast multipole methods which depend on analytical expansions of the far-field behavior of K  , for |x-y|$|x-y|$ large. Other “black-box” or “kernel-independent” fast multipole methods have been devised. Our approach has the advantage of requiring a small pre-computation time even for very large systems, and uses the minimal number of coefficients to represent the far-field, for a given L²$L^2$ tolerance error in the approximation. This technique can be very useful for problems where the kernel is known analytically but is quite complicated, or for kernels which are defined purely numerically.     

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.     

Error control in the perfectly matched layer based multilevel fast multipole algorithm

The development of efficient algorithms to analyze complex electromagnetic structures is of topical interest. Application of these algorithms in commercial solvers requires rigorous error controllability. In this paper we focus on the perfectly matched layer based multilevel fast multipole algorithm (PML-MLFMA), a dedicated technique constructed to efficiently analyze large planar structures. More specifically the crux of the algorithm, viz. the pertinent layered medium Green functions, is under investigation. Therefore, particular attention is paid to the plane wave decomposition for 2-D homogeneous space Green functions in very lossy media, as needed in the PML-MLFMA. The result of the investigations is twofold. First, upper bounds expressing the required number of samples in the plane wave decomposition as a function of a preset accuracy are rigorously derived. These formulas can be used in 2-D homogeneous (lossy) media MLFMAs. Second, a more heuristic approach to control the error of the PML-MLFMA’s Green functions is presented. The theory is verified by means of several numerical experiments.     

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.     

Implementing the fast multipole method in three dimensions

The Rokhlin-Greengard fast multipole algorithm for evaluating Coulomb and multipole potentials has been implemented and analyzed in three dimensions. The implementation is presented for bounded charged systems and systems with periodic boundary conditions. The results include timings and error characterizations.     

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...     

The fast multipole method and Fourier convolution for the solution of acoustic scattering on regular volumetric grids

The fast multipole method (FMM) is applied to the solution of large-scale, three-dimensional acoustic scattering problems involving inhomogeneous objects defined on a regular grid. The grid arrangement is especially well suited to applications in which the scattering geometry is not known a priori and is reconstructed on a regular grid using iterative inverse scattering algorithms or other imaging techniques. The regular structure of unknown scattering elements facilitates a dramatic reduction in the amount of storage and computation required for the FMM, both of which scale linearly with the number of scattering elements. In particular, the use of fast Fourier transforms to compute Green’s function convolutions required for neighboring interactions lowers the often-significant cost of finest-level FMM computations and helps mitigate the dependence of FMM cost on finest-level box size. Numerical results demonstrate the efficiency of the composite method as the number of scattering elements in each finest-level box is increased.     

A fast and stable method for rotating spherical harmonic expansions

In this paper, we present a simple and efficient method for rotating a spherical harmonic expansion. This is a well-studied problem, arising in classical scattering theory, quantum mechanics and numerical analysis, usually addressed through the explicit construction of the Wigner rotation matrices. We show that rotation can be carried out easily and stably through “pseudospectral” projection, without ever constructing the matrix entries themselves. Existing fast algorithms, based on recurrence relations, are subject to a variety of instabilities, limiting the effectiveness of the approach for expansions of high degree.     

Electron density distribution in Si and Ge using multipole, maximum entropy method and pair distribution function analysis

The local, average and electronic structure of the semiconducting materials Si and Ge has been studied using multipole, maximum entropy method (MEM) and pair distribution function (PDF) analyses, using X-ray powder data. The covalent nature of bonding and the interaction between the atoms are clearly revealed by the two-dimensional MEM maps plotted on (100) and (110) planes and one-dimensional density along [100], [110] and [111] directions. The mid-bond electron densities between the atoms are 0.554 e/?³ and 0.187 e/?³ for Si and Ge respectively. In this work, the local structural information has also been obtained by analyzing the atomic pair distribution function. An attempt has been made in the present work to utilize the X-ray powder data sets to refine the structure and electron density distribution using the currently available versatile methods, MEM, multipole analysis and determination of pair distribution function for these two systems.      

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.     

Extending the Fast Multipole Method for Charges inside a Dielectric Sphere in an Ionic Solvent: High Order Image Approximations for Reaction Fields

As a sequel to our previous paper on extending the Fast Multipole Method (FMM) for charges inside a dielectric sphere [J. Comput. Phys. 223 (2007) 846–864], this paper further extends the FMM to the electrostatic calculation for charges inside a dielectric sphere immersed in an ionic solvent, a scenery with more relevance in biological applications. The key findings include two fourth-order multiple discrete image approximations in terms of u = λa to the reaction field induced by the ionic solvent, provided that u = λa < 1 where λ is the inverse Debye screening length of the ionic solvent and a is the radius of the dielectric sphere. A 10⁻⁴ relative accuracy in the reaction field of a source charge within the sphere can be achieved with only 3–4 point image charges. Together with the image charges, the FMM can be used to speed up the calculation of electrostatic interactions of charges in a dielectric sphere immersed in an ionic solvent.     

An analysis of the wide area differential method of geostationary orbit satellites

This work aims to obtain a wide area differential method for geostationary orbit (GEO) constellation. A comparison between the dilution of precision (DOP) of four-dimensional (4D) calculation including satellite clock errors and ephemeris errors and that of three-dimensional (3D) calculation only including ephemeris errors with the inverse positioning theory of GPS shows the conclusion that all the 3D PDOPs are greatly reduced. Based on this, a basic idea of correcting satellite clock errors and ephemeris errors apart is put forward, and moreover, a specific method of separation is proposed. Satellite clock errors are separated in a master station with time synchronization, and all the remaining pseudo-range errors after the satellite clock errors have been deducted are used to work out ephemeris corrections of all GEO satellites. By a comparative analysis of user positioning accuracy before and after differential, the wide area differential method is verified to be quite valid for GEO constellation. Supported by the National Natural Science Foundation of China (Grant No. 10778715), the National Key Basic Research Development Program of China (Grant No. 2007CB815502), and the Scientific Research Fund of Hunan Provincial Education Department (Grant No. 08B039)     

Differential algebraic method for time of flight property of electrostatic electron lenses

Differential algebraic method is a powerful technique in computer numerical analysis. It presents a straightforward method for computing arbitrary order derivatives of functions with extreme high accuracy limited only by the truncation error of the computer. When applied to nonlinear dynamical systems, the arbitrary high-order transfer properties of the systems can be computed directly with high precision. In this article, the time of flight (TOF) property of electrostatic electron lens systems is studied by differential algebraic method and their arbitrary order TOF transfer properties can be numerically calculated. As an example, Schiske's model electrostatic lens has been studied by the efficient differential algebraic TOF method.     

利用重心法求光斑信号位置的误差分析

在许多光电检测系统（如ＬＡＭＯＳＴ光纤定位标定系统）中,要求准确得到光斑信号的位置。光斑信号的位置可以由重心法求出。重心法在使用中,不可避免地要受到许多因素的干扰,给测量结果带来误差,如杂散光、气流、温度、暗电流、ＡＤ 采样的位数等等。通过实验对重心法运用于这类系统将产生的误差作了较为详尽的分析。实验表明：重心法具有精度高,计算简单,对硬件要求低等优点,完全适用于ＬＡＭＯＳＴ光纤定位标定系统。     

Bidirectional beam propagation method based on the method of lines for the analysis of photonic band gap structures

The bidirectional beam propagation method based on the method of lines is proposed as an innovative and efficient algorithm to investigate the optical properties of photonic band gap (PBG) structures. A few examples illustrate the application of this technique to the modeling of passive, lossy and active one-dimensional and index confined PBG structures. The algorithm results are validated by comparison with those obtained via the transfer matrix method, the mode-matching method and the finite difference time domain method. With respect to these methods, the present algorithm exhibits accurate results with reduced computer resources.     

An opto-electrical method for measuring the gap of LCD glass plates

We focus on the experimented system development for the measurement of the gap of LCD glass plates. The measurement system includes a laser light source, lens module, image capturing system and the algorithm for calculation of the position of light spots. We emphasize the structure of laser triangulation in an optical system. The software is focused on the algorithm for calculating the position of light point, including centroid calculation method (CCM) and Fourier phase shift (FPS).

Furthermore, to verify the feasibility of the algorithm, we use computer software to simulate experiments. We also discuss the contribution of the noise to the accuracy for the CCM and FPS. To complete the development of the opto-electrical measurement system and to verify the accuracy for the hardware architecture, we use a novel mechanism of multi-track and concentricity, laser light source, lens module, and image capturing system.     

A Brinkman penalization method for compressible flows in complex geometries

To simulate flows around solid obstacles of complex geometries, various immersed boundary methods had been developed. Their main advantage is the efficient implementation for stationary or moving solid boundaries of arbitrary complexity on fixed non-body conformal Cartesian grids. The Brinkman penalization method was proposed for incompressible viscous flows by penalizing the momentum equations. Its main idea is to model solid obstacles as porous media with porosity, , and viscous permeability approaching zero. It has the pronounced advantages of mathematical proof of error bound, strong convergence, and ease of numerical implementation with the volume penalization technique. In this paper, it is extended to compressible flows. The straightforward extension of penalizing momentum and energy equations using Brinkman penalization with respective normalized viscous, η, and thermal, η_T, permeabilities produces unsatisfactory results, mostly due to nonphysical wave transmissions into obstacles, resulting in considerable energy and mass losses in reflected waves. The objective of this paper is to extend the Brinkman penalization technique to compressible flows based on a physically sound mathematical model for compressible flows through porous media. In addition to penalizing momentum and energy equations, the continuity equation for porous media is considered inside obstacles. In this model, the penalized porous region acts as a high impedance medium, resulting in negligible wave transmissions. The asymptotic analysis reveals that the proposed Brinkman penalization technique results in the amplitude and phase errors of order O((η)^1/2) and O((η/η_T)^1/43/4), when the boundary layer within the porous media is respectively resolved or unresolved. The proposed method is tested using 1- and 2-D benchmark problems. The results of direct numerical simulation are in excellent agreement with the analytical solutions. The numerical simulations verify the accuracy and convergence rates.     

Variational method for determining the extraterrestrial constant for a solar ultraviolet spectrometer/ozonometer

A theoretical rationale is presented for a variational method for determining the extraterrestrial constant of a solar ultraviolet spectrophotometer for measuring total column ozone in the atmosphere. We have established the connection between this method and the familiar Langley method for calibration of extraterrestrial constants of solar spectrophotometers. Translated from Zhurnal Prikladnoi Spektroskopii, Vol. 76, No. 2, pp. 291–297, March–April, 2009.