多重网格技术对SIMPLER算法的加速性能研究

将多重网格技术引入SIMPLER算法以加快其收敛速度,从而节约计算时间。通过计算不同雷诺数下的二维方腔顶盖驱动流,研究了多重网格方法中的V循环、W循环对SIMPLER算法的加速效果,并讨论了网格层数对加速性能的影响。研究结果表明,在不同雷诺数下,多重网格方法均可以起到良好的加速效果;在相同雷诺数和精度要求下,W循环方式的外迭代次数少于V循环方式的外迭代次数,而且网格层数对多重网格加速性能的影响并不显著。     

Numerical experiments with the lid driven cavity flow problem

The centerline velocity profiles obtained from the solution of the two- and three-dimensional representations of the lid driven cavity flow problem are compared for different Reynolds numbers. Two configurations were used in this study: a unit cavity and a cavity with an aspect ratio of 2. The Reynolds numbers ranged from 100 to 5000 for all of the configurations studied. A new method of extending the Jacobi collocation technique called spectral difference is developed in this paper together with a unique computational grid. In addition, an iterative method for solving the pressure problem is also developed. This new numerical method allowed the calculation of three-dimensional Navier-Stokes equations to be performed in computers with very modest computational capabilities such as workstations.     

Incompressible flow calculations with a consistent physical interpolation finite volume approach

The computation of incompressible three-dimensional viscous flow is discussed. A new physically consistent method is presented for the reconstruction for velocity fluxes which arise from the mass and momentum balance discrete equations. This closure method for fluxes allows the use of a cell-centered grid in which velocity and pressure unknowns share the same location, while circumventing the occurrence of spurious pressure modes. The method is validated on several benchmark problems which include steady laminar flow predictions on a two-dimensional cartesian (lid driven 2D cavity) or curvilinear grid (circular cylinder problem at Re = 40), unsteady three-dimensional laminar flow predictions on a cartesian grid (parallelopipedic lid driven cavity) and unsteady two-dimensional turbulent flow predictions on a curvilinear grid (vortex shedding past a square cylinder at Re = 22,000).     

Evaluation of multigrid acceleration for preconditioned time-accurate Navier-Stokes algorithms

The development of a two-dimensional time-accurate dual time step Navier-Stokes flow solver with time-derivative preconditioning and multigrid acceleration is described. The governing equations are integrated in time with both an explicit Runge-Kutta scheme and an implicit lower-upper symmetric-Gauss-Seidel scheme in a finite volume framework, yielding second-order accuracy in space and time. Issues concerning the implementation of multigrid for preconditioned, dual time step algorithms are discussed. Steady and unsteady computations were made of lid driven cavity flow, thermally driven cavity flow and pulsatile channel flow for a variety of conditions to validate the schemes and evaluate the effectiveness of multigrid for time-accurate simulations. Significant speedups were observed for steady and unsteady simulations. The speedups for unsteady simulations were problem dependent, a function of how rapidly the flow varied in time and the size of the allowable time step.     

Multigrid solvers for the non-aligned sonic flow: the constant coefficient case

An approach for the construction of multigrid solvers for non-elliptic equations on a rectangular grid is presented. The results of both the analysis and the numerical experiments demonstrate that such an approach permits a full multigrid efficiency to be achieved, even in the case that the equation characteristics do not align with the grid. To serve as a model problem, the two- and three-dimensional linearized sonic-flow equations with a constant velocity field have been chosen. Efficient FMG solvers for the problems are demonstrated.     

The Navier–Stokes-αβ equations as a platform for a spectral multigrid method to solve the Navier–Stokes equations

This paper describes a spectral multigrid method for spatially periodic homogeneous and isotropic turbulent flows. The method uses the Navier–Stokes-αβ equations to accelerate convergence toward solutions of the Navier–Stokes equations. The Navier–Stokes-αβ equations are solved on coarse grids at various levels and the Navier–Stokes equations are solved on the “nest grid”. The method uses Crank–Nicolson time-stepping for the viscous terms, explicit time-stepping for the remaining terms, and Richardson iteration to solve linear systems encountered at each time step and on each grid level. To explore the computational efficiency of the method, comparisons are made with results obtained from an analogous spectral multigrid method for the Navier–Stokes equations. These comparisons are based on computing work units and residuals for multigrid cycles. Most importantly, we examine how choosing different values of the length scales α and β entering the Navier–Stokes-αβ equations influence the efficiency and accuracy of these multigrid schemes.     

Comparison of finite-volume numerical methods with staggered and colocated grids

The paper presents a detailed comparison of two finite-volume solution methods for two-dimensional incompressible fluid flows, one with staggered and the other with colocated numerical grids. The staggered method is well-known and well-established, and it is used here as a standard against which the relatively new colocated approach is compared. Three test cases were considered, employing orthogonal rectilinear grids: lid driven cavity flow, backward facing step flow and flow through a pipe with sudden contraction. The results of the computations demonstrate that the convergence rate, dependency on under-relaxation parameters, computational effort and accuracy are almost identical for both solution methods. The colocated method converges faster in some cases, and has advantages when extensions such as multigrid techniques and non-orthogonal grids are considered.     

Parallelism in multigrid methods: How much is too much?

Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism, but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1) domain-parallel versions of the standard V-cycle and F-cycle algorithms; (2) a multiple coarse grid algorithm, proposed by Fredrickson and McBryan, which generates several coarse grids for each fine grid; and (3) two Rosendale algorithm, which allow computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference techniques on block-structured meshes in two or three dimensions with up to 10⁶ or 10⁹ points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models. The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which contain a large number of small (bitserial) processors, and SPMD medium-grain computers, which have a more modest number of powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than algorithms utilizing either parallel strategy. Both parallel strategies need too much extra work to compensate for their extra parallelism. They require a highly impractical number of processors to be competitive with simpler, standard algorithms. The analysis also suggests that the F-cycle, with the appropriate optimization techniques, is more efficient than the V-cycle under a broad range of problem, implementation, and machine characteristics, despite the fact that it exhibits even less parallelism than the V-cycle. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463.     

Adaptive multigrid for finite element computations in plasticity

The solution of the system of equilibrium equations is the most time-consuming part in large-scale finite element computations of plasticity problems. The development of efficient solution methods are therefore of utmost importance to the field of computational plasticity. Traditionally, direct solvers have most frequently been used. However, recent developments of iterative solvers and preconditioners may impose a change. In particular, preconditioning by the multigrid technique is especially favorable in FE applications.The multigrid preconditioner uses a number of nested grid levels to improve the convergence of the iterative solver. Prolongation of fine-grid residual forces is done to coarser grids and computed corrections are interpolated to the fine grid such that the fine-grid solution successively is improved. By this technique, large 3D problems, invincible for solvers based on direct methods, can be solved in acceptable time at low memory requirements. By means of a posteriori error estimates the computational grid could successively be refined (adapted) until the solution fulfils a predefined accuracy level. In contrast to procedures where the preceding grids are erased, the previously generated grids are used in the multigrid algorithm to speed up the solution process.The paper presents results using the adaptive multigrid procedure to plasticity problems. In particular, different error indicators are tested.     

A multigrid solver for two-dimensional stochastic diffusion equations

Steady and unsteady diffusion equations, with stochastic diffusivity coefficient and forcing term, are modeled in two dimensions by means of stochastic spectral representations. Problem data and solution variables are expanded using the Polynomial Chaos system. The approach leads to a set of coupled problems for the stochastic modes. Spatial finite-difference discretization of these coupled problems results in a large system of equations, whose dimension necessitates the use of iterative approaches in order to obtain the solution within a reasonable computational time. To accelerate the convergence of the iterative technique, a multigrid method, based on spatial coarsening, is implemented. Numerical experiments show good scaling properties of the method, both with respect to the number of spatial grid points and the stochastic resolution level.     

Multigrid Methods for Hellan–Herrmann–Johnson Mixed Method of Kirchhoff Plate Bending Problems

A V-cycle multigrid method for the Hellan–Herrmann–Johnson (HHJ) discretization of the Kirchhoff plate bending problems is developed in this paper. It is shown that the contraction number of the V-cycle multigrid HHJ mixed method is bounded away from one uniformly with respect to the mesh size. The uniform convergence is achieved for the V-cycle multigrid method with only one smoothing step and without full elliptic regularity assumption. The key is a stable decomposition of the kernel space which is derived from an exact sequence of the HHJ mixed method, and the strengthened Cauchy Schwarz inequality. Some numerical experiments are provided to confirm the proposed V-cycle multigrid method. The exact sequences of the HHJ mixed method and the corresponding commutative diagram is of some interest independent of the current context.     

A modified full multigrid algorithm for the Navier-Stokes equations

A modified full multigrid (FMG) method for the solution of the Navier-Stokes equations is presented. The method proposed is based on a V-cycle omitting the restriction procedure for dependent variables but retaining it for the residuals. This modification avoids possible mismatches between the mass fluxes and the restricted velocities as well as the turbulent viscosity and the turbulence quantities on the coarse grid. In addition, the pressure on the coarse grid can be constructed in the same way as the velocities. These features simplify the multigrid strategy and corresponding programming efforts. This algorithm is applied to accelerate the convergence of the solution of the Navier-Stokes equations for both laminar and high-Reynolds number turbulent flows. Numerical simulations of academic and practical engineering problems show that the modified algorithm is much more efficient than the FMG-FAS (Full Approximation Storage) method.     

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

An Extrapolation Cascadic Multigrid Method Combined with a Fourth-Order Compact Scheme for 3D Poisson Equation

Extrapolation cascadic multigrid (EXCMG) method is an efficient multigrid method which has mainly been used for solving the two-dimensional elliptic boundary value problems with linear finite element discretization in the existing literature. In this paper, we develop an EXCMG method to solve the three-dimensional Poisson equation on rectangular domains by using the compact finite difference (FD) method with unequal meshsizes in different coordinate directions. The resulting linear system from compact FD discretization is solved by the conjugate gradient (CG) method with a relative residual stopping criterion. By combining the Richardson extrapolation and tri-quartic Lagrange interpolation for the numerical solutions from two-level of grids (current and previous grids), we are able to produce an extremely accurate approximation of the actual numerical solution on the next finer grid, which can greatly reduce the number of relaxation sweeps needed. Additionally, a simple method based on the midpoint extrapolation formula is used for the fourth-order FD solutions on two-level of grids to achieve sixth-order accuracy on the entire fine grid cheaply and directly. The gradient of the numerical solution can also be easily obtained through solving a series of tridiagonal linear systems resulting from the fourth-order compact FD discretizations. Numerical results show that our EXCMG method is much more efficient than the classical V-cycle and W-cycle multigrid methods. Moreover, only few CG iterations are required on the finest grid to achieve full fourth-order accuracy in both the \(L^2\)-norm and \(L^{\infty }\)-norm for the solution and its gradient when the exact solution belongs to \(C^6\). Finally, numerical result shows that our EXCMG method is still effective when the exact solution has a lower regularity, which widens the scope of applicability of our EXCMG method.     

Inertial thin film flow on planar surfaces featuring topography

A range of problems is investigated, involving the gravity-driven inertial flow of a thin viscous liquid film over an inclined planar surface containing topographical features, modelled via a depth-averaged form of the governing unsteady Navier-Stokes equations. The discrete analogue of the resulting coupled equation set, employing a staggered mesh arrangement for the dependent variables, is solved accurately using an efficient full approximation storage (FAS) algorithm and a full multigrid (FMG) technique; together with error-controlled automatic adaptive time-stepping and proper treatment of the associated nonlinear convective terms. An extensive set of results is presented for flow over both one- and two-dimensional topographical features, and errors quantified via detailed comparisons drawn with complementary experimental data and predictions from finite element analyses where they exist. In the case of one-dimensional (spanwise) topography, moderate Reynolds numbers and shallow/short topographical features, the results obtained are in close agreement with corresponding finite element solutions of the full free-surface problem. For the case of flow over two-dimensional (localised) topography, it is shown that the free-surface disturbance is influenced significantly by the presence of inertia leading, as in the case of spanwise topography, to an increase in the magnitude and severity of the resulting capillary ridge and trough formations: the effect of inclination angle and topography aspect ratio are similarly explored.     

Multigrid solution of the steady-state lattice Boltzmann equation

Efficient solution strategies for the steady-state lattice Boltzmann equation are investigated. Stable iterative methods for the linearized lattice Boltzmann equation are formulated based on the linearization of the lattice Boltzmann time-stepping procedure. These are applied as relaxation methods within a linear multigrid scheme, which itself is used to drive a Newton solver for the full non-linear problem. Although the linear multigrid strategy provides rapid convergence, the cost of a linear residual evaluation is found to be substantially higher than the cost of evaluating the non-linear residual directly. Therefore, a non-linear multigrid approach is adopted, which makes use of the non-linear LBE time-stepping scheme on each grid level. Rapid convergence to steady-state is achieved by the non-linear algorithm, resulting in one or more orders of magnitude increase in solution efficiency over the LBE time-integration approach. Grid-independent convergence rates are demonstrated, although degradation with increasing Reynolds number is observed, as in the case of the original LBE time-stepping scheme. The multigrid solver is implemented in a modular fashion by calling an existing LBE time-stepping routine, and delivers the identical steady-state solution as the original LBE time-stepping approach.     

Multigrid method for stability problems

The problem of calculating the stability of steady state solutions of differential equations is treated. Leading eigenvalues (i.e., having maximal real part) of large matrices that arise from discretization are to be calculated. An efficient multigrid method for solving these problems is presented. The method begins by obtaining an initial approximation for the dominant subspace on a coarse level using a damped Jacobi relaxation. This proceeds until enough accuracy for the dominant subspace has been obtained. The resulting grid functions are then used as an initial approximation for appropriate eigenvalue problems. These problems are solved first on coarse levels, followed by refinement until a desired accuracy for the eigenvalues has been achieved. The method employs local relaxation on all levels together with a global change on the coarsest level only, which is designed to separate the different eigenfunctions as well as to update their corresponding eigenvalues. Coarsening is done using the FAS formulation in a nonstandard way in which the right-hand side of the coarse grid equations involves unknown parameters to be solved for on the coarse grid. This in particular leads to a new multigrid method for calculating the eigenvalues of symmetric problems. Numerical experiments with a model problem that are presented demonstrate the effectiveness of the method proposed. Using an FMG algorithm a solution to the level of discretization errors is obtained in just a few work units (less than 10), where a work unit is the work involved in one Jacobi relaxation on the finest level.     

A Newton-like method for solving a non-smooth elliptic equation

In this paper, we use finite element method to discrete a non-smooth elliptic equation and present some error estimates. Non-smooth Newton-like method is applied to solve the discrete problem. Since Newton's equations have a very bad conditioner when the mesh-size is finer, multigrid technique is used to solve the subproblems. It is shown that if we use V-cycle or cascadic multigrid as an inner iterator, an (nearly) optimal property can be obtained. Numerical results are illustrated to confirm the error estimates we obtained and the efficiency of the non-smooth Newton-like method combining with multigrid technique. Especially, if the mesh-size h becomes much smaller, the method can save substantial computational work.     

Multigrid method for nonlinear poroelasticity equations

In this study, a nonlinear multigrid method is applied for solving the system of incompressible poroelasticity equations considering nonlinear hydraulic conductivity. For the unsteady problem, an additional artificial term is utilized to stabilize the solutions when the equations are discretized on collocated grids. We employ two nonlinear multigrid methods, i.e. the “full approximation scheme” and “Newton multigrid” for solving the corresponding system of equations arising after discretization. For the steady case, both homogeneous and heterogeneous cases are solved and two different smoothers are examined to search for an efficient multigrid method. Numerical results show a good convergence performance for all the strategies.     

Data‐driven projection method in fluid simulation

Physically based fluid simulation requires much time in numerical calculation to solve Navier–Stokes equations. Especially in grid‐based fluid simulation, because of iterative computation, the projection step is much more time‐consuming than other steps. In this paper, we propose a novel data‐driven projection method using an artificial neural network to avoid iterative computation. Once the grid resolution is decided, our data‐driven method could obtain projection results in relatively constant time per grid cell, which is independent of scene complexity. Experimental results demonstrated that our data‐driven method drastically speeded up the computation in the projection step. With the growth of grid resolution, the speed‐up would increase strikingly. In addition, our method is still applicable in different fluid scenes with some alterations, when computational cost is more important than physical accuracy. Copyright © 2016 John Wiley & Sons, Ltd.