MONOLITHIC MULTIGRID FOR REDUCED MAGNETOHYDRODYNAMIC EQUATIONS

In this paper,the monolithic multigrid method is investigated for reduced magnetohydrodynamic equations.We propose a diagonal Braess-Sarazin smoother for the finite element discrete system and prove the uniform convergence of the MMG method with respect to mesh sizes.A multigrid-preconditioned FGMRES method is proposed to solve the magnetohydrodynamic equations.It turns out to be robust for relatively large physical parameters.By extensive numerical experiments,we demonstrate the optimality of the monolithic multigrid method with respect to the number of degrees of freedom.     

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.     

Local Multigrid in H（curl）

We consider H（curl, Ω）-elliptic variational problems on bounded Lipschitz polyhedra and their finite element Galerkin discretization by means of lowest order edge elements. We assume that the underlying tetrahedral mesh has been created by successive local mesh refinement, either by local uniform refinement with hanging nodes or bisection refinement. In this setting we develop a convergence theory for the the so-called local multigrid correction scheme with hybrid smoothing. We establish that its convergence rate is uniform with respect to the number of refinement steps. The proof relies on corresponding results for local multigrid in a H^1 （Ω）-context along with local discrete Helmholtz-type decompositions of the edge element space.     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

Uniform Convergence of Multigrid V-Cycle on Adaptively Refined Finite Element Meshes for Elliptic Problems with Discontinuous Coefficients

The multigrid V-cycle methods for adaptive finite element discretizations of two-dimensional elliptic problems with discontinuous coefficients are considered. Under the conditions that the coefficient is quasi-monotone up to a constant and the meshes are locally refined by using the newest vertex bisection algorithm, some uniform convergence results are proved for the standard multigrid V-cycle algorithm with Gauss-Seidel relaxations performed only on new nodes and their immediate neighbours. The multigrid V-cycle algorithm uses $\mathcal{O}(N)$ operations per iteration and is optimal.     

Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

Multigrid Computation of Axisymmetric Electromagnetic Fields

The focus of this paper is on boundary value problems for Maxwell's equations that feature cylindrical symmetry both of the domain R ³ and the data. Thus, by resorting to cylindrical coordinates, a reduction to two dimensions is possible. However, cylindrical coordinates introduce a potentially malicious singularity at the axis rendering the variational problems degenerate. As a consequence, the analysis of multigrid solvers along the lines of variational multigrid theory confronts severe difficulties. Line relaxation in radial direction and semicoarsening can successfully reign in the degeneracy. In addition, the lack of H ¹-ellipticity of the double-curl operator entails using special hybrid smoothing procedures. All these techniques combined yield a fast multigrid solver. The theoretical investigation of the method relies on blending generalized Fourier techniques and modern variational multigrid theory. We first determine invariant subspaces of the multigrid iteration operator and analyze the smoothers therein. Under certain assumptions on the material parameters we manage to show uniform convergence of a symmetric V-cycle.     

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.     

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)     

Convergence Analysis of Spatially Adaptive Rothe Methods

This paper is concerned with the convergence analysis of the horizontal method of lines for evolution equations of the parabolic type. Following a semidiscretization in time by \(S\) -stage one-step methods, the resulting elliptic stage equations per time step are solved with adaptive space discretization schemes. We investigate how the tolerances in each time step must be tuned in order to preserve the asymptotic temporal convergence order of the time stepping also in the presence of spatial discretization errors. In particular, we discuss the case of linearly implicit time integrators and adaptive wavelet discretizations in space. Using concepts from regularity theory for partial differential equations and from nonlinear approximation theory, we determine an upper bound for the degrees of freedom for the overall scheme that are needed to adaptively approximate the solution up to a prescribed tolerance.     

Uniform convergence of the multigrid V-cycle for an anisotropic problem

In this paper, we consider the linear systems arising from the standard finite element discretizations of certain second order anisotropic problems with variable coefficients on a rectangle. We study the performance of a V-cycle multigrid method applied to the finite element equations. Since the usual ``regularity and approximation' assumption does not hold for the anisotropic finite element problems, the standard multigrid convergence theory cannot be applied directly. In this paper, a modification of the theory of Braess and Hackbusch will be presented. We show that the V-cycle multigrid iteration with a line smoother is a uniform contraction in the energy norm. In the verification of the hypotheses in our theory, we use a weighted -norm estimate for the error in the Galerkin finite element approximation and a smoothing property of the line smoothers which is proved in this paper.

     

Online adaptive local multiscale model reduction for heterogeneous problems in perforated domains

In this paper, we develop and analyze an adaptive multiscale approach for heterogeneous problems in perforated domains. We consider commonly used model problems including the Laplace equation, the elasticity equation, and the Stokes system in perforated regions. In many applications, these problems have a multiscale nature arising because of the perforations, their geometries, the sizes of the perforations, and configurations. Typical modeling approaches extract average properties in each coarse region, that encapsulate many perforations, and formulate a coarse-grid problem. In some applications, the coarse-grid problem can have a different form from the fine-scale problem, e.g. the coarse-grid system corresponding to a Stokes system in perforated domains leads to Darcy equations on a coarse grid. In this paper, we present a general offline/online procedure, which can adequately and adaptively represent the local degrees of freedom and derive appropriate coarse-grid equations. Our approaches start with the offline procedure, which constructs multiscale basis functions in each coarse region and formulates coarse-grid equations. We presented the offline simulations without the analysis and adaptive procedures, which are needed for accurate and efficient simulations. The main contributions of this paper are (1) the rigorous analysis of the offline approach, (2) the development of the online procedures and their analysis, and (3) the development of adaptive strategies. We present an online procedure, which allows adaptively incorporating global information and is important for a fast convergence when combined with the adaptivity. We present online adaptive enrichment algorithms for the three model problems mentioned above. Our methodology allows adding and guides constructing new online multiscale basis functions adaptively in appropriate regions. We present the convergence analysis of the online adaptive enrichment algorithm for the Stokes system. In particular, we show that the online procedure has a rapid convergence with a rate related to the number of offline basis functions, and one can obtain fast convergence by a sufficient number of offline basis functions, which are computed in the offline stage. The convergence theory can also be applied to the Laplace equation and the elasticity equation. To illustrate the performance of our method, we present numerical results with both small and large perforations. We see that only a few (1 or 2) online iterations can significantly improve the offline solution.     

Convergence of nonconforming -cycle and -cycle multigrid algorithms for second order elliptic boundary value problems

The convergence of -cycle and -cycle multigrid algorithms with a sufficiently large number of smoothing steps is established for nonconforming finite element methods for second order elliptic boundary value problems.

     

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.     

The Convergence of Multigrid Methods for Solving Finite Element Equations in the Presence of Singularities

1.IntroductionMultigridMethodsprovideoptimalordersolversforlinearsysternsoffiniteele-mentequationsarisingfromellipticboundaryvalueproblems.Theconvergenceofmultigridmethodswasprovedbymanya.tho.s[2-6,9-12l.AlltheseproofS,requirestrongregularitiesandquasi-uniformityofgridsl',,']-Forexample,assumingH1+oregularityandquasi-uniformtriangulations,Bank&Dupollt[3]showedaconvergencerateofo(mY),foragrowingnumbermofsmoothingstepsperlevel.Intheoptimalcasecr=1,theproblemhastobeH'-regUlar.Whentheregionhas…     

The analysis of multigrid algorithms for cell centered finite difference methods

In this paper, we examine multigrid algorithms for cell centered finite difference approximations of second order elliptic boundary value problems. The cell centered application gives rise to one of the simplest non-variational multigrid algorithms. We shall provide an analysis which guarantees that the W-cycle and variable V-cycle multigrid algorithms converge with a rate of iterative convergence which can be bounded independently of the number of multilevel spaces. In contrast, the natural variational multigrid algorithm converges much more slowly.     

A cascadic multigrid method for a kind of semilinear elliptic problem

In this paper, we analyze a cascadic multigrid method for semilinear elliptic problems in which the derivative of the semilinear term is Hölder continuous. We first investigate the standard finite element error estimates of this kind of problem. We then solve the corresponding discrete problems using the cascadic multigrid method. We prove that the algorithm has an optimal order of convergence in energy norm and quasi-optimal computational complexity. We also report some numerical results to support the theory.     

Convergence analysis of a multigrid method for convection–diffusion equations

Summary. This paper is concerned with the convergence analysis of robust multigrid methods for convection-diffusion problems. We consider a finite difference discretization of a 2D model convection-diffusion problem with constant coefficients and Dirichlet boundary conditions. For the approximate solution of this discrete problem a multigrid method based on semicoarsening, matrix-dependent prolongation and restriction and line smoothers is applied. For a multigrid W-cycle we prove an upper bound for the contraction number in the euclidean norm which is smaller than one and independent of the mesh size and the diffusion/convection ratio. For the contraction number of a multigrid V-cycle a bound is proved which is uniform for a class of convection-dominated problems. The analysis is based on linear algebra arguments only. Received April 26, 2000 / Published online June 20, 2001     

The Convergence of the Multigrid Algorithm for Navier-Stokes Equations

This paper deal with a multigrid algorithm for the numerical solution of Navier-Stokes problems. The convergence proof and estimation of the contraction number of the multigrid algorithm are given.     

Analysis of tensor product multigrid

We consider anisotropic second order elliptic boundary value problems in two dimensions, for which the anisotropy is exactly aligned with the coordinate axes. This includes cases where the operator features a singular perturbation in one coordinate direction, whereas its restriction to the other direction remains neatly elliptic. Most prominently, such a situation arises when polar coordinates are introduced.The common multigrid approach to such problems relies on line relaxation in the direction of the singular perturbation combined with semi-coarsening in the other direction. Taking the idea from classical Fourier analysis of multigrid, we employ eigenspace techniques to separate the coordinate directions. Thus, convergence of the multigrid method can be examined by looking at one-dimensional operators only. In a tensor product Galerkin setting, this makes it possible to confirm that the convergence rates of the multigrid V-cycle are bounded independently of the number of grid levels involved. In addition, the estimates reveal that convergence is also robust with respect to a singular perturbation in one coordinate direction.Finally, we supply numerical evidence that the algorithm performs satisfactorily in settings more general than those covered by the proof.