Multigrid algorithms for a vertex–centered covolume method for elliptic problems

Summary. We analyze V–cycle multigrid algorithms for a class of perturbed problems whose perturbation in the bilinear form preserves the convergence properties of the multigrid algorithm of the original problem. As an application, we study the convergence of multigrid algorithms for a covolume method or a vertex–centered finite volume element method for variable coefficient elliptic problems on polygonal domains. As in standard finite element methods, the V–cycle algorithm with one pre-smoothing converges with a rate independent of the number of levels. Various types of smoothers including point or line Jacobi, and Gauss-Seidel relaxation are considered. Received August 19, 1999 / Revised version received July 10, 2000 / Published online June 7, 2001     

Stability theorems for singular perturbation of eigenvalues

Two stability, i.e., convergence in multiplicity, theorems for eigenvalues of non-self-adjoint singular perturbation problems are proved in this paper. Use is made of quadratic interpolation between Hubert spaces to obtain an extension of the notion of a holomorphic family of type (B). Applications to singular perturbation problems for non-self-adjoint elliptic partial differential operators, and to singular potential perturbation problems with complex coupling constants, are presented.This research was partially supported by NSF Grant 02 MCS-7902663     

An iterative method based on equation decomposition for the fourth‐order singular perturbation problem

In this article, we propose an iterative method based on the equation decomposition technique ( 1 ) for the numerical solution of a singular perturbation problem of fourth‐order elliptic equation. At each step of the given method, we only need to solve a boundary value problem of second‐order elliptic equation and a second‐order singular perturbation problem. We prove that our approximate solution converges to the exact solution when the domain is a disc. Our numerical examples show the efficiency and accuracy of our method. Our iterative method works very well for singular perturbation problems, that is, the case of 0 < ε ? 1, and the convergence rate is very fast. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Uniform Convergence of Adaptive Multigrid Methods for Elliptic Problems and Maxwell's Equations

We consider the convergence theory of adaptive multigrid methods for second-order elliptic problems and Maxwell's equations. The multigrid algorithm only performs pointwise Gauss-Seidel relaxations on new degrees of freedom and their "immediate" neighbors. In the context of lowest order conforming finite element approximations, we present a unified proof for the convergence of adaptive multigrid V-cycle algorithms. The theory applies to any hierarchical tetrahedral meshes with uniformly bounded shape-regularity measures. The convergence rates for both problems are uniform with respect to the number of mesh levels and the number of degrees of freedom. We demonstrate our convergence theory by two numerical experiments.     

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.     

NON C~0 NONCONFORMING ELEMENTS FOR ELLIPTIC FOURTH ORDER SINGULAR PERTURBATION PROBLEM

In this paper we give a convergence theorem for non C^0 nonconforming finite element to solve the elliptic fourth order singular perturbation problem. Two such kind of elements, a nine parameter triangular element and a twelve parameter rectangular element both with double set parameters, are presented. The convergence and numerical results of the two elements are given.     

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.     

Fourier-Laplace analysis of the multigrid waveform relaxation method for hyperbolic equations

The multigrid waveform relaxation (WR) algorithm has been fairly studied and implemented for parabolic equations. It has been found that the performance of the multigrid WR method for a parabolic equation is practically the same as that of multigrid iteration for the associated steady state elliptic equation. However, the properties of the multigrid WR method for hyperbolic problems are relatively unknown. This paper studies the multigrid acceleration to the WR iteration for hyperbolic problems, with a focus on the convergence comparison between the multigrid WR iteration and the multigrid iteration for the corresponding steady state equations. Using a Fourier-Laplace analysis in two case studies, it is found that the multigrid performance on hyperbolic problems no longer shares the close resemblance in convergence factors between the WR iteration for parabolic equations and the iteration for the associated steady state equations.     

椭圆-抛物偏微分方程奇异摄动问题的差分解法

本文讨论了含有小参数在高阶导数项的椭圆型方程奇异摄动问题的差分解法.当ε=0时椭圆型方程退化为抛物型方程.作者根据此问题解的边界层性质,构造了特殊的差分格式:研究了它的收敛性和解的渐近性态.最后给出一个数值例题.     

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.     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

Uniformly stable rectangular elements for fourth order elliptic singular perturbation problems

In this article, we consider rectangular finite element methods for fourth order elliptic singular perturbation problems. We show that the non‐ C⁰ rectangular Morley element is uniformly convergent in the energy norm with respect to the perturbation parameter. We also propose a C⁰ extended high order rectangular Morley element and prove the uniform convergence. Finally, we do some numerical experiments to confirm the theoretical results. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

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.     

Semilinear Finite Element Method

In the Ritz-Galerkin method the linear subspace of the trial solution is extended to a closed subset. Some results, such as orthogonalization and minimum property of the error function, are obtained. A second order scheme is developed for solving a linear singular perturbation elliptic problem and error estimates are given for a uniform mesh size. Numerical results for linear and semilinear singular perturbation problems are included.     

The Convergence of Multigrid Methods for Nonsymmetric Elliptic Variational Inequalities

This paper is concerned with the convergence of multigrid methods (MGM) on nonsymmetric elliptic variational inequalities. On the basis of Wang and Zeng's work (1988), we develop the convergence results of the smoothing operator (i.e. PJOR and PSOR). We also extend the multigrid method of J.Mandel (1984) to nonsymmetric variational inequalities and obtain the convergence of MGM for these problems.     

A compact finite difference scheme for 2D reaction–diffusion singularly perturbed problems

In this work we define a compact finite difference scheme of positive type to solve a class of 2D reaction–diffusion elliptic singularly perturbed problems. We prove that if the new scheme is constructed on a piecewise uniform mesh of Shishkin type, it provides better approximations than the classical central finite difference scheme. Moreover, the uniform parameter bound of the error shows that the scheme is third order convergent in the maximum norm when the singular perturbation parameter is sufficiently small. Some numerical experiments illustrate in practice the result of convergence proved theoretically.     

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.     

A new semi-smooth Newton multigrid method for control-constrained semi-linear elliptic PDE problems

In this paper a new multigrid algorithm is proposed to accelerate the convergence of the semi-smooth Newton method that is applied to the first order necessary optimality systems arising from a class of semi-linear control-constrained elliptic optimal control problems. Under admissible assumptions on the nonlinearity, the discretized Jacobian matrix is proved to have an uniformly bounded inverse with respect to mesh size. Different from current available approaches, a new numerical implementation that leads to a robust multigrid solver is employed to coarsen the grid operator. Numerical simulations are provided to illustrate the efficiency of the proposed method, which shows to be computationally more efficient than the full-approximation-storage multigrid in current literature. In particular, our proposed approach achieves a mesh-independent convergence and its performance is highly robust with respect to the regularization parameter.     

On Schwarz-type smoothers for elliptic optimal control problems

We present a multigrid method for elliptic optimal control problems using a patch smoother. The method allows a rigorous multigrid convergence analysis and shows good convergence properties, which are comparable with known results from literature. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

多刚性奇异摄动问题Rosenbrock方法的定量误差分析

本文获得了Rosenbrock方法关于一类多刚性奇异摄动问题的定量收敛结果．这是对Strehmel等人于1991年所获的单刚性奇异摄动问题相应结果的推广和发展．