Multi‐Block Solution Algorithm for Joint PDF Methods

A multi‐block grid (MBG) based algorithm to solve the joint velocity‐frequency‐composition PDF transport equation for turbulent reactive flow is presented. The algorithm is based on a previously developed hybrid finite‐volume/particle approach which has significant advantages over stand alone particle PDF methods. It is demonstrated that the new solution method, due to the flexibility of MBGs, allows to perform simulation studies which involve very complex 3D geometries. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.     

A multigrid method for grid generation with line-spacing control

A multigrid method for grid generation on two-dimensional regions and its applications to test problems are presented. The multigrid algorithm deals with the solution of elliptic differential problems which occur in the computation of boundary-fitted grids. The solution of elliptic systems of partial differential equations, which correspond to transformed Poisson systems, is carried out by a full approximation storage (FAS) algorithm. The components of the method, such as the relaxation for error smoothing and the coarsening strategy, are evaluated on problems in which sources of attractions are considered, and the generated grids are shown by figures.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

Multigrid transfers for nonsymmetric systems based on Schur complements and Galerkin projections

A framework is proposed for constructing algebraic multigrid transfer operators suitable for nonsymmetric positive definite linear systems. This framework follows a Schur complement perspective as this is suitable for both symmetric and nonsymmetric systems. In particular, a connection between algebraic multigrid and approximate block factorizations is explored. This connection demonstrates that the convergence rate of a two‐level model multigrid iteration is completely governed by how well the coarse discretization approximates a Schur complement operator. The new grid transfer algorithm is then based on computing a Schur complement but restricting the solution space of the corresponding grid transfers in a Galerkin‐style so that a far less expensive approximation is obtained. The final algorithm corresponds to a Richardson‐type iteration that is used to improve a simple initial prolongator or a simple initial restrictor. Numerical results are presented illustrating the performance of the resulting algebraic multigrid method on highly nonsymmetric systems. Copyright © 2013 John Wiley & Sons, Ltd.     

Artificial damping in multigrid methods

When the solution and problem coefficients are highly oscillatory, the computed solution may not show characteristics of the original physical problem unless the numerical mesh is sufficiently fine. In the case, the coarse grid problem of a multigrid (MG) algorithm must be still huge and poorly-conditioned, and therefore, it is hard to solve by either a direct method or an iterative scheme. This article suggests a MG algorithm for such problems in which the coarse grid problem is slightly modified by an artificial damping (compressibility) term. It has been numerically observed that the artificial damping, even if slight, makes the coarse grid problem much easier to solve, without deteriorating the overall convergence rate of the MG method. For most problems, 2–6 times speed up have been observed.     

Single-level multigrid

A single-level multigrid algorithm is developed in which coarse-grid correction is performed on the fine grid. This negates the need for coarse grid storage allocation resulting in easy programmability. The algorithm differs from unigrid in that it mimics multigrid V(0, v) cycles which effectively overcomes the inefficiency of the unigrid technique. The single-level algorithm is therefore both easy to program and efficient. It is illustrated by two numerical examples and compared with unigrid and conventional multigrid.     

Fast and Robust Sixth Order Multigrid Computation for 3D Convection Diffusion Equation

We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.     

A new type of full multigrid method for the elasticity eigenvalue problem

This paper introduces a new type of full multigrid method for the elasticity eigenvalue problem. The main idea is to avoid solving large scale elasticity eigenvalue problem directly by transforming the solution of the elasticity eigenvalue problem into a series of solutions of linear boundary value problems defined on a multilevel finite element space sequence and some small scale elasticity eigenvalue problems defined on the coarsest correction space. The involved linear boundary value problems will be solved by performing some multigrid iterations. Besides, some efficient techniques such as parallel computing and adaptive mesh refinement can also be absorbed in our algorithm. The efficiency and validity of the multigrid methods are verified by several numerical experiments.     

Acceleration of two-grid stabilized mixed finite element method for the Stokes eigenvalue problem

This paper provides an accelerated two-grid stabilized mixed finite element scheme for the Stokes eigenvalue problem based on the pressure projection. With the scheme, the solution of the Stokes eigenvalue problem on a fine grid is reduced to the solution of the Stokes eigenvalue problem on a much coarser grid and the solution of a linear algebraic system on the fine grid. By solving a slightly different linear problem on the fine grid, the new algorithm significantly improves the theoretical error estimate which allows a much coarser mesh to achieve the same asymptotic convergence rate. Finally, numerical experiments are shown to verify the high efficiency and the theoretical results of the new method.     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Sparse-grid finite-volume multigrid for 3D-problems

We introduce a multigrid algorithm for the solution of a second order elliptic equation in three dimensions. For the approximation of the solution we use a partially ordered hierarchy of finite-volume discretisations. We show that there is a relation with semicoarsening and approximation by more-dimensional Haar wavelets. By taking a proper subset of all possible meshes in the hierarchy, a sparse grid finite-volume discretisation can be constructed.The multigrid algorithm consists of a simple damped point-Jacobi relaxation as the smoothing procedure, while the coarse grid correction is made by interpolation from several coarser grid levels.The combination of sparse grids and multigrid with semi-coarsening leads to a relatively small number of degrees of freedom,N, to obtain an accurate approximation, together with anO(N) method for the solution. The algorithm is symmetric with respect to the three coordinate directions and it is fit for combination with adaptive techniques.To analyse the convergence of the multigrid algorithm we develop the necessary Fourier analysis tools. All techniques, designed for 3D-problems, can also be applied for the 2D case, and — for simplicity — we apply the tools to study the convergence behaviour for the anisotropic Poisson equation for this 2D case.     

The Logarithmic finite element method in a multigrid setting

The Logarithmic finite element (“LogFE”) method is a novel finite element approach for solving boundary-value problems proposed in [1]. In contrast to the standard Ritz-Galerkin formulation, the shape functions are given on the logarithmic space of the deformation function, which is obtained by the exponentiation of the linear combination of the shape functions given by the degrees of freedom. Unlike many existing multigrid formulations, the LogFE method allows for a very smooth interpolation between nodal values on the coarse grid. It can thus avoid problems with regard to locking and convergence that appear in multigrid applications using only linear interpolation, especially for larger corsening factors. We illustrate the use of the LogFE method as a coarse grid algorithm, in conjunction with an atomistic finite element method on the fine grid, for calculating the mechanical response of super carbon nanotubes. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Two-Grid Finite Element Method with Crank-Nicolson Fully Discrete Scheme for the Time-Dependent Schrödinger Equation

In this paper, we study the Crank-Nicolson Galerkin finite element method and construct a two-grid algorithm for the general two-dimensional time-dependent Schrödinger equation. Firstly, we analyze the superconvergence error estimate of the finite element solution in $H^1$ norm by use of the elliptic projection operator. Secondly, we propose a fully discrete two-grid finite element algorithm with Crank-Nicolson scheme in time. With this method, the solution of the Schrödinger equation on a fine grid is reduced to the solution of original problem on a much coarser grid together with the solution of two Poisson equations on the fine grid. Finally, we also derive error estimates of the two-grid finite element solution with the exact solution in $H^1$ norm. It is shown that the solution of two-grid algorithm can achieve asymptotically optimal accuracy as long as mesh sizes satisfy $H = \mathcal{O}(h^{\frac{1}{2}})$.     

外推瀑布多网格法(EXCMG)——-大规模求解椭圆问题的新算法

基于有限元的渐近展开式,导出了新的外推公式,它们更精确地逼近密网上的有限元解(而不是微分方程的解).提出了新的外推瀑布型多网格法(EXCMG),采用新外推公式及其二次插值提供密网上的好初值.数值实验表明,新方法有很高的精度和效率.最后在PC机上求解了大规模二维椭圆问题.     

A new two grid variational multiscale method for steady‐state natural convection problem

A two‐grid variational multiscale method based on two local Gauss integrations for solving the stationary natural convection problem is presented in this article. A significant feature of the method is that we solve the natural convection problem on a coarse mesh using finite element variational multiscale method based on two local Gauss integrations firstly, and then find a fine grid solution by solving a linearized problem on a fine grid. In the computation, we introduce two local Gauss integrations as a stabilizing term to replace the projection operator without adding other variables. The stability estimates and convergence analysis of the new method are derived. Ample numerical experiments are performed to validate the theoretical predictions and demonstrate the efficiency of the new method. Copyright © 2016 John Wiley & Sons, Ltd.     

Multigrid for second‐order ADN elliptic systems

This paper theoretically examines a multigrid strategy for solving systems of elliptic partial differential equations (PDEs) introduced in the work of Lee. Unlike most multigrid solvers that are constructed directly from the whole system operator, this strategy builds the solver using a factorization of the system operator. This factorization is composed of an algebraic coupling term and a diagonal (decoupled) differential operator. Exploiting the factorization, this approach can produce decoupled systems on the coarse levels. The corresponding coarse‐grid operators are in fact the Galerkin variational coarsening of the diagonal differential operator. Thus, rather than performing delicate coarse‐grid selection and interpolation weight procedures on the original strongly coupled system as often done, these procedures are isolated to the diagonal differential operator. To establish the theoretical results, however, we assume that these systems of PDEs are elliptic in the Agmon–Douglis–Nirenberg (ADN) sense and apply the factorization and multigrid only to the principal part of the system of PDEs. Two‐grid error bounds are established for the iteration applied to the complete system of PDEs. Numerical results are presented to illustrate the effectiveness of this strategy and to expose factors that affect the convergence of the methods derived from this strategy.     

Some numerical experiments with multigrid methods on Shishkin meshes

Piecewise uniform meshes introduced by Shishkin, are a very useful tool to construct robust and efficient numerical methods to approximate the solution of singularly perturbed problems. For small values of the diffusion coefficient, the step size ratios, in this kind of grids, can be very large. In this case, standard multigrid methods are not convergent. To avoid this troublesome, in this paper we propose a modified multigrid algorithm, which works fine on Shishkin meshes. We show some numerical experiments confirming that the proposed multigrid method is convergent, and it has similar properties that standard multigrid for classical elliptic problems.     

Monotone multigrid methods for elliptic variational inequalities II

Summary. We derive globally convergent multigrid methods for discrete elliptic variational inequalities of the second kind as obtained from the approximation of related continuous problems by piecewise linear finite elements. The coarse grid corrections are computed from certain obstacle problems. The actual constraints are fixed by the preceding nonlinear fine grid smoothing. This new approach allows the implementation as a classical V-cycle and preserves the usual multigrid efficiency. We give estimates for the asymptotic convergence rates. The numerical results indicate a significant improvement as compared with previous multigrid approaches. Received March 26, 1994 / Revised version received September 22, 1994     

Analysis of linear and quadratic simplicial finite volume methods for elliptic equations

This paper is devoted to analysis of some convergent properties of both linear and quadratic simplicial finite volume methods (FVMs) for elliptic equations. For linear FVM on domains in any dimensions, the inf-sup condition is established in a simple fashion. It is also proved that the solution of a linear FVM is super-close to that of a relevant finite element method (FEM). As a result, some a posterior error estimates and also algebraic solvers for FEM are extended to FVM. For quadratic FVM on domains in two dimensions, the inf-sup condition is established under some weak condition on the grid.