The Frequency Decomposition Multilevel Method: A robust additive hierarchical basis preconditioner

Hackbusch's frequency decomposition multilevel method is characterized by the application of three additional coarse-grid corrections in parallel to the standard one. Each coarse-grid correction was designed to damp errors from a different part of the frequency spectrum. In this paper, we introduce a cheap variant of this method, partly based on semicoarsening, which demands fewer recursive calls than the original version. Using the theory of the additive Schwarz methods, we will prove robustness of our method as a preconditioner applied to anisotropic equations.

     

An efficient hierarchical preconditioner for quadratic discretizations of finite element problems

Higher order finite element discretizations, although providing higher accuracy, are considered to be computationally expensive and of limited use for large‐scale problems. In this paper, we have developed an efficient iterative solver for solving large‐scale quadratic finite element problems. The proposed approach shares some common features with geometric multigrid methods but does not need structured grids to create the coarse problem. This leads to a robust method applicable to finite element problems discretized by unstructured meshes such as those from adaptive remeshing strategies. The method is based on specific properties of hierarchical quadratic bases. It can be combined with an algebraic multigrid (AMG) preconditioner or with other algebraic multilevel block factorizations. The algorithm can be accelerated by flexible Krylov subspace methods. We present some numerical results on the convection–diffusion and linear elasticity problems to illustrate the efficiency and the robustness of the presented algorithm. In these experiments, the performance of the proposed method is compared with that of an AMG preconditioner and other iterative solvers. Our approach requires less computing time and less memory storage. Copyright © 2010 John Wiley & Sons, Ltd.     

Rapid error reduction for block Gauss–Seidel based on p‐hierarchical basis

We consider a two‐level block Gauss–Seidel iteration for solving systems arising from finite element discretizations employing higher‐order elements. A p‐hierarchical basis is used to induce this block structure. Using superconvergence results normally employed in the analysis of gradient recovery schemes, we argue that a massive reduction of the H¹‐error occurs in the first iterate, so that the discrete solution is adequately resolved in very few iterates—sometimes a single iteration is sufficient. Numerical experiments on uniform and adapted meshes support these claims. Copyright © 2012 John Wiley & Sons, Ltd.     

A two-level additive Schwarz preconditioner for the stationary Stokes equations

We consider the stationary Stokes equations on a polygonal domain whose boundary has more than one component, i.e., flow with obstacles. A two-level additive Schwarz preconditioner is developed for the divergence-free nonconforming P1 finite element. The condition number of the preconditioned system is shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.This work was supported in part by the National Science Foundation under Grant Nos. DMS-92-09332 and DMS-94-96275.     

Weak Galerkin finite element methods for the biharmonic equation on polytopal meshes

A new weak Galerkin (WG) finite element method is introduced and analyzed in this article for the biharmonic equation in its primary form. This method is highly robust and flexible in the element construction by using discontinuous piecewise polynomials on general finite element partitions consisting of polygons or polyhedra of arbitrary shape. The resulting WG finite element formulation is symmetric, positive definite, and parameter‐free. Optimal order error estimates in a discrete H² norm is established for the corresponding WG finite element solutions. Error estimates in the usual L² norm are also derived, yielding a suboptimal order of convergence for the lowest order element and an optimal order of convergence for all high order of elements. Numerical results are presented to confirm the theory of convergence under suitable regularity assumptions. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 1003–1029, 2014     

Multilevel preconditioners for discretizations of the biharmonic equation by rectangular finite elements

Recently, some new multilevel preconditioners for solving elliptic finite element discretizations by iterative methods have been proposed. They are based on appropriate splittings of the finite element spaces under consideration, and may be analyzed within the framework of additive Schwarz schemes. In this paper we discuss some multilevel methods for discretizations of the fourth-order biharmonic problem by rectangular elements and derive optimal estimates for the condition numbers of the preconditioned linear systems. For the Bogner–Fox–Schmit rectangle, the generalization of the Bramble–Pasciak–Xu method is discussed. As a byproduct, an optimal multilevel preconditioner for nonconforming discretizations by Adini elements is also derived.     

Remarks on Multilevel Bases for Divergence-Free Finite Elements

The connection between the multilevel factorization method recently proposed by Sarin and Sameh for solving mixed discretizations of the Stokes equation using a divergence-free finite element formulation, and hierarchical basis preconditioners for the Poisson problem is established. For the 2D triangular Taylor–Hood element, a preconditioner is proposed that could be useful in fractional step methods.     

Hierarchical Riesz Bases for Hs(Ω), 1 < s < 5/2

On arbitrary polygonal domains $\Omega \subset \RR^2$, we construct $C^1$ hierarchical Riesz bases for Sobolev spaces $H^s(\Omega)$. In contrast to an earlier construction by Dahmen, Oswald, and Shi (1994), our bases will be of Lagrange instead of Hermite type, by which we extend the range of stability from $s \in (2,\frac{5}{2})$ to $s \in (1,\frac{5}{2})$. Since the latter range includes $s=2$, with respect to the present basis, the stiffness matrices of fourth-order elliptic problems are uniformly well-conditioned.     

A third-order mixed finite-element method for the numerical solution of the biharmonic problem

This paper is devoted to the introduction of a mixed finite element for the solution of the biharmonic problem. We prove optimal rate of convergence for the element. The mixed approach allows the simultaneous approximation of both displacement and tensor of its second derivatives.     

Some remarks on the constant in the strengthened CBS inequality: Estimate for hierarchical finite element discretizations of elasticity problems

For a class of two‐dimensional boundary value problems including diffusion and elasticity problems, it is proved that the constants in the corresponding strengthened Cauchy‐Buniakowski‐Schwarz (CBS) inequality in the cases of two‐level hierarchical piecewise‐linear/piecewise‐linear and piecewise‐linear/piecewise‐quadratic finite element discretizations with triangular meshes differ by the factor 0.75. For plane linear elasticity problems and triangulations with right isosceles triangles, formulas are presented that show the dependence of the constant in the CBS inequality on the Poisson's ratio. Furthermore, numerically determined bounds of the constant in the CBS inequality are given for plane linear elasticity problems discretized by means of arbitrary triangles and for three‐dimensional elasticity problems discretized by means of tetrahedral elements. Finally, the robustness of iterative solvers for elasticity problems is discussed briefly. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 469–487, 1999     

Residual‐based a posteriori error estimator for the mixed finite element approximation of the biharmonic equation

A reliable and efficient residual‐based a posteriori error estimator is derived for the Ciarlet‐Raviart mixed finite element method for the biharmonic equation on polygonal domains. The performance of the estimator is illustrated by numerical experiments. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

A stable, direct solver for the gradient equation

A new finite element discretization of the equation is introduced. This discretization gives rise to an invertible system that can be solved directly, requiring a number of operations proportional to the number of unknowns. We prove an optimal error estimate, and furthermore show that the method is stable with respect to perturbations of the right-hand side . We discuss a number of applications related to the Stokes equations.

     

A numerical scheme based on mean value solutions for the helmholtz equation on triangular grids

A numerical treatment for the Dirichlet boundary value problem on regular triangular grids for homogeneous Helmholtz equations is presented, which also applies to the convection-diffusion problems. The main characteristic of the method is that an accuracy estimate is provided in analytical form with a better evaluation than that obtained with the usual finite difference method. Besides, this classical method can be seen as a truncated series approximation to the proposed method. The method is developed from the analytical solutions for the Dirichlet problem on a ball together with an error evaluation of an integral on the corresponding circle, yielding accuracy. Some numerical examples are discussed and the results are compared with other methods, with a consistent advantage to the solution obtained here.

     

A direct approach to the finite element solution of elliptic optimal control problems

A general framework is developed for the finite element solution of optimal control problems governed by elliptic nonlinear partial differential equations. Typical applications are steady‐state problems in nonlinear continuum mechanics, where a certain property of the solution (a function of displacements, temperatures, etc.) is to be minimized by applying control loads. In contrast to existing formulations, which are based on the “adjoint state,” the present formulation is a direct one, which does not use adjoint variables. The formulation is presented first in a general nonlinear setting, then specialized to a case leading to a sequence of quadratic programming problems, and then specialized further to the unconstrained case. Linear governing partial differential equations are also considered as a special case in each of these categories. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15:371–388, 1999     

A robust optimal preconditioner for the mixed finite element discretization of elliptic optimal control problems

In this paper, we consider the efficient solving of the resulting algebraic system for elliptic optimal control problems with mixed finite element discretization. We propose a block‐diagonal preconditioner for the symmetric and indefinite algebraic system solved with minimum residual method, which is proved to be robust and optimal with respect to both the mesh size and the regularization parameter. The block‐diagonal preconditioner is constructed based on an isomorphism between appropriately chosen solution space and its dual for a general control problem with both state and gradient state observations in the objective functional. Numerical experiments confirm the efficiency of our proposed preconditioner.     

An overlapping additive Schwarz preconditioner for interpolation on the unit sphere with spherical radial basis functions

The problem of interpolation of scattered data on the unit sphere has many applications in geodesy and Earth science in which the sphere is taken as a model for the Earth. Spherical radial basis functions provide a convenient tool for constructing the interpolant. However, the underlying linear systems tend to be ill-conditioned. In this paper, we present an additive Schwarz preconditioner for accelerating the solution process. An estimate for the condition number of the preconditioned system will be discussed. Numerical experiments using MAGSAT satellite data will be presented.     

Uniform l1 behaviour for time discretization of a Volterra equation with completely monotonic kernel: I. stability

This paper is the first of two papers on the time discretizationof the equation u_t + ^t ₀ ß (t — s) Au (s) ds= 0, t > 0, u (0) = u₀, where A is a self-adjoint denselydefined linear operator on a Hilbert space H with a completeeigensystem {_m, _m}_{m = 1}, and ß (t) is completely monotonicand locally integrable, but not constant. The equation is discretizedin time using first-order differences in combination with order-oneconvolution quadrature. The stability properties of the timediscretization are derived in the l¹_t (0, ; H) norm.     

Algorithm for constructing range restricted histosplines

This paper is concerned with numerical methods in range restricted histopolation. The proposal is to apply splines on refined grids. The ratios of the added split points are considered to be parameters. In this way, by choosing suitable spline classes, range restricted histosplines can always be constructed if the restrictions are compatible with the given histogram. We offer an algorithm for solving the bivariate problem on a rectangular grid which utilizes univariate results as well as tensor product techniques. This revised version was published online in June 2006 with corrections to the Cover Date.     

Composite‐grid multigrid for diffusion on the sphere

Recently, there has been much interest in the solution of differential equations on surfaces and manifolds, driven by many applications whose dynamics take place on such domains. Although increasingly powerful algorithms have been developed in this field, many straightforward questions remain, particularly in the area of coupling advanced discretizations with efficient linear solvers. In this paper, we develop a structured refinement algorithm for octahedral triangulations of the surface of the sphere. We explain the composite‐grid finite‐element discretization of the Laplace–Beltrami operator on such triangulations and extend the fast adaptive composite‐grid scheme to provide an efficient solution of the resulting linear system. Supporting numerical examples are presented, including the recovery of second‐order accuracy in the case of a nonsmooth solution.     

A class of singular integrals on then-complex unit sphere

The operaton on the n-complex unit sphere under study have three forms: the singular integrals with holomorphic kernels, the bounded and holomorphic Fourier multipliers, and the Cauchy-Dunford bounded and holomorphic functional calculus of the radial Dirac operator $D = \sum\nolimits_{k = 1}^n {z_k \frac{\partial }{{\partial _{z_k } }}} $ . The equivalence between the three fom and the strong-type (p,p), 1 <p < ∞, and weak-type (1,1)-boundedness of the operators is proved. The results generalise the work of L. K. Hua, A. Korányli and S. Vagi, W. Rudin and S. Gong on the Cauchy-Szegö, kemel and the Cauchy singular integral operator.