A simple multigrid scheme for solving the Poisson equation with arbitrary domain boundaries

We present a new multigrid scheme for solving the Poisson equation with Dirichlet boundary conditions on a Cartesian grid with irregular domain boundaries. This scheme was developed in the context of the Adaptive Mesh Refinement (AMR) schemes based on a graded-octree data structure. The Poisson equation is solved on a level-by-level basis, using a “one-way interface” scheme in which boundary conditions are interpolated from the previous coarser level solution. Such a scheme is particularly well suited for self-gravitating astrophysical flows requiring an adaptive time stepping strategy. By constructing a multigrid hierarchy covering the active cells of each AMR level, we have designed a memory-efficient algorithm that can benefit fully from the multigrid acceleration. We present a simple method for capturing the boundary conditions across the multigrid hierarchy, based on a second-order accurate reconstruction of the boundaries of the multigrid levels. In case of very complex boundaries, small scale features become smaller than the discretization cell size of coarse multigrid levels and convergence problems arise. We propose a simple solution to address these issues. Using our scheme, the convergence rate usually depends on the grid size for complex grids, but good linear convergence is maintained. The proposed method was successfully implemented on distributed memory architectures in the RAMSES code, for which we present and discuss convergence and accuracy properties as well as timing performances.     

Multicloud: Multigrid convergence with a meshless operator

The primary objective of this work is to develop and test a new convergence acceleration technique we call multicloud. Multicloud is well-founded in the mathematical basis of multigrid, but relies on a meshless operator on coarse levels. The meshless operator enables extremely simple and automatic coarsening procedures for arbitrary meshes using arbitrary fine level discretization schemes. The performance of multicloud is compared with established multigrid techniques for structured and unstructured meshes for the Euler equations on two-dimensional test cases. Results indicate comparable convergence rates per unit work for multicloud and multigrid. However, because of its mesh and scheme transparency, multicloud may be applied to a wide array of problems with no modification of fine level schemes as is often required with agglomeration techniques. The implication is that multicloud can be implemented in a completely modular fashion, allowing researchers to develop fine level algorithms independent of the convergence accelerator for complex three-dimensional problems.     

Multigrid method based on the transformation-free HOC scheme on nonuniform grids for 2D convection diffusion problems

In this paper, a multigrid method based on the high order compact (HOC) difference scheme on nonuniform grids, which has been proposed by Kalita et al. [J.C. Kalita, A.K. Dass, D.C. Dalal, A transformation-free HOC scheme for steady convection–diffusion on non-uniform grids, Int. J. Numer. Methods Fluids 44 (2004) 33–53], is proposed to solve the two-dimensional (2D) convection diffusion equation. The HOC scheme is not involved in any grid transformation to map the nonuniform grids to uniform grids, consequently, the multigrid method is brand-new for solving the discrete system arising from the difference equation on nonuniform grids. The corresponding multigrid projection and interpolation operators are constructed by the area ratio. Some boundary layer and local singularity problems are used to demonstrate the superiority of the present method. Numerical results show that the multigrid method with the HOC scheme on nonuniform grids almost gets as equally efficient convergence rate as on uniform grids and the computed solution on nonuniform grids retains fourth order accuracy while on uniform grids just gets very poor solution for very steep boundary layer or high local singularity problems. The present method is also applied to solve the 2D incompressible Navier–Stokes equations using the stream function–vorticity formulation and the numerical solutions of the lid-driven cavity flow problem are obtained and compared with solutions available in the literature.     

二维半线性扩散反应方程的高精度全隐格式及其多重网格方法

针对二维非定常半线性扩散反应方程，空间导数项采用四阶紧致差分公式离散，时间导数项采用四阶向后Euler公式进行离散，提出一种无条件稳定的高精度五层全隐格式.格式截断误差为O（τ⁴+τ²h²+h⁴），即时间和空间均具有四阶精度.对于第一、二、三时间层采用Crank-Nicolson方法进行离散，并采用Richardson外推公式将启动层时间精度外推到四阶.建立适用于该格式的多重网格方法，加快在每个时间层上迭代求解代数方程组的收敛速度，提高计算效率.最后通过数值实验验证格式的精确性和稳定性以及多重网格方法的高效性.     

Adaptive mesh refinement based on high order finite difference WENO scheme for multi-scale simulations

In this paper, we propose a finite difference AMR-WENO method for hyperbolic conservation laws. The proposed method combines the adaptive mesh refinement (AMR) framework  and  with the high order finite difference weighted essentially non-oscillatory (WENO) method in space and the total variation diminishing (TVD) Runge–Kutta (RK) method in time (WENO-RK)  and  by a high order coupling. Our goal is to realize mesh adaptivity in the AMR framework, while maintaining very high (higher than second) order accuracy of the WENO-RK method in the finite difference setting. The high order coupling of AMR and WENO-RK is accomplished by high order prolongation in both space (WENO interpolation) and time (Hermite interpolation) from coarse to fine grid solutions, and at ghost points. The resulting AMR-WENO method is accurate, robust and efficient, due to the mesh adaptivity and very high order spatial and temporal accuracy. We have experimented with both the third and the fifth order AMR-WENO schemes. We demonstrate the accuracy of the proposed scheme using smooth test problems, and their quality and efficiency using several 1D and 2D nonlinear hyperbolic problems with very challenging initial conditions. The AMR solutions are observed to perform as well as, and in some cases even better than, the corresponding uniform fine grid solutions. We conclude that there is significant improvement of the fifth order AMR-WENO over the third order one, not only in accuracy for smooth problems, but also in its ability in resolving complicated solution structures, due to the very low numerical diffusion of high order schemes. In our work, we found that it is difficult to design a robust AMR-WENO scheme that is both conservative and high order (higher than second order), due to the mass inconsistency of coarse and fine grid solutions at the initial stage in a finite difference scheme. Resolving these issues as well as conducting comprehensive evaluation of computational efficiency constitute our future work.     

Fourth order accurate evaluation of integrals in potential theory on exterior 3D regions

We present two methods for the rapid, high order accurate evaluation of integrals in potential theory on general, unbounded 3D regions. Our methods allow for direct calculation of derivatives of the integrals as well. One of the methods uses a fourth order compact stencil, and the other uses a nonstandard variant of Richardson extrapolation. Both methods involve calculation of discontinuities in high order derivatives of the integrals across the boundary of the integration region. The extrapolation method, in addition, involves correction for the discontinuities in truncation error. The number of operations required for the methods is essentially equal to twice the number of operations needed to solve Poisson’s equation on a regular grid. Both methods avoid problems associated with using quadrature methods to evaluate integrals with singular kernels. Numerical results are presented for experiments on a variety of geometries in free space.     

非定常Navier-Stokes方程基于两重网格离散的有限元并行算法

基于两重网格离散和区域分解技巧,提出三种求解非定常Navier-Stokes方程的有限元并行算法.算法的基本思想是在每一时间迭代步,在粗网格上采用Oseen迭代法求解非线性问题,在细网格上分别并行求解Oseen、Newton、Stokes线性问题以校正粗网格解.对于空间变量采用有限元离散,时间变量采用向后Euler格式离散.数值实验验证了算法的有效性.     

Advances in multi-domain lattice Boltzmann grid refinement

Grid refinement has been addressed by different authors in the lattice Boltzmann method community. The information communication and reconstruction on grid transitions is of crucial importance from the accuracy and numerical stability point of view. While a decimation is performed when going from the fine to the coarse grid, a reconstruction must performed to pass form the coarse to the fine grid. In this context, we introduce a decimation technique for the copy from the fine to the coarse grid based on a filtering operation. We show this operation to be extremely important, because a simple copy of the information is not sufficient to guarantee the stability of the numerical scheme at high Reynolds numbers. Then we demonstrate that to reconstruct the information, a local cubic interpolation scheme is mandatory in order to get a precision compatible with the order of accuracy of the lattice Boltzmann method.These two fundamental extra-steps are validated on two classical 2D benchmarks, the 2D circular cylinder and the 2D dipole–wall collision. The latter is especially challenging from the numerical point of view since we allow strong gradients to cross the refinement interfaces at a relatively high Reynolds number of 5000. A very good agreement is found between the single grid and the refined grid cases.The proposed grid refinement strategy has been implemented in the parallel open-source library Palabos.     

Simulation of axisymmetric jets with a finite element Navier–Stokes solver and a multilevel VOF approach

A multilevel VOF approach has been coupled to an accurate finite element Navier–Stokes solver in axisymmetric geometry for the simulation of incompressible liquid jets with high density ratios. The representation of the color function over a fine grid has been introduced to reduce the discontinuity of the interface at the cell boundary. In the refined grid the automatic breakup and coalescence occur at a spatial scale much smaller than the coarse grid spacing. To reduce memory requirements, we have implemented on the fine grid a compact storage scheme which memorizes the color function data only in the mixed cells. The capillary force is computed by using the Laplace–Beltrami operator and a volumetric approach for the two principal curvatures. Several simulations of axisymmetric jets have been performed to show the accuracy and robustness of the proposed scheme.     

Block structured adaptive mesh and time refinement for hybrid,hyperbolic + N-body systems

We present a new numerical algorithm for the solution of coupled collisional and collisionless systems, based on the block structured adaptive mesh and time refinement strategy (AMR). We describe the issues associated with the discretization of the system equations and the synchronization of the numerical solution on the hierarchy of grid levels. We implement a code based on a higher order, conservative and directionally unsplit Godunov’s method for hydrodynamics; a symmetric, time centered modified symplectic scheme for collisionless component; and a multilevel, multigrid relaxation algorithm for the elliptic equation coupling the two components. Numerical results that illustrate the accuracy of the code and the relative merit of various implemented schemes are also presented.     

A multi-domain Fourier pseudospectral time-domain method for the linearized Euler equations

The Fourier pseudospectral time-domain (F-PSTD) method is computationally one of the most cost-efficient methods for solving the linearized Euler equations for wave propagation through a medium with smoothly varying spatial inhomogeneities in the presence of rigid boundaries. As the method utilizes an equidistant discretization, local fine scale effects of geometry or medium inhomogeneities require a refinement of the whole grid which significantly reduces the computational efficiency. For this reason, a multi-domain F-PSTD methodology is presented with a coarse grid covering the complete domain and fine grids acting as a subgrid resolution of the coarse grid near local fine scale effects. Data transfer between coarse and fine grids takes place utilizing spectral interpolation with super-Gaussian window functions to impose spatial periodicity. Local time stepping is employed without intermediate interpolation. The errors introduced by the window functions and the multi-domain implementation are quantified and compared to errors related to the initial conditions and from the time iteration scheme. It is concluded that the multi-domain methodology does not introduce significant errors compared to the single-domain method. Examples of scattering from small scale density scatters, sound reflecting from a slitted rigid object and sound propagation through a jet are accurately modelled by the proposed methodology. For problems that can be solved by F-PSTD, the presented methodology can lead to a significant gain in computational efficiency.     

Multigrid method and fourth-order compact difference discretization scheme with unequal meshsizes for 3D poisson equation

A fourth-order compact difference discretization scheme with unequal meshsizes in different coordinate directions is employed to solve a three-dimensional (3D) Poisson equation on a cubic domain. Two multgrid methods are developed to solve the resulting sparse linear systems. One is to use the full-coarsening multigrid method with plane Gauss–Seidel relaxation, which uses line Gauss–Seidel relaxation to compute each planewise solution. The other is to construct a partial semi-coarsening multigrid method with the traditional point or plane Gauss–Seidel relaxations. Numerical experiments are conducted to test the computed accuracy of the fourth-order compact difference scheme and the computational efficiency of the multigrid methods with the fourth-order compact difference scheme.     

An effective explicit pressure gradient scheme implemented in the two-level non-staggered grids for incompressible Navier–Stokes equations

In this paper, an improved two-level method is presented for effectively solving the incompressible Navier–Stokes equations. This proposed method solves a smaller system of nonlinear Navier–Stokes equations on the coarse mesh and needs to solve the Oseen-type linearized equations of motion only once on the fine mesh level. Within the proposed two-level framework, a prolongation operator, which is required to linearize the convective terms at the fine mesh level using the convergent Navier–Stokes solutions computed at the coarse mesh level, is rigorously derived to increase the prediction accuracy. This indispensable prolongation operator can properly communicate the flow velocities between the two mesh levels because it is locally analytic. Solution convergence can therefore be accelerated. For the sake of numerical accuracy, momentum equations are discretized by employing the general solution for the two-dimensional convection–diffusion–reaction model equation. The convective instability problem can be simultaneously eliminated thanks to the proper treatment of convective terms. The converged solution is, thus, very high in accuracy as well as in yielding a quadratic spatial rate of convergence. For the sake of programming simplicity and computational efficiency, pressure gradient terms are rigorously discretized within the explicit framework in the non-staggered grid system. The proposed analytical prolongation operator for the mapping of solutions from the coarse to fine meshes and the explicit pressure gradient discretization scheme, which accommodates the dispersion-relation-preserving property, have been both rigorously justified from the predicted Navier–Stokes solutions.     

An efficient flexible-order model for 3D nonlinear water waves

The flexible-order, finite difference based fully nonlinear potential flow model described in [H.B. Bingham, H. Zhang, On the accuracy of finite difference solutions for nonlinear water waves, J. Eng. Math. 58 (2007) 211–228] is extended to three dimensions (3D). In order to obtain an optimal scaling of the solution effort multigrid is employed to precondition a GMRES iterative solution of the discretized Laplace problem. A robust multigrid method based on Gauss–Seidel smoothing is found to require special treatment of the boundary conditions along solid boundaries, and in particular on the sea bottom. A new discretization scheme using one layer of grid points outside the fluid domain is presented and shown to provide convergent solutions over the full physical and discrete parameter space of interest. Linear analysis of the fundamental properties of the scheme with respect to accuracy, robustness and energy conservation are presented together with demonstrations of grid independent iteration count and optimal scaling of the solution effort. Calculations are made for 3D nonlinear wave problems for steep nonlinear waves and a shoaling problem which show good agreement with experimental measurements and other calculations from the literature.     

An optimized spectral difference scheme for CAA problems

In the implementation of spectral difference (SD) method, the conserved variables at the flux points are calculated from the solution points using extrapolation or interpolation schemes. The errors incurred in using extrapolation and interpolation would result in instability. On the other hand, the difference between the left and right conserved variables at the edge interface will introduce dissipation to the SD method when applying a Riemann solver to compute the flux at the element interface. In this paper, an optimization of the extrapolation and interpolation schemes for the fourth order SD method on quadrilateral element is carried out in the wavenumber space through minimizing their dispersion error over a selected band of wavenumbers. The optimized coefficients of the extrapolation and interpolation are presented. And the dispersion error of the original and optimized schemes is plotted and compared. An improvement of the dispersion error over the resolvable wavenumber range of SD method is obtained. The stability of the optimized fourth order SD scheme is analyzed. It is found that the stability of the 4th order scheme with Chebyshev–Gauss–Lobatto flux points, which is originally weakly unstable, has been improved through the optimization. The weak instability is eliminated completely if an additional second order filter is applied on selected flux points. One and two dimensional linear wave propagation analyses are carried out for the optimized scheme. It is found that in the resolvable wavenumber range the new SD scheme is less dispersive and less dissipative than the original scheme, and the new scheme is less anisotropic for 2D wave propagation. The optimized SD solver is validated with four computational aeroacoustics (CAA) workshop benchmark problems. The numerical results with optimized schemes agree much better with the analytical data than those with the original schemes.     

三维不可压N-S方程的多重网格求解

应用全近似存储(Full Approximation Storage,FAS)多重网格法和人工压缩性方法求解了三维不可压Navi-er-Stokes方程.在解粗网格差分方程时,对Neumann边界条件采用增量形式进行更新,离散方程用对角化形式的近似隐式因子分解格式求解,其中空间无粘项分别用MUSCL格式和对称TVD格式进行离散.对90°弯曲的方截面管道流动和4:1椭球体层流绕流的数值模拟表明,多重网格的计算时间比单重网格节省一半以上,且无限制函数的MUSCL格式比TVD格式对流动结构有更好的分辨能力.     

The effect of the 2-D Laplacian operator approximation on the performance of finite-difference time-domain schemes for Maxwell’s equations

The behavior of the finite-difference time-domain method (FDTD) is investigated with respect to the approximation of the two-dimensional Laplacian, associated with the curl–curl operator. Our analysis begins from the observation that in a two-dimensional space the Yee algorithm approximates the Laplacian operator via a strongly anisotropic 5-point approximation. It is demonstrated that with the aid of a transversely extended-curl operator any 9-point Laplacian can be mapped onto FDTD update equations. Our analysis shows that the mapping of an isotropic Laplacian approximation results in an isotropic and less dispersive FDTD scheme. The properties of the extended curl are further explored and it is proved that a unity Courant number can be achieved without the resulting scheme suffering from grid decoupling. Additionally, the case of a 25-point isotropic Laplacian is examined and it is shown that the corresponding scheme is fourth order accurate in space and exhibits isotropy up to sixth order. Representative numerical simulations are performed that validate the theoretically derived results.     

A second-order accurate numerical method for the two-dimensional fractional diffusion equation

Spatially fractional order diffusion equations are generalizations of classical diffusion equations which are used in modeling practical superdiffusive problems in fluid flow, finance and others. In this paper, we present an accurate and efficient numerical method to solve a fractional superdiffusive differential equation. This numerical method combines the alternating directions implicit (ADI) approach with a Crank–Nicolson discretization and a Richardson extrapolation to obtain an unconditionally stable second-order accurate finite difference method. The stability and the consistency of the method are established. Numerical solutions for an example super-diffusion equation with a known analytic solution are obtained and the behavior of the errors are analyzed to demonstrate the order of convergence of the method.     

各向同性紊流能量衰减的大涡模拟

在多重网格驱动的,高效且得到充分验证的有限体积方法的基础上发展了可压缩流大涡模拟的方法.空间离散采用Jameson的中心格式附加二阶和四阶耗散的方法,时间推进则采用了双时间步长的方法.亚格子剪切应力张量和亚格子热通量用Smagorinsky模型进行模拟.通过对各向同性紊流能量衰减的模拟来验证本方法的准确性和高效性,模拟得到的能量谱和紊流动能衰减历程与过滤后的CBC实验数据吻合良好.     

奇异退化扩散反应方程的高阶紧致差分及网格自适应方法

利用余项修正法建立奇异退化扩散反应方程非均匀网格上的高阶紧致差分式,其时间具有二阶精度,空间具有三阶至四阶精度. 利用等分布原理建立时间和空间的网格自适应方法.最后通过具有精确解的数值算例验证方法的可靠性和精确性,并研究一维爆破问题.