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.     

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

Convergence of V‐ and F‐cycle multigrid methods for the biharmonic problem using the Hsieh‐Clough‐Tocher element

Multigrid V‐ and F‐cycle algorithms for the biharmonic problem using the H‐C‐T element are studied in the article. We show that the contraction numbers can be uniformly improved by increasing the number of smoothing steps. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

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.     

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.     

Algebraic multigrid preconditioning of the Hessian in optimization constrained by a partial differential equation

We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.     

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.     

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.     

A convergent multigrid cycle for the hybridized mixed method

We consider the application of a variable V‐cycle multigrid algorithm for the hybridized mixed method for second‐order elliptic boundary‐value problems. Our algorithm differs from the previous works on multigrid for the mixed method in that it is targeted at efficiently solving the matrix system for the Lagrange multiplier of the method. Since the mixed method is best implemented by first solving for the Lagrange multiplier and recovering the remaining unknowns locally, our algorithm is more useful in practice. The critical ingredient in the algorithm is a suitable intergrid transfer operator. We design such an operator and prove mesh‐independent convergence of the variable V‐cycle algorithm. Numerical experiments indicating the asymptotically optimal performance of our algorithm, as well as the failure of certain seemingly plausible intergrid transfer operators, are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

On a finite element method for unsteady compressible viscous flows

In this article we present an analysis of a finite element method for solving two‐dimensional unsteady compressible Navier‐Stokes equations. Under the time‐stepping size restriction Δt ≤ Ch, we prove the existence and uniqueness of the numerical solution and obtain an a prior error estimate uniform in time. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 152–166, 2003     

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.     

Least‐squares finite element method on adaptive grid for PDEs with shocks

We apply the least‐squares finite element method with adaptive grid to nonlinear time‐dependent PDEs with shocks. The least‐squares finite element method is also used in applying the deformation method to generate the adaptive moving grids. The effectiveness of this method is demonstrated by solving a Burgers' equation with shocks. Computational results on uniform grids and adaptive grids are compared for the purpose of evaluation. The results show that the adaptive grids can capture the shock more sharply with significantly less computational time. For moving shock, the adaptive grid moves correctly with the shock. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Parallel multigrid method for finite element simulations of complex flow problems on locally refined meshes

We present a parallel multigrid solver on locally refined meshes for solving very complex three‐dimensional flow problems. Besides describing the parallel implementation in detail, we prove the smoothing property of the suggested iteration for a simple model problem. For demonstration of the efficiency and feasibility of the solver, we show a chemically reactive flow simulation for a Methane burner using detailed chemical reaction modeling. Further, we give the results of an ocean flow simulation. All described methods are implemented in the finite element toolbox Gascoigne. Copyright © 2010 John Wiley & Sons, Ltd.     

A posteriori error estimate for the mixed finite element method

A computable error bound for mixed finite element methods is established in the model case of the Poisson-problem to control the error in the H(div,) -norm. The reliable and efficient a posteriori error estimate applies, e.g., to Raviart-Thomas, Brezzi-Douglas-Marini, and Brezzi-Douglas-Fortin-Marini elements.

     

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.     

Quasi‐optimality of the adaptive finite element method for the eigenvalue problem arising from the vibration frequencies of the cavity flow

In this article, we present a posteriori error analysis for the regularization formulation of the eigenvalue problem arising from the vibration frequencies of the cavity flow. The quasi‐optimality of the adaptive finite element method is also proved for the single eigenvalues under the Dörfler's marking strategy without marking the oscillation terms and enforcing the so‐called interior node property. Numerical examples illustrate the quasi‐optimality of the adaptive finite element method. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 900–922, 2015     

Solution of some plate bending problems using the boundary element method

Some fundamental aspects of the boundary element method of the Kirchhoff theory of thin plate flexure are given. The direct boundary integral equation method with higher conforming properties (using first-order Hermitian interpolation for plate displacement ω, and zero-order Hermitian interpolation for angle of rotation θ, the moment M andthe equivalent shear V) are used for several computational examples. They are: square plate with simply-supported or clamped edges, the same square plate with square central opening and the cantilevered triangular plates. The results of computation as compared with some known experimental and theoritical results showed that the numerical schemes seemed to be satisfactory for the practical applications.     

Simplified versions of the conditional gradient method

ABSTRACT

We suggest simple modifications of the conditional gradient method for smooth optimization problems, which maintain the basic convergence properties, but reduce the implementation cost of each iteration essentially. Namely, we propose an adaptive step-size procedure without any line-search and inexact solution of the direction finding subproblem. Preliminary results of computational tests confirm efficiency of the proposed modifications.