Algebraic multigrid,mixed‐order interpolation,and incompressible fluid flow

This paper presents the results of numerical experiments on the use of equal‐order and mixed‐order interpolations in algebraic multigrid (AMG) solvers for the fully coupled equations of incompressible fluid flow. Several standard test problems are addressed for Reynolds numbers spanning the laminar range. The range of unstructured meshes spans over two orders of problem size (over one order of mesh bandwidth). Deficiencies in performance are identified for AMG based on equal‐order interpolations (both zero‐order and first‐order). They take the form of poor, fragile, mesh‐dependent convergence rates. The evidence suggests that a degraded representation of the inter‐field coupling in the coarse‐grid approximation is the cause. Mixed‐order interpolation (first‐order for the vectors, zero‐order for the scalars) is shown to address these deficiencies. Convergence is then robust, independent of the number of coarse grids and (almost) of the mesh bandwidth. The AMG algorithms used are reviewed. Copyright © 2009 John Wiley & Sons, Ltd.     

Comparison of multigrid algorithms for high‐order continuous finite element discretizations

We present a comparison of different multigrid approaches for the solution of systems arising from high‐order continuous finite element discretizations of elliptic partial differential equations on complex geometries. We consider the pointwise Jacobi, the Chebyshev‐accelerated Jacobi, and the symmetric successive over‐relaxation smoothers, as well as elementwise block Jacobi smoothing. Three approaches for the multigrid hierarchy are compared: (1) high‐order h‐multigrid, which uses high‐order interpolation and restriction between geometrically coarsened meshes; (2) p‐multigrid, in which the polynomial order is reduced while the mesh remains unchanged, and the interpolation and restriction incorporate the different‐order basis functions; and (3) a first‐order approximation multigrid preconditioner constructed using the nodes of the high‐order discretization. This latter approach is often combined with algebraic multigrid for the low‐order operator and is attractive for high‐order discretizations on unstructured meshes, where geometric coarsening is difficult. Based on a simple performance model, we compare the computational cost of the different approaches. Using scalar test problems in two and three dimensions with constant and varying coefficients, we compare the performance of the different multigrid approaches for polynomial orders up to 16. Overall, both h‐multigrid and p‐multigrid work well; the first‐order approximation is less efficient. For constant coefficients, all smoothers work well. For variable coefficients, Chebyshev and symmetric successive over‐relaxation smoothing outperform Jacobi smoothing. While all of the tested methods converge in a mesh‐independent number of iterations, none of them behaves completely independent of the polynomial order. When multigrid is used as a preconditioner in a Krylov method, the iteration number decreases significantly compared with using multigrid as a solver. Copyright © 2015 John Wiley & Sons, Ltd.     

Optimal uniform error estimates for moving least‐squares collocation with application to option pricing under jump‐diffusion processes

In this study, we derive optimal uniform error bounds for moving least‐squares (MLS) mesh‐free point collocation (also called finite point method) when applied to solve second‐order elliptic partial integro‐differential equations (PIDEs). In the special case of elliptic partial differential equations (PDEs), we show that our estimate improves the results of Cheng and Cheng (Appl. Numer. Math. 58 (2008), no. 6, 884–898) both in terms of the used error norm (here the uniform norm and there the discrete vector norm) and the obtained order of convergence. We then present optimal convergence rate estimates for second‐order elliptic PIDEs. We proceed by some numerical experiments dealing with elliptic PDEs that confirm the obtained theoretical results. The article concludes with numerical approximation of the linear parabolic PIDE arising from European option pricing problem under Merton's and Kou's jump‐diffusion models. The presented computational results (including the computation of option Greeks) and comparisons with other competing approaches suggest that the MLS collocation scheme is an efficient and reliable numerical method to solve elliptic and parabolic PIDEs arising from applied areas such as financial engineering.     

An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions

The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Stability and convergence of the mark and cell finite difference scheme for Darcy‐Stokes‐Brinkman equations on non‐uniform grids

In this paper, we consider the mark and cell (MAC) method for Darcy‐Stokes‐Brinkman equations and analyze the stability and convergence of the method on nonuniform grids. Firstly, to obtain the stability for both velocity and pressure, we establish the discrete inf‐sup condition. Then we introduce an auxiliary function depending on the velocity and discretizing parameters to analyze the super‐convergence. Finally, we obtain the second‐order convergence in L2 norm for both velocity and pressure for the MAC scheme, when the perturbation parameter ? is not approaching 0. We also obtain the second‐order convergence for some terms of ∥·∥_? norm of the velocity, and the other terms of ∥·∥_? norm are second‐order convergence on uniform grid. Numerical experiments are carried out to verify the theoretical results.     

A C0 interior penalty method for a singularly‐perturbed fourth‐order elliptic problem on a layer‐adapted mesh

We analyze the convergence of a continuous interior penalty (CIP) method for a singularly perturbed fourth‐order elliptic problem on a layer‐adapted mesh. On this anisotropic mesh, we prove under reasonable assumptions uniform convergence of almost order k ? 1 for finite elements of degree k ≥ 2. This result is of better order than the known robust result on standard meshes. A by‐product of our analysis is an analytic lower bound for the penalty of the symmetric CIP method. Finally, our convergence result is verified numerically. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 838–861, 2014     

Analysis of a two‐level method for anisotropic diffusion equations on aligned and nonaligned grids

This paper is on the convergence analysis for two‐grid and multigrid methods for linear systems arising from conforming linear finite element discretization of the second‐order elliptic equations with anisotropic diffusion. The multigrid algorithm with a line smoother is known to behave well when the discretization grid is aligned with the anisotropic direction; however, this is not the case with a nonaligned grid. The analysis in this paper is mainly focused on two‐level algorithms. For aligned grids, a lower bound is given for a pointwise smoother, and this bound shows a deterioration in the convergence rate, whereas for ‘maximally’ nonaligned grids (with no edges in the triangulation parallel to the direction of the anisotropy), the pointwise smoother results in a robust convergence. With a specially designed block smoother, we show that, for both aligned and nonaligned grids, the convergence is uniform with respect to the anisotropy ratio and the mesh size in the energy norm. The analysis is complemented by numerical experiments that confirm the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.     

A geometric‐based algebraic multigrid method for higher‐order finite element equations in two‐dimensional linear elasticity

In this paper, we will discuss the geometric‐based algebraic multigrid (AMG) method for two‐dimensional linear elasticity problems discretized using quadratic and cubic elements. First, a two‐level method is proposed by analyzing the relationship between the linear finite element space and higher‐order finite element space. And then a geometric‐based AMG method is obtained with the existing solver used as a solver on the first coarse level. The resulting AMG method is applied to some typical elasticity problems including the plane strain problem with jumps in Young's modulus. The results of various numerical experiments show that the proposed AMG method is much more robust and efficient than a classical AMG solver that is applied directly to the high‐order systems alone. Moreover, we present the corresponding theoretical analysis for the convergence of the proposed AMG algorithms. These theoretical results are also confirmed by some numerical tests. Copyright © 2008 John Wiley & Sons, Ltd.     

CLC in AMG solvers for saddle‐point problems

An algebraic multigrid (AMG) solution method for saddle‐point problems is described. The indefinite nature of the saddle‐point matrix makes it unsuitable for the simple smoothing methods normally used in AMG. Moreover, even if presented in a stabilised form, as is done here, poorly conditioned matrices will be generated when constructing the coarse‐grid approximation. This is because, with each successive coarsening step, the off‐diagonal matrix blocks (of interfield coupling) reduce in size more slowly than the diagonal blocks (of intrafield coupling). Stabilised smoothing operators are therefore considered. The first is based on an incomplete decomposition of the complete system matrix into the product of lower‐triangular ( L ) and upper‐triangular ( U ) matrices, an ILU factorisation. The second is based on an exact block decomposition of an incomplete (simplified) system matrix into lower and upper block‐triangular matrices, a BILU factorisation. However, the degree of stabilisation thus established in the smoothing operators does not guarantee an efficient smoothing at all grid levels. There can still be inefficiency on the least‐stable coarser grids. The breakdown in efficiency begins at a grid level where the ratio of the inter‐ to intrafield coupling strengths exceeds a critical ratio. Provision is thus made for a further conditioning of coarse‐grid operators, a coarse‐level conditioning (CLC). This is another block‐LU factorisation that is only applied at and beyond the critical grid level. It is not applied directly to the operator for any chosen level but to its fine‐grid progenitor. Thus, while ILU and BILU use postcoarsening‐step factorisations, CLC uses precoarsening‐step factorisations. With CLC so deployed, ILU and BILU become efficient at all grid levels, resulting in an AMG convergence that is independent of the total number of grids.     

A robust algebraic multilevel preconditioner for non‐symmetric M‐matrices

Stable finite difference approximations of convection‐diffusion equations lead to large sparse linear systems of equations whose coefficient matrix is an M‐matrix, which is highly non‐symmetric when the convection dominates. For an efficient iterative solution of such systems, it is proposed to consider in the non‐symmetric case an algebraic multilevel preconditioning method formerly proposed for pure diffusion problems, and for which theoretical results prove grid independent convergence in this context. These results are supplemented here by a Fourier analysis that applies to constant coefficient problems with periodic boundary conditions whenever using an ‘idealized’ version of the two‐level preconditioner. Within this setting, it is proved that any eigenvalue λ of the preconditioned system satisfies for some real constant c such that . This result holds independently of the grid size and uniformly with respect to the ratio between convection and diffusion. Extensive numerical experiments are conducted to assess the convergence of practical two‐ and multi‐level schemes. These experiments, which include problems with highly variable and rotating convective flow, indicate that the convergence is grid independent. It deteriorates moderately as the convection becomes increasingly dominating, but the convergence factor remains uniformly bounded. This conclusion is supported for both uniform and some non‐uniform (stretched) grids. Copyright © 2000 John Wiley & Sons, Ltd.     

Discontinuous Galerkin method for the coupled Stokes‐Biot model

In this paper, a semi‐discrete scheme and a fully discrete scheme of the Stokes‐Biot model are proposed, and we analyze the semi‐discrete scheme in detail. First of all, we prove the existence and uniqueness of the semi‐discrete scheme, and a‐priori error estimates are derived. Then, we present the same conclusions for the fully discrete scheme. Finally, under both matching and non‐matching meshes some numerical tests are given to validate the analysis of convergence, which well support the theoretical results.     

Linear system solution by null‐space approximation and projection (SNAP)

Solutions of large sparse linear systems of equations are usually obtained iteratively by constructing a smaller dimensional subspace such as a Krylov subspace. The convergence of these methods is sometimes hampered by the presence of small eigenvalues, in which case, some form of deflation can help improve convergence. The method presented in this paper enables the solution to be approximated by focusing the attention directly on the ‘small’ eigenspace (‘singular vector’ space). It is based on embedding the solution of the linear system within the eigenvalue problem (singular value problem) in order to facilitate the direct use of methods such as implicitly restarted Arnoldi or Jacobi–Davidson for the linear system solution. The proposed method, called ‘solution by null‐space approximation and projection’ (SNAP), differs from other similar approaches in that it converts the non‐homogeneous system into a homogeneous one by constructing an annihilator of the right‐hand side. The solution then lies in the null space of the resulting matrix. We examine the construction of a sequence of approximate null spaces using a Jacobi–Davidson style singular value decomposition method, called restarted SNAP‐JD, from which an approximate solution can be obtained. Relevant theory is discussed and the method is illustrated by numerical examples where SNAP is compared with both GMRES and GMRES‐IR. Copyright © 2006 John Wiley & Sons, Ltd.     

A two‐grid stabilized mixed finite element method for Darcy‐Forchheimer model

A two‐grid stabilized mixed finite element method based on pressure projection stabilization is proposed for the two‐dimensional Darcy‐Forchheimer model. We use the derivative of a smooth function, , to approximate the derivative of in constructing the two‐grid algorithm. The two‐grid method consists of solving a small nonlinear system on the coarse mesh and then solving a linear system on the fine mesh. There are a substantial reduction in computational cost. We prove the existence and uniqueness of solution of the discrete schemes on the coarse grid and the fine grid and obtain error estimates for the two‐grid algorithm. Finally, some numerical experiments are carried out to verify the accuracy and efficiency of the method.     

The discrete duality finite volume method for a class of quasi‐Newtonian Stokes flows

In this paper, we propose a discrete duality finite volume (DDFV) scheme for the incompressible quasi‐Newtonian Stokes equation. The DDFV method is based on the use of discrete differential operators which satisfy some duality properties analogous to their continuous counterparts in a discrete sense. The DDFV method has a great ability to handle general geometries and meshes. In addition, every component of the velocity gradient can be reconstructed directly, which makes it suitable to deal with the nonlinear terms in the quasi‐Newtonian Stokes equation. We prove that the proposed DDFV scheme is uniquely solvable and of first‐order convergence in the discrete L²‐norms for the velocity, the strain rate tensor, and the pressure, respectively. Ample numerical tests are provided to highlight the performance of the proposed DDFV scheme and to validate the theoretical error analysis, in particular on locally refined nonconforming and polygonal meshes.     

Efficient approximation algorithm for the Schrödinger–Possion system

In this article, we study an efficient approximation algorithm for the Schrödinger–Possion system arising in the resonant tunneling diode (RTD) structure. By following the classical Gummel iterative procedure, we first decouple this nonlinear system and prove the convergence of the iteration method. Then via introducing a novel spatial discrete method, we solve efficiently the decoupled Schrödinger and Possion equations with discontinuous coefficients on no‐uniform meshes at each iterative step, respectively. Compared with the traditional ones, the algorithm considered here not only has a less restriction on the discrete mesh, but also is more accurate. Finally, some numerical experiments are shown to confirm the efficiency of the proposed algorithm.     

Two grid finite element discretization method for semi‐linear hyperbolic integro‐differential equations

In this paper, we will investigate a two grid finite element discretization method for the semi‐linear hyperbolic integro‐differential equations by piecewise continuous finite element method. In order to deal with the semi‐linearity of the model, we use the two grid technique and derive that once the coarse and fine mesh sizes H, h satisfy the relation h = H² for the two‐step two grid discretization method, the two grid method achieves the same convergence accuracy as the ordinary finite element method. Both theoretical analysis and numerical experiments are given to verify the results.     

Algebraic interface‐based coarsening AMG preconditioner for multi‐scale sparse matrices with applications to radiation hydrodynamics computation

Coarsening is a crucial component of algebraic multigrid (AMG) methods for iteratively solving sparse linear systems arising from scientific and engineering applications. Its application largely determines the complexity of the AMG iteration operator. Usually, high operator complexities lead to fast convergence of the AMG method; however, they require additional memory and as such do not scale as well in parallel computation. In contrast, although low operator complexities improve parallel scalability, they often lead to deterioration in convergence. This study introduces a new type of coarsening strategy called algebraic interface‐based coarsening that yields a better balance between convergence and complexity for a class of multi‐scale sparse matrices. Numerical results for various model‐type problems and a radiation hydrodynamics practical application are provided to show the effectiveness of the proposed AMG solver.     

Stochastic homogenization of Hamilton‐Jacobi‐Bellman equations

We study the homogenization of some Hamilton‐Jacobi‐Bellman equations with a vanishing second‐order term in a stationary ergodic random medium under the hyperbolic scaling of time and space. Imposing certain convexity, growth, and regularity assumptions on the Hamiltonian, we show the locally uniform convergence of solutions of such equations to the solution of a deterministic “effective” first‐order Hamilton‐Jacobi equation. The effective Hamiltonian is obtained from the original stochastic Hamiltonian by a minimax formula. Our homogenization results have a large‐deviations interpretation for a diffusion in a random environment. © 2005 Wiley Periodicals, Inc.     

Quasi‐optimal preconditioners for finite element approximations of diffusion dominated convection–diffusion equations on (nearly) equilateral triangle meshes

The paper is devoted to the spectral analysis of effective preconditioners for linear systems obtained via a finite element approximation to diffusion‐dominated convection–diffusion equations. We consider a model setting in which the structured finite element partition is made by equilateral triangles. Under such assumptions, if the problem is coercive and the diffusive and convective coefficients are regular enough, then the proposed preconditioned matrix sequences exhibit a strong eigenvalue clustering at unity, the preconditioning matrix sequence and the original matrix sequence are spectrally equivalent, and under the constant coefficients assumption, the eigenvector matrices have a mild conditioning. The obtained results allow to prove the conjugate gradient optimality and the generalized minimal residual quasi‐optimality in the case of structured uniform meshes. The interest of such a study relies on the observation that automatic grid generators tend to construct equilateral triangles when the mesh is fine enough. Numerical tests, both on the model setting and in the non‐structured case, show the effectiveness of the proposal and the correctness of the theoretical findings. Copyright © 2014 John Wiley & Sons, Ltd.     

A discrete duality finite volume discretization of the vorticity‐velocity‐pressure stokes problem on almost arbitrary two‐dimensional grids

We present an application of the discrete duality finite volume method to the numerical approximation of the vorticity‐velocity‐pressure formulation of the two‐dimensional Stokes equations, associated to various nonstandard boundary conditions. The finite volume method is based on the use of discrete differential operators obeying some discrete duality principles. The scheme may be seen as an extension of the classical Marker and Cell scheme to almost arbitrary meshes, thanks to an appropriate choice of degrees of freedom. The efficiency of the scheme is illustrated by numerical examples over unstructured triangular and locally refined nonconforming meshes, which confirm the theoretical convergence analysis led in the article. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1–30, 2015