AN OPTIMAL V-CYCLE MULTIGRID METHOD FOR CONFORMING AND NONCONFORMING PLATE ELEMENTS

In this paper, an optimal V-cycle multigrid method for some conforming and nonconforming plate elements are constructed. A new method dealing with nonnested multigrid methods is presented.     

ON THE CONVERGENCE OF THE NONNESTED V-CYCLE MULTIGRID METHOD FOR NONSYMMETRIC AND INDEFINITE SECOND-ORDER ELLIPTIC PROBLEMS

This paper provides a proof for the uniform convergence rate （independently of the number of mesh levels） for the nonnested V-cycle multigrid method for nonsymmetric and indefinite second-order elliptic problems.     

V-cycle convergence of some multigrid methods for ill-posed problems

For ill-posed linear operator equations we consider some V-cycle multigrid approaches, that, in the framework of Bramble, Pasciak, Wang, and Xu (1991), we prove to yield level independent contraction factor estimates. Consequently, we can incorporate these multigrid operators in a full multigrid method, that, together with a discrepancy principle, is shown to act as an iterative regularization method for the underlying infinite-dimensional ill-posed problem. Numerical experiments illustrate the theoretical results.

     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

MULTIGRID METHODS FOR MORLEY ELEMENT ON NONNESTED MESHES

1.IntroductionWeconsidersomemultigridalgorithmsforthebiharmonicequationdiscretizedbyMoneyelementonnonnestedmeshes.TOdefineamultigridalgorithm,certainintergridtransferoperatorhastobeconstructed.Throughtakingtheaveragesofthenodalvariables,weconstructanintergridtransferoperatorforMoneyelementonnonnestedmeshesthatsatisfiesacertainstableapproximationpropertywhichplaysakeyroleinmultigridmethodsfornonconformingplateelementsonnonnestedmeshes.Theso--calledregularity-approximaticnassurnptionisestablis…     

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.

     

The convergence of V-cycle multigrid algorithms for axisymmetric Laplace and Maxwell equations

We investigate some simple finite element discretizations for the axisymmetric Laplace equation and the azimuthal component of the axisymmetric Maxwell equations as well as multigrid algorithms for these discretizations. Our analysis is targeted at simple model problems and our main result is that the standard V-cycle with point smoothing converges at a rate independent of the number of unknowns. This is contrary to suggestions in the existing literature that line relaxations and semicoarsening are needed in multigrid algorithms to overcome difficulties caused by the singularities in the axisymmetric Maxwell problems. Our multigrid analysis proceeds by applying the well known regularity based multigrid theory. In order to apply this theory, we prove regularity results for the axisymmetric Laplace and Maxwell equations in certain weighted Sobolev spaces. These, together with some new finite element error estimates in certain weighted Sobolev norms, are the main ingredients of our analysis.

     

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.     

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

     

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     

Smoothing factor,order of prolongation and actual multigrid convergence

We consider the Fourier analysis of multigrid methods (of Galerkin type) for symmetric positive definite and semi-positive definite linear systems arising from the discretization of scalar partial differential equations (PDEs). We relate the so-called smoothing factor to the actual two-grid convergence rate and also to the convergence rate of the V-cycle multigrid. We derive a two-sided bound that defines an interval containing both the two-grid and V-cycle convergence rate. This interval is narrow and away from 1 when both the smoothing factor and an additional parameter are small enough. Besides the smoothing factor, the convergence mainly depends on the angle between the range of the prolongation and the eigenvectors of the system matrix associated with small eigenvalues. Nice V-cycle convergence is guaranteed if the tangent of this angle has an upper bound proportional to the eigenvalue, whereas nice two-grid convergence requires a bound proportional to the square root of the eigenvalue. We also discuss the well-known rule which relates the order of the prolongation to that of the differential operator associated to the problem. We first define a frequency based order which in most cases amounts to the so-called high frequency order as defined in Hemker (J Comput Appl Math 32:423–429, 1990). We give a firmer basis to the related order rule by showing that, together with the requirement of having the smoothing factor away from one, it provides necessary and sufficient conditions for having the two-grid convergence rate away from 1. A stronger condition is further shown to be sufficient for optimal convergence with the V-cycle. The presented results apply to rigorous Fourier analysis for regular discrete PDEs, and also to local Fourier analysis via the discussion of semi-positive systems as may arise from the discretization of PDEs with periodic boundary conditions.     

Nonnested multigrid methods for linear problems

This article presents an application of nonnested and unstructured multigrid methods to linear elastic problems. A variational formulation for transfer operators and some multigrid strategies, including adaptive algorithms, are presented. Expressions for the performance evaluation of multigrid strategies and its comparison with direct and preconditioned conjugate gradient algorithms are also presented. A C++ implementation of the multigrid algorithms and the quadtree and octree data structures for transfer operators are discussed. Some two‐ and three‐dimensional elasticity examples are analyzed. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:313–331, 2001     

MULTIGRID ALGORITHM FOR THE COUPLING SYSTEM OF NATURAL BOUNDARY ELEMENT METHOD AND FINITE ELEMENT METHOD FOR UNBOUNDED DOMAIN PROBLEMS

In this paper, some V-cycle multigrid algorithms are presented for the coupling system arising from the discretization of the Dirichlet exterior problem by coupling the natural boundary element method and finite element method. The convergence of these multigrid algorithms is obtained even with only one smoothing on all levels. The rate of convergence is found uniformly bounded independent of the number of levels and the mesh sizes of all levels, which indicates that these multigrid algorithms are optimal. Some numerical results are also reported.     

Global and uniform convergence of subspace correction methods for some convex optimization problems

This paper gives some global and uniform convergence estimates for a class of subspace correction (based on space decomposition) iterative methods applied to some unconstrained convex optimization problems. Some multigrid and domain decomposition methods are also discussed as special examples for solving some nonlinear elliptic boundary value problems.

     

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     

Multigrid methods for a parameter dependent problem in primal variables

Summary. In this paper we consider multigrid methods for the parameter dependent problem of nearly incompressible materials. We construct and analyze multilevel-projection algorithms, which can be applied to the mixed as well as to the equivalent, non-conforming finite element scheme in primal variables. For proper norms, we prove that the smoothing property and the approximation property hold with constants that are independent of the small parameter. Thus we obtain robust and optimal convergence rates for the W-cycle and the variable V-cycle multigrid methods. The numerical results pretty well conform the robustness and optimality of the multigrid methods proposed. Received June 17, 1998 / Revised version received October 26, 1998 / Published online September 7, 1999     

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.     

MORTAR型旋转Q_1元的多重网格方法

本文讨论了mortar型旋转Q_1元的多重网格方法.证明了W循环的多重网格法是最优的,即收敛率与网格尺寸及层数无关.同时给出了一种可变的V循环多重网格算法,得到了一个条件数一致有界的预条件子.最后,数值试验验证了我们的理论结果.     

MULTIGRID METHODS FOR THE GENERALIZED STOKES EQUATIONS BASED ON MIXED FINITE ELEMENT METHODS

1. IntroductionIn this paper, we consider the fOllowing generalized stationary Stokes equations:where fl is a bounded convex domain in R', u represents the velocity of fluid, p its pressure; Fand G are external fOrce and source terms. Note that the source…     

Multigrid for the mortar element method for P1 nonconforming element

In this paper, a multigrid algorithm is presented for the mortar element method for P1 nonconforming element. Based on the theory developed by Bramble, Pasciak, Xu in [5], we prove that the W-cycle multigrid is optimal, i.e. the convergence rate is independent of the mesh size and mesh level. Meanwhile, a variable V-cycle multigrid preconditioner is constructed, which results in a preconditioned system with uniformly bounded condition number. Received May 11, 1999 / Revised version received April 1, 2000 / Published online October 16, 2000