On the reference mapping for quadrilateral and hexahedral finite elements on multilevel adaptive grids

We study the properties of the reference mapping for quadrilateral and hexahedral finite elements. We consider multilevel adaptive grids with possibly hanging nodes which are typically generated by adaptive refinement starting from a regular coarse grid. It turns out that for such grids the reference mapping behaves – up to a perturbation depending on the mesh size – like an affine mapping. As an application, we prove optimal estimates of the interpolation error for discontinuous mapped -elements on quadrilateral and hexahedral grids.     

Multilevel Gauging for Edge Elements

The vector potential of a solenoidal vector field, if it exists, is not unique in general. Any procedure that aims to determine such a vector potential typically involves a decision on how to fix it. This is referred to by the term gauging. Gauging is an important issue in computational electromagnetism, whenever discrete vector potentials have to be computed. In this paper a new gauging algorithm for discrete vector potentials is introduced that relies on a hierarchical multilevel decomposition. With minimum computational effort it yields vector potentials whose L ²-norm does not severely blow up. Thus the new approach compares favorably to the widely used co-tree gauging. Received May 27, 1999; revised October 22, 1999     

Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients

We present a method for discretizing and solving general elliptic partial differential equations on sparse grids employing higher order finite elements. On the one hand, our approach is charactarized by its simplicity. The calculation of the occurring functionals is composed of basic pointwise or unidirectional algorithms. On the other hand, numerical experiments prove our method to be robust and accurate. Discontinuous coefficients can be treated as well as curvilinearly bounded domains. When applied to adaptively refined sparse grids, our discretization results to be highly efficient, yielding balanced errors on the computational domain.     

Nitsche Type Mortaring for Singularly Perturbed Reaction-diffusion Problems

The paper is concerned with the Nitsche mortaring in the framework of domain decomposition where non-matching meshes and weak continuity of the finite element approximation at the interface are admitted. The approach is applied to singularly perturbed reaction-diffusion problems in 2D. Non-matching meshes of triangles being anisotropic in the boundary layers are applied. Some properties as well as error estimates of the Nitsche mortar finite element schemes are proved. In particular, using a suitable degree of anisotropy of triangles in the boundary layers of a rectangle, convergence rates as known for the conforming finite element method are derived. Numerical examples illustrate the approach and the results.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

BDDC and FETI-DP preconditioners for spectral element discretizations

Two of the most recent and important nonoverlapping domain decomposition methods, the BDDC method (Balancing Domain Decomposition by Constraints) and the FETI-DP method (Dual-Primal Finite Element Tearing and Interconnecting) are here extended to spectral element discretizations of second-order elliptic problems. In spite of the more severe ill-conditioning of the spectral element discrete systems, compared with low-order finite elements and finite differences, these methods retain their good properties of scalability, quasi-optimality and independence on the discontinuities of the elliptic operator coefficients across subdomain interfaces.     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

Hierarchical and adaptive visualization on nested grids

Modern numerical methods are capable to resolve fine structures in solutions of partial differential equations. Thereby they produce large amounts of data. The user wants to explore them interactively by applying visualization tools in order to understand the simulated physical process. Here we present a multiresolution approach for a large class of hierarchical and nested grids. It is based on a hierarchical traversal of mesh elements combined with an adaptive selection of the hierarchical depth. The adaptation depends on an error indicator which is closely related to the visual impression of the smoothness of isosurfaces or isolines, which are typically used to visualize data. Significant examples illustrate the applicability and efficiency on different types of meshes.     

<Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript>-interpolation on quadrilateral and hexahedral meshes with hanging nodes

We propose a Scott-Zhang type finite element interpolation operator of first order for the approximation of H ¹-functions by means of continuous piecewise mapped bilinear or trilinear polynomials. The novelty of the proposed interpolation operator is that it is defined for general non-affine equivalent quadrilateral and hexahedral elements and so-called 1-irregular meshes with hanging nodes. We prove optimal local approximation properties of this interpolation operator for functions in H ¹. As necessary ingredients we provide a definition of a hanging node and a rigorous analysis of the issue of constrained approximation which cover both the two- and three-dimensional case in a unified fashion.      

A Domain Decomposition Preconditioner for p-FEM Discretizations of Two-dimensional Elliptic Problems

In this paper, a uniformly elliptic second order boundary value problem in 2-D discretized by the p-version of the finite element method is considered. An inexact Dirichlet-Dirichlet domain decomposition pre-conditioner for the system of linear algebraic equations is investigated. Two solvers for the problem in the sub-domains, a pre-conditioner for the Schur-complement and an extension operator operating from the edges of the elements into the interior are proposed as ingredients for the inexact DD-pre-conditioner. In the main part of the paper, several numerical experiments on a parallel computer are given.     

Numerical Integrations and Unit Resolution Multipliers for Domain Decomposition Methods with Nonmatching Grids

In this paper, we are concerned with the non-overlapping domain decomposition method (DDM) with nonmatching grids for three-dimensional problems. The weak continuity of the DDM solution on the interface is imposed by some Lagrange multiplier. We shall first analyze the influence of the numerical integrations over the interface on the (non-conforming) approximate solution. Then we will propose a simple approach to construct multiplier spaces, one of which can be simply spanned by some smooth basis functions with local compact supports, and thus makes the numerical integrations on the interface rather simple and inexpensive. Also it is shown this multiplier space can generate an optimal approximate solution. Numerical results are presented to compare the new method with the point to point method widely used in engineering.     

Anisotropic interpolation error estimates for isoparametric quadrilateral finite elements

Anisotropic local interpolation error estimates are derived for quadrilateral and hexahedral Lagrangian finite elements with straight edges. These elements are allowed to have diameters with different asymptotic behaviour in different space directions. The case of affine elements (parallel-epipeds) with arbitrarily high degree of the shape functions is considered first. Then, a careful examination of the multi-linear map leads to estimates for certain classes of more general, isoparametric elements. As an application, the Galerkin finite element method for a reaction diffusion problem in a polygonal domain is considered. The boundary layers are resolved using anisotropic trapezoidal elements.     

Non-Reflecting Boundary Conditions for Maxwell’s Equations

A new discrete non-reflecting boundary condition for the time-dependent Maxwell equations describing the propagation of an electromagnetic wave in an infinite homogenous lossless rectangular waveguide with perfectly conducting walls is presented. It is derived from a virtual spatial finite difference discretization of the problem on the unbounded domain. Fourier transforms are used to decouple transversal modes. A judicious combination of edge based nodal values permits us to recover a simple structure in the Laplace domain. Using this, it is possible to approximate the convolution in time by a similar fast convolution algorithm as for the standard wave equation.     

Application of an Adaptive Sparse-Grid Technique to a Model Singular Perturbation Problem

In this paper we show how, under minimal conditions, a combination extrapolation can be introduced for an adaptive sparse grid. We apply this technique for the solution of a two-dimensional model singular perturbation problem, defined on the domain exterior of a circle. Received October 18, 1999     

Problem Dependent Generalized Prewavelets

In this paper, we present a new approach to construct robust multilevel algorithms for elliptic differential equations. The multilevel algorithms consist of multiplicative subspace corrections in spaces spanned by problem dependent generalized prewavelets. These generalized prewavelets are constructed by a local orthogonalization of hierarchical basis functions with respect to a so-called local coarse-grid space. Numerical results show that the local orthogonalization leads to a smaller constant in strengthened Cauchy-Schwarz inequality than the original hierarchical basis functions. This holds also for several equations with discontinuous coefficients. Thus, the corresponding multilevel algorithm is a fast and robust iterative solver. Received November 13, 2001; revised October 21, 2002 Published online: December 12, 2002     

Goal-oriented a posteriori error estimates for transport problems

Some aspects of goal-oriented a posteriori error estimation are addressed in the context of steady convection–diffusion equations. The difference between the exact and approximate values of a linear target functional is expressed in terms of integrals that depend on the solutions to the primal and dual problems. Gradient averaging techniques are employed to separate the element residual and diffusive flux errors without introducing jump terms. The dual solution is computed numerically and interpolated using higher-order basis functions. A node-based approach to localization of global errors in the quantities of interest is pursued. A possible violation of Galerkin orthogonality is taken into account. Numerical experiments are performed for centered and upwind-biased approximations of a 1D boundary value problem.     

Fast Summation of Radial Functions on the Sphere

Radial functions are a powerful tool in many areas of multi-dimensional approximation, especially when dealing with scattered data. We present a fast approximate algorithm for the evaluation of linear combinations of radial functions on the sphere . The approach is based on a particular rank approximation of the corresponding Gram matrix and fast algorithms for spherical Fourier transforms. The proposed method takes (L) arithmetic operations for L arbitrarily distributed nodes on the sphere. In contrast to other methods, we do not require the nodes to be sorted or pre-processed in any way, thus the pre-computation effort only depends on the particular radial function and the desired accuracy. We establish explicit error bounds for a range of radial functions and provide numerical examples covering approximation quality, speed measurements, and a comparison of our particular matrix approximation with a truncated singular value decomposition.     

Nitsche Type Mortaring for some Elliptic Problem with Corner Singularities

The paper deals with Nitsche type mortaring as a finite element method (FEM) for treating non-matching meshes of triangles at the interface of some domain decomposition. The approach is applied to the Poisson equation with Dirichlet boundary conditions (as a model problem) under the aspect that the interface passes re-entrant corners of the domain. For such problems and non-matching meshes with and without local refinement near the re-entrant corner, some properties of the finite element scheme and error estimates are proved. They show that appropriate mesh grading yields convergence rates as known for the classical FEM in presence of regular solutions. Finally, a numerical example illustrates the approach and the theoretical results. Received July 5, 2001; revised February 5, 2002 Published online April 25, 2002     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Applications of -Matrix Techniques in Micromagnetics

The variational model by Landau and Lifshitz is frequently used in the simulation of stationary micromagnetic phenomena. We consider the limit case of large and soft magnetic bodies, treating the associated Maxwell equation exactly via an integral operator . In numerical simulations of the resulting minimization problem, difficulties arise due to the imposed side-constraint and the unboundedness of the domain. We introduce a possible discretization by a penalization strategy. Here the computation of is numerically the most challenging issue, as it leads to densely populated matrices. We show how an efficient treatment of both and the corresponding bilinear form can be achieved by application of -matrix techniques.