Preconditioning in H and applications

We consider the solution of the system of linear algebraic equations which arises from the finite element discretization of boundary value problems associated to the differential operator I. The natural setting for such problems is in the Hilbert space H and the variational formulation is based on the inner product in H. We show how to construct preconditioners for these equations using both domain decomposition and multigrid techniques. These preconditioners are shown to be spectrally equivalent to the inverse of the operator. As a consequence, they may be used to precondition iterative methods so that any given error reduction may be achieved in a finite number of iterations, with the number independent of the mesh discretization. We describe applications of these results to the efficient solution of mixed and least squares finite element approximations of elliptic boundary value problems.

     

Implicit-explicit multistep finite element methods for nonlinear parabolic problems

We approximate the solution of initial boundary value problems for nonlinear parabolic equations. In space we discretize by finite element methods. The discretization in time is based on linear multistep schemes. One part of the equation is discretized implicitly and the other explicitly. The resulting schemes are stable, consistent and very efficient, since their implementation requires at each time step the solution of a linear system with the same matrix for all time levels. We derive optimal order error estimates. The abstract results are applied to the Kuramoto-Sivashinsky and the Cahn-Hilliard equations in one dimension, as well as to a class of reaction diffusion equations in

     

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.

     

Numerical solution of a fast diffusion equation

In this paper, the authors consider the first boundary value problem for the nonlinear reaction diffusion equation: in , a smooth bounded domain in with the zero lateral boundary condition and with a positive initial condition, (fast diffusion problem), and . Sufficient conditions on the initial data are obtained for the solution to vanish or become infinite in a finite time. A scheme for the discretization in time of this problem is proposed. The numerical scheme preserves the essential properties of the initial problem; namely existence of an extinction or a blow-up time, for which estimates have been obtained. The convergence of the method is also proved.

     

A posteriori error estimation and adaptivity for degenerate parabolic problems

Two explicit error representation formulas are derived for degenerate parabolic PDEs, which are based on evaluating a parabolic residual in negative norms. The resulting upper bounds are valid for any numerical method, and rely on regularity properties of solutions of a dual parabolic problem in nondivergence form with vanishing diffusion coefficient. They are applied to a practical space-time discretization consisting of piecewise linear finite elements over highly graded unstructured meshes, and backward finite differences with varying time-steps. Two rigorous a posteriori error estimates are derived for this scheme, and used in designing an efficient adaptive algorithm, which equidistributes space and time discretization errors via refinement/coarsening. A simulation finally compares the behavior of the rigorous a posteriori error estimators with a heuristic approach, and hints at the potentials and reliability of the proposed method.

     

Optimal error estimate of the penalty finite element method for the time-dependent Navier-Stokes equations

A fully discrete penalty finite element method is presented for the two-dimensional time-dependent Navier-Stokes equations. The time discretization of the penalty Navier-Stokes equations is based on the backward Euler scheme; the spatial discretization of the time discretized penalty Navier-Stokes equations is based on a finite element space pair which satisfies some approximate assumption. An optimal error estimate of the numerical velocity and pressure is provided for the fully discrete penalty finite element method when the parameters and are sufficiently small.

     

Approximation of solution operators of elliptic partial differential equations by {\mathcal{H}}- and {\mathcal{H}^2}-matrices

We investigate the problem of computing the inverses of stiffness matrices resulting from the finite element discretization of elliptic partial differential equations. Since the solution operators are non-local, the inverse matrices will in general be dense, therefore representing them by standard techniques will require prohibitively large amounts of storage. In the field of integral equations, a successful technique for handling dense matrices efficiently is to use a data-sparse representation like the popular multipole method. In this paper we prove that this approach can be generalized to cover inverse matrices corresponding to partial differential equations by switching to data-sparse ${\mathcal{H}}$ - and ${\mathcal{H}^2}$ -matrices. The key results are existence proofs for local low-rank approximations of the solution operator and its discrete counterpart, which give rise to error estimates for ${\mathcal{H}}$ - and ${\mathcal{H}^2}$ -matrix approximations of the entire matrices.     

Multigrid and multilevel methods for nonconforming elements

In this paper we study theoretical properties of multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated finite elements in two space dimensions. In particular, for the case of square partitions and the Laplacian we derive properties of the associated intergrid transfer operators which allow us to prove convergence of the -cycle with any number of smoothing steps and close-to-optimal condition number estimates for -cycle preconditioners. This is in contrast to most of the other nonconforming finite element discretizations where only results for -cycles with a sufficiently large number of smoothing steps and variable -cycle multigrid preconditioners are available. Some numerical tests, including also a comparison with a preconditioner obtained by switching from the nonconforming rotated discretization to a discretization by conforming bilinear elements on the same partition, illustrate the theory.

     

A nonconforming combination of the finite element and volume methods with an anisotropic mesh refinement for a singularly perturbed convection-diffusion equation

In this paper we formulate and analyze a discretization method for a 2D linear singularly perturbed convection-diffusion problem with a singular perturbation parameter . The method is based on a nonconforming combination of the conventional Galerkin piecewise linear triangular finite element method and an exponentially fitted finite volume method, and on a mixture of triangular and rectangular elements. It is shown that the method is stable with respect to a semi-discrete energy norm and the approximation error in the semi-discrete energy norm is bounded by with independent of the mesh parameter , the diffusion coefficient and the exact solution of the problem.

     

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.

     

The space of complete minimal surfaces with finite total curvature as lagrangian submanifold

The space of nondegenerate, properly embedded minimal surfaces in with finite total curvature and fixed topology is an analytic lagrangian submanifold of , where is the number of ends of the surface. In this paper we give two expressions, one integral and the other pointwise, for the second fundamental form of this submanifold. We also consider the compact boundary case, and we show that the space of stable nonflat minimal annuli that bound a fixed convex curve in a horizontal plane, having a horizontal end of finite total curvature, is a locally convex curve in the plane .

     

A posteriori error estimates for upwind finite volume schemes for nonlinear conservation laws in multi dimensions

In this paper we shall derive a posteriori error estimates in the -norm for upwind finite volume schemes for the discretization of nonlinear conservation laws on unstructured grids in multi dimensions. This result is mainly based on some fundamental a priori error estimates published in a recent paper by C. Chainais-Hillairet. The theoretical results are confirmed by numerical experiments.

     

Constructive decomposition of functions of finite central mean oscillation

The space CMO of functions of finite central mean oscillation is an analogue of BMO where the condition that the sharp maximal function is bounded is replaced by the convergence of the sharp function at the origin. In this paper it is shown that each element of CMO is a singular integral image of an element of the Beurling space of functions whose Hardy-Littlewood maximal function converges at zero. This result is an analogue of Uchiyama's constructive decomposition of BMO in terms of singular integral images of bounded functions. The argument shows, in fact, that to each element of CMO one can construct a vector Calderón-Zygmund operator that maps that element into the proper subspace .

     

Robust norm equivalencies for diffusion problems

Additive multilevel methods offer an efficient way for the fast solution of large sparse linear systems which arise from a finite element discretization of an elliptic boundary value problem. These solution methods are based on multilevel norm equivalencies for the associated bilinear form using a suitable subspace decomposition. To obtain a robust iterative scheme, it is crucial that the constants in the norm equivalence do not depend or depend only weakly on the ellipticity constants of the problem.

In this paper we present such a robust norm equivalence for the model problem with a scalar diffusion coefficient in . Our estimates involve only very weak information about , and the results are applicable for a large class of diffusion coefficients. Namely, we require to be in the Muckenhoupt class , a function class well-studied in harmonic analysis.

The presented multilevel norm equivalencies are a main step towards the realization of an optimal and robust multilevel preconditioner for scalar diffusion problems.

     

Restriction matrices for numerically exploiting symmetry

In this paper we develop a technique for exploiting symmetry in the numerical treatment of boundary value problems (BVP) and eigenvalue problems which are invariant under a finite group of congruences of . This technique will be based upon suitable restriction matrices strictly related to a system of irreducible matrix representation of . Both Abelian and non-Abelian finite groups are considered. In the framework of symmetric Galerkin boundary element method (SGBEM), where the discretization matrices are typically full, to increase the computational gain we couple Panel Clustering Method [30] and Adaptive Cross Approximation algorithm [13] with restriction matrices introduced in this paper, showing some numerical examples. Applications of restriction matrices to SGBEM under the weaker assumption of partial geometrical symmetry, where the boundary has disconnected components, one of which is invariant, are proposed. The paper concludes with several numerical tests to demonstrate the effectiveness of the introduced technique in the numerical resolution of Dirichlet or Neumann invariant BVPs, in their differential or integral formulation.      

Analysis of a continuous finite element method for H(\mathrm{curl},\mathrm{div})-elliptic interface problem

In this paper, we develop a continuous finite element method for the curlcurl-grad div vector second-order elliptic problem in a three-dimensional polyhedral domain occupied by discontinuous nonhomogeneous anisotropic materials. In spite of the fact that the curlcurl-grad div interface problem is closely related to the elliptic interface problem of vector Laplace operator type, the continuous finite element discretization of the standard variational problem of the former generally fails to give a correct solution even in the case of homogeneous media whenever the physical domain has reentrant corners and edges. To discretize the curlcurl-grad div interface problem by the continuous finite element method, we apply an element-local $L^2$ projector to the curl operator and a pseudo-local $L^2$ projector to the div operator, where the continuous Lagrange linear element enriched by suitable element and face bubbles may be employed. It is shown that the finite element problem retains the same coercivity property as the continuous problem. An error estimate $\mathcal{O }(h^r)$ in an energy norm is obtained between the analytical solution and the continuous finite element solution, where the analytical solution is in $\prod _{l=1}^L (H^r(\Omega _l))^3$ for some $r\in (1/2,1]$ due to the domain boundary reentrant corners and edges (e.g., nonconvex polyhedron) and due to the interfaces between the different material domains in $\Omega =\bigcup _{l=1}^L \Omega _l$ .     

Nonconforming elements in least-squares mixed finite element methods

In this paper we analyze the finite element discretization for the first-order system least squares mixed model for the second-order elliptic problem by means of using nonconforming and conforming elements to approximate displacement and stress, respectively. Moreover, on arbitrary regular quadrilaterals, we propose new variants of both the rotated nonconforming element and the lowest-order Raviart-Thomas element.

     

Canonical construction of finite elements

The mixed variational formulation of many elliptic boundary value problems involves vector valued function spaces, like, in three dimensions, and . Thus finite element subspaces of these function spaces are indispensable for effective finite element discretization schemes. Given a simplicial triangulation of the computational domain , among others, Raviart, Thomas and Nédélec have found suitable conforming finite elements for and . At first glance, it is hard to detect a common guiding principle behind these approaches. We take a fresh look at the construction of the finite spaces, viewing them from the angle of differential forms. This is motivated by the well-known relationships between differential forms and differential operators: , and can all be regarded as special incarnations of the exterior derivative of a differential form. Moreover, in the realm of differential forms most concepts are basically dimension-independent. Thus, we arrive at a fairly canonical procedure to construct conforming finite element subspaces of function spaces related to differential forms. In any dimension we can give a simple characterization of the local polynomial spaces and degrees of freedom underlying the definition of the finite element spaces. With unprecedented ease we can recover the familiar - and -conforming finite elements, and establish the unisolvence of degrees of freedom. In addition, the use of differential forms makes it possible to establish crucial algebraic properties of the canonical interpolation operators and representation theorems in a single sweep for all kinds of spaces.

     

Two classes of special functions using Fourier transforms of some finite classes of classical orthogonal polynomials

Some orthogonal polynomial systems are mapped onto each other by the Fourier transform. The best-known example of this type is the Hermite functions, i.e., the Hermite polynomials multiplied by , which are eigenfunctions of the Fourier transform. In this paper, we introduce two new examples of finite systems of this type and obtain their orthogonality relations. We also estimate a complicated integral and propose a conjecture for a further example of finite orthogonal sequences.

     

Maximum norm stability of difference schemes for parabolic equations on overset nonmatching space-time grids

In this paper, theoretical results are described on the maximum norm stability and accuracy of finite difference discretizations of parabolic equations on overset nonmatching space-time grids. We consider parabolic equations containing a linear reaction term on a space-time domain which is decomposed into an overlapping collection of cylindrical subregions of the form , for . Each of the space-time domains are assumed to be independently grided (in parallel) according to the local geometry and space-time regularity of the solution, yielding space-time grids with mesh parameters and . In particular, the different space-time grids need not match on the regions of overlap, and the time steps can differ from one grid to the next. We discretize the parabolic equation on each local grid by employing an explicit or implicit -scheme in time and a finite difference scheme in space satisfying a discrete maximum principle. The local discretizations are coupled together, without the use of Lagrange multipliers, by requiring the boundary values on each space-time grid to match a suitable interpolation of the solution on adjacent grids. The resulting global discretization yields a large system of coupled equations which can be solved by a parallel Schwarz iterative procedure requiring some communication between adjacent subregions. Our analysis employs a contraction mapping argument.

Applications of the results are briefly indicated for reaction-diffusion equations with contractive terms and heterogeneous hyperbolic-parabolic approximations of parabolic equations.