Algebraic multigrid and 4th‐order discrete‐difference equations of incompressible fluid flow

This paper investigates the effectiveness of two different Algebraic Multigrid (AMG) approaches to the solution of 4th‐order discrete‐difference equations for incompressible fluid flow (in this case for a discrete, scalar, stream‐function field). One is based on a classical, algebraic multigrid, method (C‐AMG) the other is based on a smoothed‐aggregation method for 4th‐order problems (SA‐AMG). In the C‐AMG case, the inter‐grid transfer operators are enhanced using Jacobi relaxation. In the SA‐AMG case, they are improved using a constrained energy optimization of the coarse‐grid basis functions. Both approaches are shown to be effective for discretizations based on uniform, structured and unstructured, meshes. They both give good convergence factors that are largely independent of the mesh size/bandwidth. The SA‐AMG approach, however, is more costly both in storage and operations. The Jacobi‐relaxed C‐AMG approach is faster, by a factor of between 2 and 4 for two‐dimensional problems, even though its reduction factors are inferior to those of SA‐AMG. For non‐uniform meshes, the accuracy of this particular discretization degrades from 2nd to 1st order and the convergence factors for both methods then become mesh dependent. Copyright © 2009 John Wiley & Sons, Ltd.     

An algebraic multigrid method for Q2−Q1 mixed discretizations of the Navier–Stokes equations

Algebraic multigrid (AMG) preconditioners are considered for discretized systems of partial differential equations (PDEs) where unknowns associated with different physical quantities are not necessarily colocated at mesh points. Specifically, we investigate a Q ₂? Q ₁ mixed finite element discretization of the incompressible Navier–Stokes equations where the number of velocity nodes is much greater than the number of pressure nodes. Consequently, some velocity degrees of freedom (DOFs) are defined at spatial locations where there are no corresponding pressure DOFs. Thus, AMG approaches leveraging this colocated structure are not applicable. This paper instead proposes an automatic AMG coarsening that mimics certain pressure/velocity DOF relationships of the Q ₂? Q ₁ discretization. The main idea is to first automatically define coarse pressures in a somewhat standard AMG fashion and then to carefully (but automatically) choose coarse velocity unknowns so that the spatial location relationship between pressure and velocity DOFs resembles that on the finest grid. To define coefficients within the intergrid transfers, an energy minimization AMG (EMIN‐AMG) is utilized. EMIN‐AMG is not tied to specific coarsening schemes and grid transfer sparsity patterns, and so it is applicable to the proposed coarsening. Numerical results highlighting solver performance are given on Stokes and incompressible Navier–Stokes problems.     

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.     

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.     

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.     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.     

On some versions of the element agglomeration AMGe method

The present paper deals with element‐based algebraic multigrid (AMGe) methods that target linear systems of equations coming from finite element discretizations of elliptic partial differential equations. The individual element information (element matrices and element topology) is the main input to construct the AMG hierarchy. We study a number of variants of the spectral agglomerate AMGe method. The core of the algorithms relies on element agglomeration utilizing the element topology (built recursively from fine to coarse levels). The actual selection of the coarse degrees of freedom is based on solving a large number of local eigenvalue problems. Additionally, we investigate strategies for adaptive AMG as well as multigrid cycles that are more expensive than the V‐cycle utilizing simple interpolation matrices and nested conjugate gradient (CG)‐based recursive calls between the levels. The presented algorithms are illustrated with an extensive set of experiments based on a matlab implementation of the methods. Copyright © 2008 John Wiley & Sons, Ltd.     

A two‐level finite element method for the stationary Navier‐Stokes equations based on a stabilized local projection

In this article, we propose a two‐level finite element method to analyze the approximate solutions of the stationary Navier‐Stokes equations based on a stabilized local projection. The local projection allows to circumvent the Babuska‐Brezzi condition by using equal‐order finite element pairs. The local projection can be used to stabilize high equal‐order finite element pairs. The proposed method combines the local projection stabilization method and the two‐level method under the assumption of the uniqueness condition. The two‐level method consists of solving a nonlinear equation on the coarse mesh and solving a linear equation on fine mesh. The nonlinear equation is solved by the one‐step Newtonian iteration method. In the rest of this article, we show the error analysis of the lowest equal‐order finite element pair and provide convergence rate of approximate solutions. Furthermore, the numerical illustrations coincide with the theoretical analysis expectations. From the view of computational time, the results show that the two‐level method is effective to solve the stationary Navier‐Stokes equations. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

An accurate solution procedure for fluid flow with natural convection

We consider the Boussinesq model of buoyancy driven fluid flows. This nonlinear system is solved numerically using a two level finite element method. On the first level, a nonlinear system is solved on a very coarse mesh. Thereafter, a linear system is solved on a fine mesh.

In a standard approach, one might obtain the numerical solution from a discretization of the original, nonlinear system using the same fine mesh.

Both solutions are of equal order of accuracy if the mesh widths are properly balanced. Therefore the two level method is very efficient.     

Analysis of algebraic multigrid parameters for two-dimensional steady-state heat diffusion equations

In this work, it is provided a comparison for the algebraic multigrid (AMG) and the geometric multigrid (GMG) parameters, for Laplace and Poisson two-dimensional equations in square and triangular grids. The analyzed parameters are the number of: inner iterations in the solver, grids and unknowns. For the AMG, the effects of the grid reduction factor and the strong dependence factor in the coarse grid on the necessary CPU time are studied. For square grids the finite difference method is used, and for the triangular grids, the finite volume one. The results are obtained with the use of an adapted AMG1R6 code of Ruge and Stüben. For the AMG the following components are used: standard coarsening, standard interpolation, correction scheme (CS), lexicographic Gauss–Seidel and V-cycle. Comparative studies among the CPU time of the GMG, AMG and singlegrid are made. It was verified that: (1) the optimum inner iterations is independent of the multigrid, however it is dependent on the grid; (2) the optimum number of grids is the maximum number; (3) AMG was shown to be sensitive to both the variation of the grid reduction factor and the strong dependence factor in the coarse grid; (4) in square grids, the GMG CPU time is 20% of the AMG one.     

Superconvergence of a stabilized finite element approximation for the Stokes equations using a local coarse mesh L2 projection

This article first recalls the results of a stabilized finite element method based on a local Gauss integration method for the stationary Stokes equations approximated by low equal‐order elements that do not satisfy the inf‐sup condition. Then, we derive general superconvergence results for this stabilized method by using a local coarse mesh L² projection. These supervergence results have three prominent features. First, they are based on a multiscale method defined for any quasi‐uniform mesh. Second, they are derived on the basis of a large sparse, symmetric positive‐definite system of linear equations for the solution of the stationary Stokes problem. Third, the finite elements used fail to satisfy the inf‐sup condition. This article combines the merits of the new stabilized method with that of the L² projection method. This projection method is of practical importance in scientific computation. Finally, a series of numerical experiments are presented to check the theoretical results obtained. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 28: 115‐126, 2012     

An efficient hierarchical preconditioner for quadratic discretizations of finite element problems

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large‐scale problems. In this paper, we have developed an efficient iterative solver for solving large‐scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection–diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd.     

Two‐level discretization of the Navier‐Stokes equations with r‐Laplacian subgridscale viscosity

The r‐Laplacian has played an important role in the development of computationally efficient models for applications, such as numerical simulation of turbulent flows. In this article, we examine two‐level finite element approximation schemes applied to the Navier‐Stokes equations with r‐Laplacian subgridscale viscosity, where r is the order of the power‐law artificial viscosity term. In the two‐level algorithm, the solution to the fully nonlinear coarse mesh problem is utilized in a single‐step linear fine mesh problem. When modeling parameters are chosen appropriately, the error in the two‐level algorithm is comparable to the error in solving the fully nonlinear problem on the fine mesh. We provide rigorous numerical analysis of the two‐level approximation scheme and derive scalings which vary based on the coefficient r, coarse mesh size H, fine mesh size h, and filter radius δ. We also investigate the two‐level algorithm in several computational settings, including the 3D numerical simulation of flow past a backward‐facing step at Reynolds number Re = 5100. In all numerical tests, the two‐level algorithm was proven to achieve the same order of accuracy as the standard one‐level algorithm, at a fraction of the computational cost. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

A coarse–fine‐mesh stabilization for an alternating Schwarz domain decomposition method

Domain decomposition methods can be solved in various ways. In this paper, domain decomposition in strips is used. It is demonstrated that a special version of the Schwarz alternating iteration method coupled with coarse–fine‐mesh stabilization leads to a very efficient solver, which is easy to implement and has a behavior nearly independent of mesh and problem parameters. The novelty of the method is the use of alternating iterations between odd‐ and even‐numbered subdomains and the replacement of the commonly used coarse‐mesh stabilization method with coarse–fine‐mesh stabilization.     

Domain decomposition preconditioners for multiscale problems in linear elasticity

We analyze two‐level overlapping Schwarz domain decomposition methods for vector‐valued piecewise linear finite element discretizations of the PDE system of linear elasticity. The focus of our study lies in the application to compressible, particle‐reinforced composites in 3D with large jumps in their material coefficients. We present coefficient‐explicit bounds for the condition number of the two‐level additive Schwarz preconditioned linear system. Thereby, we do not require that the coefficients are resolved by the coarse mesh. The bounds show a dependence of the condition number on the energy of the coarse basis functions, the coarse mesh, and the overlap parameters, as well as the coefficient variation. Similar estimates have been developed for scalar elliptic PDEs by Graham et al. 1 The coarse spaces to which they apply here are assumed to contain the rigid body modes and can be considered as generalizations of the space of piecewise linear vector‐valued functions on a coarse triangulation. The developed estimates provide a concept for the construction of coarse spaces, which can lead to preconditioners that are robust with respect to high contrasts in Young's modulus and the Poisson ratio of the underlying composite. To confirm the sharpness of the theoretical findings, we present numerical results in 3D using vector‐valued linear, multiscale finite element and energy‐minimizing coarse spaces. The theory is not restricted to the isotropic (Lamé) case, extends to the full‐tensor case, and allows applications to multiphase materials with anisotropic constituents in two and three spatial dimensions. However, the bounds will depend on the ratio of largest to smallest eigenvalue of the elasticity tensor.     

A homogeneous limit methodology and refinements of computationally efficient zigzag theory for homogeneous,laminated composite,and sandwich plates

The Refined Zigzag Theory (RZT) for homogeneous, laminated composite, and sandwich plates is revisited to offer a fresh insight into its fundamental assumptions and practical possibilities. The theory is introduced from a multiscale formalism starting with the inplane displacement field expressed as a superposition of coarse and fine contributions. The coarse displacement field is that of first‐order shear‐deformation theory, whereas the fine displacement field has a piecewise‐linear zigzag distribution through the thickness. The resulting kinematic field provides a more realistic representation of the deformation states of transverse‐shear‐flexible plates than other similar theories. The condition of limiting homogeneity of transverse‐shear properties is proposed and yields four distinct variants of zigzag functions. Analytic solutions for highly heterogeneous sandwich plates undergoing elastostatic deformations are used to identify the best‐performing zigzag functions. Unlike previously used methods, which often result in anomalous conditions and nonphysical solutions, the present theory does not rely on transverse‐shear‐stress equilibrium constraints. For all material systems, there are no requirements for use of transverse‐shear correction factors to yield accurate results. To model homogeneous plates with the full power of zigzag kinematics, infinitesimally small perturbations in the transverse shear properties are derived, thus enabling highly accurate predictions of homogeneous‐plate behavior without the use of shear correction factors. The RZT predictive capabilities to model highly heterogeneous sandwich plates are critically assessed, demonstrating its superior efficiency, accuracy, and a wide range of applicability. This theory, which is derived from the virtual work principle, is well‐suited for developing computationally efficient, C⁰ a continuous function of (x₁,x₂) coordinates whose first‐order derivatives are discontinuous along finite element interfaces and is thus appropriate for the analysis and design of high‐performance load‐bearing aerospace structures. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Robust iterative methods for elliptic problems with highly varying coefficients in thin substructures

Summary. In this paper we introduce a class of robust multilevel interface solvers for two-dimensional finite element discrete elliptic problems with highly varying coefficients corresponding to geometric decompositions by a tensor product of strongly non-uniform meshes. The global iterations convergence rate is shown to be of the order with respect to the number of degrees of freedom on the single subdomain boundaries, uniformly upon the coarse and fine mesh sizes, jumps in the coefficients and aspect ratios of substructures. As the first approach, we adapt the frequency filtering techniques [28] to construct robust smoothers on the highly non-uniform coarse grid. As an alternative, a multilevel averaging procedure for successive coarse grid correction is proposed and analyzed. The resultant multilevel coarse grid preconditioner is shown to have (in a two level case) the condition number independent of the coarse mesh grading and jumps in the coefficients related to the coarsest refinement level. The proposed technique exhibited high serial and parallel performance in the skin diffusion processes modelling [20] where the high dimensional coarse mesh problem inherits a strong geometrical and coefficients anisotropy. The approach may be also applied to magnetostatics problems as well as in some composite materials simulation. Received December 27, 1994     

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.     

内网点连通剖分下网线的编号

本文讨论内网点连通剖分下网线的编号方法，以使协调方程的带宽尽量的小．这样对解协调方程，进而确定给定剖分下的作条函数空间是有意义的．文中给出一个随机选取的剖分的网线的一个具体编号．对矩形剖分、Ｉ型与Ⅱ型三角剖分，给出了它们的带宽分析．     

Adaptive reduction‐based AMG

With the ubiquity of large‐scale computing resources has come significant attention to practical details of fast algorithms for the numerical solution of partial differential equations. Included in this group are the class of multigrid and algebraic multigrid algorithms that are effective solvers for many of the large matrix problems arising from the discretization of elliptic operators. Algebraic multigrid (AMG) is especially effective for many problems with discontinuous coefficients, discretized on unstructured grids, or over complex geometries. While much effort has been invested in improving the practical performance of AMG, little theoretical understanding of this performance has emerged. This paper presents a two‐level convergence theory for a reduction‐based variant of AMG, called AMGr, which is particularly appropriate for linear systems that have M‐matrix‐like properties. For situations where less is known about the problem matrix, an adaptive version of AMGr that automatically determines the form of the reduction needed by the AMGr process is proposed. The adaptive cycle is shown, in both theory and practice, to yield an effective AMGr algorithm. Copyright © 2006 John Wiley & Sons, Ltd.