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.     

Sixth order compact scheme combined with multigrid method and extrapolation technique for 2D poisson equation

We develop a sixth order finite difference discretization strategy to solve the two dimensional Poisson equation, which is based on the fourth order compact discretization, multigrid method, Richardson extrapolation technique, and an operator based interpolation scheme. We use multigrid V-Cycle procedure to build our multiscale multigrid algorithm, which is similar to the full multigrid method (FMG). The multigrid computation yields fourth order accurate solution on both the fine grid and the coarse grid. A sixth order accurate coarse grid solution is computed by using the Richardson extrapolation technique. Then we apply our operator based interpolation scheme to compute sixth order accurate solution on the fine grid. Numerical experiments are conducted to show the solution accuracy and the computational efficiency of our new method, compared to Sun–Zhang’s sixth order Richardson extrapolation compact (REC) discretization strategy using Alternating Direction Implicit (ADI) method and the standard fourth order compact difference (FOC) scheme using a multigrid method.     

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.     

求解非线性Poisson方程的格子演化算法

非线性Poisson方程在化学、化工及生物等领域有着广泛的应用。本文发展了一种基于格子演化的新算法-格子Poisson方法(LPM),并且给出了Dirichlet边界条件和Neumann边界条件的实现方法。本方法不需要对方程进行线化处理,直接求解非线性方程,适用范围广泛。Dirichlet边界与Neumann边界的数值模拟结果与多重网格法等结果符合很好,验证了该方法在求解非线性Poisson方程的正确性与有效性。本方法非常适合并行计算,并方便扩展到三维情况。     

An efficient method for the incompressible Navier–Stokes equations on irregular domains with no-slip boundary conditions,high order up to the boundary

Common efficient schemes for the incompressible Navier–Stokes equations, such as projection or fractional step methods, have limited temporal accuracy as a result of matrix splitting errors, or introduce errors near the domain boundaries (which destroy uniform convergence to the solution). In this paper we recast the incompressible (constant density) Navier–Stokes equations (with the velocity prescribed at the boundary) as an equivalent system, for the primary variables velocity and pressure. equation for the pressure. The key difference from the usual approaches occurs at the boundaries, where we use boundary conditions that unequivocally allow the pressure to be recovered from knowledge of the velocity at any fixed time. This avoids the common difficulty of an, apparently, over-determined Poisson problem. Since in this alternative formulation the pressure can be accurately and efficiently recovered from the velocity, the recast equations are ideal for numerical marching methods. The new system can be discretized using a variety of methods, including semi-implicit treatments of viscosity, and in principle to any desired order of accuracy. In this work we illustrate the approach with a 2-D second order finite difference scheme on a Cartesian grid, and devise an algorithm to solve the equations on domains with curved (non-conforming) boundaries, including a case with a non-trivial topology (a circular obstruction inside the domain). This algorithm achieves second order accuracy in the L^∞ norm, for both the velocity and the pressure. The scheme has a natural extension to 3-D.     

Fourier spectral embedded boundary solution of the Poisson’s and Laplace equations with Dirichlet boundary conditions

A Fourier spectral embedded boundary method, for solution of the Poisson’s equation with Dirichlet boundary conditions and arbitrary forcing functions (including zero forcing function), is presented in this paper. This iterative method begins by transformation of the Dirichlet boundary conditions from the physical boundaries to some corresponding regular grid points (which are called the numerical boundaries), using a second order interpolation method. Then the transformed boundary conditions and the forcing function are extended to a square, smoothly and periodically, via multiplying them by some suitable error functions. Instead of direct solution of the resulting extended Poisson’s problem, it is suggested to define and solve an equivalent transient diffusion problem on the regular domain, until achievement of the steady solution (which is considered as the solution of the original problem). Without need of any numerical time integration method, time advancement of the solution is obtained directly, from the exact solution of the transient problem in the Fourier space. Consequently, timestep sizes can be chosen without stability limitations, which it means higher rates of convergence in comparison with the classical relaxation methods. The method is presented in details for one- and two-dimensional problems, and a new emerged phenomenon (which is called the saturation state) is illustrated both in the physical and spectral spaces. The numerical experiments have been performed on the one- and two-dimensional irregular domains to show the accuracy of the method and its superiority (from the rate of convergence viewpoint) to the other classical relaxation methods. Capability of the method, in dealing with complex geometries, and in presence of discontinuity at the boundaries, has been shown via some numerical experiments on a four-leaf shape geometry.     

A second order virtual node method for elliptic problems with interfaces and irregular domains

We present a second order accurate, geometrically flexible and easy to implement method for solving the variable coefficient Poisson equation with interfacial discontinuities or on irregular domains, handling both cases with the same approach. We discretize the equations using an embedded approach on a uniform Cartesian grid employing virtual nodes at interfaces and boundaries. A variational method is used to define numerical stencils near these special virtual nodes and a Lagrange multiplier approach is used to enforce jump conditions and Dirichlet boundary conditions. Our combination of these two aspects yields a symmetric positive definite discretization. In the general case, we obtain the standard 5-point stencil away from the interface. For the specific case of interface problems with continuous coefficients, we present a discontinuity removal technique that admits use of the standard 5-point finite difference stencil everywhere in the domain. Numerical experiments indicate second order accuracy in L^∞.     

Pressure boundary conditions for computing incompressible flows with SPH

In Smoothed Particle Hydrodynamics (SPH) methods for fluid flow, incompressibility may be imposed by a projection method with an artificial homogeneous Neumann boundary condition for the pressure Poisson equation. This is often inconsistent with physical conditions at solid walls and inflow and outflow boundaries. For this reason open-boundary flows have rarely been computed using SPH. In this work, we demonstrate that the artificial pressure boundary condition produces a numerical boundary layer that compromises the solution near boundaries. We resolve this problem by utilizing a “rotational pressure-correction scheme” with a consistent pressure boundary condition that relates the normal pressure gradient to the local vorticity. We show that this scheme computes the pressure and velocity accurately near open boundaries and solid objects, and extends the scope of SPH simulation beyond the usual periodic boundary conditions.     

Handling solid–fluid interfaces for viscous flows: Explicit jump approximation vs. ghost cell approaches

The ghost cell approaches (GCA) for handling stationary solid boundaries, regular or irregular, are first investigated theoretically and numerically for the diffusion equation with Dirichlet boundary conditions. The main conclusion of this part of investigation is that the approximation for the diffusion term has to be second-order accurate everywhere in order for the numerical solution to be rigorously second-order accurate. Violating this principle, the linear and quadratic GCAs have the following shortcomings: (1) restrictive constraints on grid size when the viscosity is small; (2) susceptibleness to instability of a time-explicit formulation for strongly transient flows; (3) convergence deterioration to zeroth- or first-order for solutions with high-frequency modes. Therefore, the widely-used linear extrapolation for enforcing no-slip boundary conditions should be avoided, even for regular solid boundaries. As a remedy, a simple method based on explicit jump approximation (EJA) is proposed. EJA hinges on the idea that a velocity-derivative jump at the boundary reduces to the value of the velocity-derivative at the fluid side because the velocity of the stationary boundary is zero. Although the time-marching linear system of EJA is not symmetric, it is strictly diagonal dominant with positive diagonal entries. Numerical results show that, over a large range of viscosity and grid sizes, EJA performs much better than GCAs in terms of stability and accuracy. Furthermore, the second-order convergence of EJA does not depend on viscosity and the spectrum of the solution, as those of GCAs do. This paper is written with enough details so that one can reproduce the numerical results.     

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

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

A hybrid spectral/DG method for solving the phase-averaged ocean wave equation: Algorithm and validation

We develop a new high-order hybrid discretization of the phased-averaged (action balance) equation to simulate ocean waves. We employ discontinuous Galerkin (DG) discretization on an unstructured grid in geophysical space and Fourier-collocation along the directional and frequency coordinates. The original action balance equation is modified to facilitate absorbing boundary conditions along the frequency direction; this modification enforces periodicity at the frequency boundaries so that the fast convergence of Fourier-collocation holds. In addition, a mapping along the directional coordinate is introduced to cluster the collocation points around steep directional spectra. Time-discretization is accomplished by the TVD Runge–Kutta scheme. The overall convergence of the scheme is exponential (spectral). We successfully verified and validated the method against several analytical solutions, observational data, and experimental results.     

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.     

Open and traction boundary conditions for the incompressible Navier–Stokes equations

We present numerical schemes for the incompressible Navier–Stokes equations (NSE) with open and traction boundary conditions. We use pressure Poisson equation (PPE) formulation and propose new boundary conditions for the pressure on the open or traction boundaries. After replacing the divergence free constraint by this pressure Poisson equation, we obtain an unconstrained NSE. For Stokes equation with open boundary condition on a simple domain, we prove unconditional stability of a first order semi-implicit scheme where the pressure is treated explicitly and hence is decoupled from the computation of velocity. Using either boundary condition, the schemes for the full NSE that treat both convection and pressure terms explicitly work well with various spatial discretizations including spectral collocation and C⁰ finite elements. Moreover, when Reynolds number is of O(1) and when the first order semi-implicit time stepping is used, time step size of O(1) is allowed in benchmark computations for the full NSE. Besides standard stability and accuracy check, various numerical results including flow over a backward facing step, flow past a cylinder and flow in a bifurcated tube are reported. Numerically we have observed that using PPE formulation enables us to use the velocity/pressure pairs that do not satisfy the standard inf–sup compatibility condition. Our results extend that of Johnston and Liu [H. Johnston, J.-G. Liu, Accurate, stable and efficient Navier–Stokes solvers based on explicit treatment of the pressure term. J. Comp. Phys. 199 (1) (2004) 221–259] which deals with no-slip boundary conditions only.     

A second order virtual node method for elliptic problems with interfaces and irregular domains in three dimensions

We present a numerical method for the variable coefficient Poisson equation in three-dimensional irregular domains and with interfacial discontinuities. The discretization embeds the domain and interface into a uniform Cartesian grid augmented with virtual degrees of freedom to provide accurate treatment of jump and boundary conditions. The matrix associated with the discretization is symmetric positive definite and equal to the standard 7-point finite difference Poisson stencil away from embedded interfaces and boundaries. Numerical evidence suggests second order accuracy in the L^∞-norm. Our approach improves the treatment of Dirichlet and jump constraints in the recent work of Bedrossian et al. [1] and introduces innovations necessary in three dimensions. Specifically, we construct new constraint-based Lagrange multiplier spaces that significantly improve the conditioning of the associated linear system of equations; we provide a method for cell-local polyhedral approximation to the zero isocontour surface of a level set needed for three-dimensional embedding; and we show that the new Lagrange multiplier spaces naturally lead to a class of easy-to-implement multigrid methods that achieve near optimal efficiency, as shown by numerical examples. For the specific case of a continuous Poisson coefficient in interface problems, we provide an expansive treatment of the construction of a particular solution that satisfies the value jump and flux jump constraints. As in [1], this is used in a discontinuity removal technique that yields the standard 7-point stencil across the interface and only requires a modification to the right-hand side of the linear system.     

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 accurate, stable and efficient domain-type meshless method for the solution of MHD flow problems

The aim of the present paper is the development of an efficient numerical algorithm for the solution of magnetohydrodynamics flow problems for regular and irregular geometries subject to Dirichlet, Neumann and Robin boundary conditions. Toward this, the meshless point collocation method (MPCM) is used for MHD flow problems in channels with fully insulating or partially insulating and partially conducting walls, having rectangular, circular, elliptical or even arbitrary cross sections. MPC is a truly meshless and computationally efficient method. The maximum principle for the discrete harmonic operator in the meshfree point collocation method has been proven very recently, and the convergence proof for the numerical solution of the Poisson problem with Dirichlet boundary conditions have been attained also. Additionally, in the present work convergence is attained for Neumann and Robin boundary conditions, accordingly. The shape functions are constructed using the Moving Least Squares (MLS) approximation. The refinement procedure with meshless methods is obtained with an easily handled and fully automated manner. We present results for Hartmann number up to 10⁵${10}^5$. The numerical evidences of the proposed meshless method demonstrate the accuracy of the solutions after comparing with the exact solution and the conventional FEM and BEM, for the Dirichlet, Neumann and Robin boundary conditions of interior problems with simple or complex boundaries.     

A multiresolution remeshed Vortex-In-Cell algorithm using patches

We present a novel multiresolution Vortex-In-Cell algorithm using patches of varying resolution. The Poisson equation relating the fluid vorticity and velocity is solved using Fast Fourier Transforms subject to free space boundary conditions. Solid boundaries are implemented using the semi-implicit formulation of Brinkman penalization and we show that the penalization can be carried out as a simple interpolation. We validate the implementation against the analytic solution to the Perlman test case and by free-space simulations of the onset flow around fixed and rotating circular cylinders and bluff body flows around bridge sections.     

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.     

并行代数多重网格算法可扩展性能分析

对当今求解大型稀疏线性代数方程组最有效的迭代方法之--代数多重网格(AMG)算法的并行计算进行可扩展性能分析.给出一套并行计算可扩展性能分析方法,用于分析和指导并行迭代算法及实现技术的设计与优化并应用于并行AMG算法.分析表明,网格算子的平均模式大小和迭代过程的算法效率分别制约了AMG算法启动阶段和迭代求解阶段并行性能的发挥,成为该类算法急需解决的两个关键问题.