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.     

Two‐level Fourier analysis of multigrid for higher‐order finite‐element discretizations of the Laplacian

In this paper, we employ local Fourier analysis (LFA) to analyze the convergence properties of multigrid methods for higher‐order finite‐element approximations to the Laplacian problem. We find that the classical LFA smoothing factor, where the coarse‐grid correction is assumed to be an ideal operator that annihilates the low‐frequency error components and leaves the high‐frequency components unchanged, fails to accurately predict the observed multigrid performance and, consequently, cannot be a reliable analysis tool to give good performance estimates of the two‐grid convergence factor. While two‐grid LFA still offers a reliable prediction, it leads to more complex symbols that are cumbersome to use to optimize parameters of the relaxation scheme, as is often needed for complex problems. For the purposes of this analytical optimization as well as to have simple predictive analysis, we propose a modification that is “between” two‐grid LFA and smoothing analysis, which yields reasonable predictions to help choose correct damping parameters for relaxation. This exploration may help us better understand multigrid performance for higher‐order finite element discretizations, including for Q₂‐Q₁ (Taylor‐Hood) elements for the Stokes equations. Finally, we present two‐grid and multigrid experiments, where the corrected parameter choice is shown to yield significant improvements in the resulting two‐grid and multigrid convergence factors.     

A robust preconditioner for higher order finite element discretizations in linear elasticity

Based on the auxiliary space method, a preconditioner is studied in this paper for linear systems of equations arising from higher order finite element (FEM) discretizations of linear elasticity equations. The main idea, which is proposed by Xu (Computing 1996; 56 :215–235) for the scalar PDE, is to construct the preconditioner as a combination of a smoother and a coarse level solver, where the systems of equations arising from lower order FEM discretizations are used in the coarse level solver. It is theoretically shown that the condition number of the preconditioned systems is uniformly bounded with respect to both the problem size and moderate Poisson's ratio. When the Poisson's ratio is near the limit of 0.5, we have presented some numerical tests for the case of fourth‐order FEM discretization in a combination with quadratic conforming FEM as a coarse space. The results are almost robust when Poisson's ratio is near the limit of 0.5. Copyright © 2011 John Wiley & Sons, Ltd.     

An algebraic multigrid method for finite element systems on criss-cross grids

In this paper, we design and analyze an algebraic multigrid method for a condensed finite element system on criss-cross grids and then provide a convergence analysis. Criss-cross grid finite element systems represent a large class of finite element systems that can be reduced to a smaller system by first eliminating certain degrees of freedoms. The algebraic multigrid method that we construct is analogous to many other algebraic multigrid methods for more complicated problems such as unstructured grids, but, because of the specialty of our problem, we are able to provide a rigorous convergence analysis to our algebraic multigrid method. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday The work was supported in part by NSAF(10376031) and National Major Key Project for basic researches and by National High-Tech ICF Committee in China.     

An algebraic multigrid method for elasticity based on an auxiliary topology with edge matrices

This article introduces a novel approach to algebraic multigrid methods for large systems of linear equations coming from finite element discretizations of certain elliptic second-order partial differential equations. Based on a discrete energy made up of edge and vertex contributions, we are able to develop coarsening criteria that guarantee two-level convergence even for systems of equations such as linear elasticity . This energy also allows us to construct prolongations with prescribed sparsity pattern that still preserve kernel vectors exactly. These allow for a straightforward optimization that simplifies parallelization and reduces communication on coarse levels. Numerical experiments demonstrate efficiency and robustness of the method and scalability of the implementation.     

An algebraic multigrid method for finite element discretizations with edge elements

This paper presents an algebraic multigrid method for the efficient solution of the linear system arising from a finite element discretization of variational problems in H₀(curl,Ω). The finite element spaces are generated by Nédélec's edge elements. A coarsening technique is presented, which allows the construction of suitable coarse finite element spaces, corresponding transfer operators and appropriate smoothers. The prolongation operator is designed such that coarse grid kernel functions of the curl‐operator are mapped to fine grid kernel functions. Furthermore, coarse grid kernel functions are ‘discrete’ gradients. The smoothers proposed by Hiptmair and Arnold, Falk and Winther are directly used in the algebraic framework. Numerical studies are presented for 3D problems to show the high efficiency of the proposed technique. Copyright © 2002 John Wiley & Sons, Ltd.     

Rational Chebyshev collocation method for solving higher‐order linear ordinary differential equations

A collocation method to find an approximate solution of higher‐order linear ordinary differential equation with variable coefficients under the mixed conditions is proposed. This method is based on the rational Chebyshev (RC) Tau method and Taylor‐Chebyshev collocation methods. The solution is obtained in terms of RC functions. Also, illustrative examples are included to demonstrate the validity and applicability of the technique, and performed on the computer using a program written in maple9. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1130–1142, 2011     

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 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.     

Algebraic analysis of aggregation‐based multigrid

A convergence analysis of two‐grid methods based on coarsening by (unsmoothed) aggregation is presented. For diagonally dominant symmetric (M‐)matrices, it is shown that the analysis can be conducted locally; that is, the convergence factor can be bounded above by computing separately for each aggregate a parameter, which in some sense measures its quality. The procedure is purely algebraic and can be used to control a posteriori the quality of automatic coarsening algorithms. Assuming the aggregation pattern is sufficiently regular, it is further shown that the resulting bound is asymptotically sharp for a large class of elliptic boundary value problems, including problems with variable and discontinuous coefficients. In particular, the analysis of typical examples shows that the convergence rate is insensitive to discontinuities under some reasonable assumptions on the aggregation scheme. Copyright © 2010 John Wiley & Sons, Ltd.     

Mixed two‐grid finite difference methods for solving one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations

The aim of this paper is to propose mixed two‐grid finite difference methods to obtain the numerical solution of the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. The finite difference equations at all interior grid points form a large‐sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a family of finite difference methods for discretizing the spatial and time derivatives. The obtained system has been solved by two‐grid method, where the two‐grid method is used for solving the large‐sparse linear systems. Also, in the proposed method, the spectral radius with local Fourier analysis is calculated for different values of h and Δt. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional and two‐dimensional Fitzhugh–Nagumo equations. Copyright © 2016 John Wiley & Sons, Ltd.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

Adaptive iterative regularization schemes for two‐dimensional integral‐algebraic systems

The main idea of this paper is to utilize the adaptive iterative schemes based on regularization techniques for moderately ill‐posed problems that are obtained by a system of linear two‐dimensional Volterra integral equations with a singular matrix in the leading part. These problems may arise in the modeling of certain heat conduction processes as well as in the dynamic simulation packages such as compressible flow through a plant piping network. Owing to the ill‐posed nature of the first kind Volterra equation that appears in the system, we will focus on the two families of regularization algorithms, ie, the Landweber and Lavrentiev type methods, where we treat both the exact and perturbed data. Our aim is to work directly with the original Volterra equations without any kind of reduction. Two fast iterative algorithms with reasonable computational complexity are developed. Numerical experiments on a few test problems are used to illustrate the validity and efficiency of the proposed iterative methods in comparison with the classical regularization methods.     

A two‐grid characteristic finite volume element method for semilinear advection‐dominated diffusion equations

A two‐grid finite volume element method, combined with the modified method of characteristics, is presented and analyzed for semilinear time‐dependent advection‐dominated diffusion equations in two space dimensions. The solution of a nonlinear system on the fine‐grid space (with grid size h) is reduced to the solution of two small (one linear and one nonlinear) systems on the coarse‐grid space (with grid size H) and a linear system on the fine‐grid space. An optimal error estimate in H¹ ‐norm is obtained for the two‐grid method. It shows that the two‐grid method achieves asymptotically optimal approximation, as long as the mesh sizes satisfy h = O(H²). Numerical example is presented to validate the usefulness and efficiency of the method. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Analysis of an aggregation‐based algebraic two‐grid method for a rotated anisotropic diffusion problem

A two‐grid convergence analysis based on the paper [Algebraic analysis of aggregation‐based multigrid, by A. Napov and Y. Notay, Numer. Lin. Alg. Appl. 18 (2011), pp. 539–564] is derived for various aggregation schemes applied to a finite element discretization of a rotated anisotropic diffusion equation. As expected, it is shown that the best aggregation scheme is one in which aggregates are aligned with the anisotropy. In practice, however, this is not what automatic aggregation procedures do. We suggest approaches for determining appropriate aggregates based on eigenvectors associated with small eigenvalues of a block splitting matrix or based on minimizing a quantity related to the spectral radius of the iteration matrix. Copyright © 2015 John Wiley & Sons, Ltd.     

Two‐grid method for two‐dimensional nonlinear Schrödinger equation by finite element method

A conservative two‐grid finite element scheme is presented for the two‐dimensional nonlinear Schrödinger equation. One Newton iteration is applied on the fine grid to linearize the fully discrete problem using the coarse‐grid solution as the initial guess. Moreover, error estimates are conducted for the two‐grid method. It is shown that the coarse space can be extremely coarse, with no loss in the order of accuracy, and still achieve the asymptotically optimal approximation as long as the mesh sizes satisfy in the two‐grid method. The numerical results show that this method is very effective.     

Modulus‐based multigrid methods for linear complementarity problems

By employing modulus‐based matrix splitting iteration methods as smoothers, we establish modulus‐based multigrid methods for solving large sparse linear complementarity problems. The local Fourier analysis is used to quantitatively predict the asymptotic convergence factor of this class of multigrid methods. Numerical results indicate that the modulus‐based multigrid methods of the W‐cycle can achieve optimality in terms of both convergence factor and computing time, and their asymptotic convergence factors can be predicted perfectly by the local Fourier analysis of the corresponding modulus‐based two‐grid methods.     

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.     

A two‐grid stabilization method for solving the steady‐state Navier‐Stokes equations

We formulate a subgrid eddy viscosity method for solving the steady‐state incompressible flow problem. The eddy viscosity does not act on the large flow structures. Optimal error estimates are obtained for velocity and pressure. The numerical illustrations agree completely with the theoretical results. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

An element agglomeration nonlinear additive Schwarz preconditioned Newton method for unstructured finite element problems

This paper extends previous results on nonlinear Schwarz preconditioning (Cai and Keyes 2002) to unstructured finite element elliptic problems exploiting now nonlocal (but small) subspaces. The nonlocal finite element subspaces are associated with subdomains obtained from a non-overlapping element partitioning of the original set of elements and are coarse outside the prescribed element subdomain. The coarsening is based on a modification of the agglomeration based AMGe method proposed in Jones and Vassilevski 2001. Then, the algebraic construction from Jones, Vassilevski and Woodward 2003 of the corresponding non-linear finite element subproblems is applied to generate the subspace based nonlinear preconditioner. The overall nonlinearly preconditioned problem is solved by an inexact Newton method. A numerical illustration is also provided.This work was performed under the auspices of the U.S. Department of Energy by the University of California Lawrence Livermore National Laboratory: contract/grant number: W-7405-Eng-48. The contribution of the second author was also partially supported by Polish Scientific Grant 2/P03A/005/24.