A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

A posteriori H1 error estimation for a singularly perturbed reaction diffusion problem on anisotropic meshes

The paper deals with a singularly perturbed reaction diffusionmodel problem. The focus is on reliable a posteriori error estimatorsfor the H¹ seminorm that can be applied to anisotropic finiteelement meshes. A residual error estimator and a local problemerror estimator are proposed and rigorously analysed. They arelocally equivalent, and both bound the error reliably. Threemodifications of these estimators are introduced and discussed. Much attention is given to the performance of the error estimatorin numerical experiments. This helps to identify those estimatorsthat are suitable for practical applications.     

A mixed finite volume scheme for anisotropic diffusion problems on any grid

We present a new finite volume scheme for anisotropic heterogeneous diffusion problems on unstructured irregular grids, which simultaneously gives an approximation of the solution and of its gradient. The approximate solution is shown to converge to the continuous one as the size of the mesh tends to 0, and an error estimate is given. An easy implementation method is then proposed, and the efficiency of the scheme is shown on various types of grids and for various diffusion matrices.     

Elliptic gradient estimates for diffusion operators on complete riemannian manifolds

In this note, we obtain the elliptic estimate for diffusion operator L = Δ + ∇??∇ on complete, noncompact Riemannian manifolds, under the curvature condition CD(K,m), which generalizes B. L. Kotschwar's work [5]. As an application, we get estimate on the heat kernel. The Bernstein-type gradient estimate for Schrödinger-type gradient is also derived.     

A posteriori L2 error estimation on anisotropic tetrahedral finite element meshes

A new a posteriori L₂ norm error estimator is proposed for thePoisson equation. The error estimator can be applied to anisotropictetrahedral or triangular finite element meshes. The estimatoris rigorously analysed for Dirichlet and Neumann boundary conditions. The lower error bound relies on specifically designed anisotropicbubble functions and the corresponding inverse inequalities.The upper error bound utilizes non-standard anisotropic interpolationestimates. Its proof requires H² regularity of the Poisson problem,and its quality depends on how good the anisotropic mesh resolvesthe anisotropy of the problem. This is measured by a so-called‘matching function’. A numerical example supports the anisotropic error analysis.     

Numerical approximation of anisotropic geometric evolution equations in the plane

Harald GarckeNaturwissenchaftliche Fakultät I' Mathematik, Universität Regensburg, 93040 Regensburg, GermanyRobert NürnbergDepartment of Mathematics, Imperial College London, London SW7 2AZ, UK Received on 13 April 2006. Revised on 20 February 2007. We present a variational formulation of fully anisotropic motionby surface diffusion and mean curvature flow, as well as relatedflows. The proposed scheme covers both the closed-curve caseand the case of curves that are connected via triple junctionpoints. On introducing a parametric finite-element approximation,we prove stability bounds and report on numerical experiments,including regularized crystalline mean curvature flow and regularizedcrystalline surface diffusion. The presented scheme has verygood properties with respect to the distribution of mesh pointsand, if applicable, area conservation.     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

Finite element approximation of a forward and backward anisotropic diffusion model in image denoising and form generalization

A new forward–backward anisotropic diffusion model is introduced. The two limit cases are the Perona‐Malik equation and the Total Variation flow model. A fully discrete finite element scheme is studied using C⁰‐piecewise linear elements in space and the backward Euler difference scheme in time. A priori estimates are proven. Numerical results in image denoising and form generalization are presented.© 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

A second order finite difference-spectral method for space fractional diffusion equations

A high order finite difference-spectral method is derived for solving space fractional diffusion equations,by combining the second order finite difference method in time and the spectral Galerkin method in space.The stability and error estimates of the temporal semidiscrete scheme are rigorously discussed,and the convergence order of the proposed method is proved to be O(τ2+Nα-m)in L2-norm,whereτ,N,αand m are the time step size,polynomial degree,fractional derivative index and regularity of the exact solution,respectively.Numerical experiments are carried out to demonstrate the theoretical analysis.     

A lumped mass nonconforming finite element method for nonlinear parabolic integro-differential equations on anisotropic meshes

A lumped mass approximation scheme of a low order Crouzeix-Raviart type noncon- forming triangular finite element is proposed to a kind of nonlinear parabolic integro-differential equations. The L2 error estimate is derived on anisotropic meshes without referring to the traditional nonclassical elliptic projection.     

A posteriori error estimation of the new mixed element schemes for second order elliptic problem on anisotropic meshes

This paper presents a posteriori residual error estimator for the new mixed element scheme for second order elliptic problem on anisotropic meshes. The reliability and efficiency of our estimator are established without any regularity assumption on the mesh.     

The Crouzeix-Raviart type nonconforming finite element method for the nonstationary Navier-Stokes equations on anisotropic meshes

This paper is devoted to study the Crouzeix-Raviart （C-R） type nonconforming linear triangular finite element method （FEM） for the nonstationary Navier-Stokes equations on anisotropic meshes. By intro- ducing auxiliary finite element spaces, the error estimates for the velocity in the L2-norm and energy norm, as well as for the pressure in the L2-norm are derived.     

A uniformly optimal‐order estimate for finite volume method for advection‐diffusion equations

We prove an optimal‐order error estimate in a weighted energy norm for finite volume method for two‐dimensional time‐dependent advection–diffusion equations on a uniform space‐time partition of the domain. The generic constants in the estimates depend only on certain norms of the true solution but not on the scaling parameter. These estimates, combined with a priori stability estimates of the governing partial differential equations with full regularity, yield a uniform estimate of the finite volume method, in which the generic constants depend only on the Sobolev norms of the initial and right side data but not on the scaling parameter. We use the interpolation of spaces and stability estimates to derive a uniform estimate for problems with minimal or intermediate regularity, where the convergence rates are proportional to certain Besov norms of the initial and right‐hand side data. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 17‐43, 2014     

A combined penalty function and gradient projection method for nonlinear programming

A new programming algorithm for nonlinear constrained optimization problems is proposed. The method is based on the penalty function approach and thereby circumyents the necessity to maintain feasibility at each iteration, but it also behaves much like the gradient projection method. Although only first-order information is used, the algorithm converges asymptotically at a rate which is independent of the magnitude of the penalty term; hence, unlike the simple gradient method, the asymptotic rate of the proposed method is not affected by the ill-conditioning associated with the introduction of the penalty term. It is shown that the asymptotic rate of convergence of the proposed method is identical with that of the gradient projection method.Dedicated to Professor M. R. HestenesThis research was supported by the National Science Foundation, Grant No. GK-16125.     

Gradient recovery type a posteriori error estimate for finite element approximation on non-uniform meshes

In this paper, we derive gradient recovery type a posteriori error estimate for the finite element approximation of elliptic equations. We show that a posteriori error estimate provide both upper and lower bounds for the discretization error on the non-uniform meshes. Moreover, it is proved that a posteriori error estimate is also asymptotically exact on the uniform meshes if the solution is smooth enough. The numerical results demonstrating the theoretical results are also presented in this paper.     

Calculating the vertex unknowns of nine point scheme on quadrilateral meshes for diffusion equation

In the construction of nine point scheme,both vertex unknowns and cell-centered unknowns are introduced,and the vertex unknowns are usually eliminated by using the interpolation of neighboring cell-centered unknowns,which often leads to lose accuracy.Instead of using interpolation,here we propose a different method of calculating the vertex unknowns of nine point scheme,which are solved independently on a new generated mesh.This new mesh is a Vorono¨i mesh based on the vertexes of primary mesh and some additional points on the interface.The advantage of this method is that it is particularly suitable for solving diffusion problems with discontinuous coeffcients on highly distorted meshes,and it leads to a symmetric positive definite matrix.We prove that the method has first-order convergence on distorted meshes.Numerical experiments show that the method obtains nearly second-order accuracy on distorted meshes.     

A fast dual proximal gradient algorithm for convex minimization and applications

We consider the convex composite problem of minimizing the sum of a strongly convex function and a general extended valued convex function. We present a dual-based proximal gradient scheme for solving this problem. We show that although the rate of convergence of the dual objective function sequence converges to the optimal value with the rate O(1/k²)$O(1/k^2)$, the rate of convergence of the primal sequence is of the order O(1/k)$O(1/k)$.     

The streamline-diffusion method for nonconforming Qrot1 elements on rectangular tensor-product meshes

When the streamline–diffusion finite element method isapplied to convection–diffusion problems using nonconformingtrial spaces, it has previously been observed that stabilityand convergence problems may occur. It has consequently beenproposed that certain jump terms should be added to the bilinearform to obtain the same stability and convergence behaviouras in the conforming case. The analysis in this paper showsthat for the Q^rot₁ 1 element on rectangular shape-regular tensor-productmeshes, no jump terms are needed to stabilize the method. Inthis case moreover, for smooth solutions we derive in the streamline–diffusionnorm convergence of order h^3/2 (uniformly in the diffusion coefficientof the problem), where h is the mesh diameter. (This estimateis already known for the conforming case.) Our analysis alsoshows that similar stability and convergence results fail tohold true for analogous piecewise linear nonconforming elements.