A Numerical Method to Verify the Invertibility of Linear Elliptic Operators with Applications to Nonlinear Problems

In this paper, we propose a numerical method to verify the invertibility of second-order linear elliptic operators. By using the projection and the constructive a priori error estimates, the invertibility condition is formulated as a numerical inequality based upon the existing verification method originally developed by one of the authors. As a useful application of the result, we present a new verification method of solutions for nonlinear elliptic problems, which enables us to simplify the verification process. Several numerical examples that confirm the actual effectiveness of the method are presented.     

A Hermitian Box-scheme for One-dimensional Elliptic Equations – Application to Problems with High Contrasts in the Ellipticity

We introduce a new box-scheme, called ``hermitian box-scheme' on the model of the one-dimensional Poisson problem. The scheme combines features of the box-scheme of Keller, [20], [13], with the hermitian approximation of the gradient on a compact stencil, which is characteristic of compact schemes, [9], [21]. The resulting scheme is proved to be 4th order accurate for the primitive unknown u and its gradient p. The proved convergence rate is 1.5 for (u,p) in the discrete L ² norm. The connection with a non standard mixed finite element method is given. Finally, numerical results are displayed on pertinent 1-D elliptic problems with high contrasts in the ellipticity, showing in practice convergence rates ranging from 1 to 2.5 in the discrete H ¹ norm. This work has been performed with the support of the GDR MOMAS, (ANDRA, CEA, EDF, BRGM and CNRS): Modélisation pour le stockage des déchets radioactifs. The author thanks especially A. Bourgeat for his encouragements and his interest in this work.     

Spectral Galerkin Discretization for Hydrodynamic Stability Problems

A spectral Galerkin discretization for calculating the eigenvalues of the Orr-Sommerfeld equation is presented. The matrices of the resulting generalized eigenvalue problem are sparse. A convergence analysis of the method is presented which indicates that a) no spurious eigenvalues occur and b) reliable results can only be expected under the assumption of scale resolution, i.e., that Re/p ² is small; here Re is the Reynolds number and p is the spectral order. Numerical experiments support that the assumption of scale resolution is necessary in order to obtain reliable results. Exponential convergence of the method is shown theoretically and observed numerically. Received November 11, 1998; revised March 1, 2000     

Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

A Time Domain Point Source Method for Inverse Scattering by Rough Surfaces

In this paper we propose a new method to determine the location and shape of an unbounded rough surface from measurements of scattered electromagnetic waves. The proposed method is based on the point source method of Potthast (IMA J. Appl. Math. 61, 119–140, 1998) for inverse scattering by bounded obstacles. We propose a version for inverse rough surface scattering which can reconstruct the total field when the incident field is not necessarily time harmonic. We present numerical results for the case of a perfectly conducting surface in TE polarization, in which case a homogeneous Dirichlet condition applies on the boundary. The results show great accuracy of reconstruction of the total field and of the prediction of the surface location.     

Two-Level Additive Schwarz Preconditioners for the h-p Version of the Galerkin Boundary Element Method for 2-d Problems

We study two-level additive Schwarz preconditioners for the h-p version of the Galerkin boundary element method when used to solve hypersingular integral equations of the first kind, which arise from the Neumann problems for the Laplacian in two dimensions. Overlapping and non-overlapping methods are considered. We prove that the non-overlapping preconditioner yields a system of equations having a condition number bounded by   where H _i is the length of the i-th subdomain, h _i is the maximum length of the elements in this subdomain, and p is the maximum polynomial degree used. For the overlapping method, we prove that the condition number is bounded by   where δ is the size of the overlap and H=max _i H _i . We also discuss the use of the non-overlapping method when the mesh is geometrically graded. The condition number in that case is bounded by clog² M, where M is the degrees of freedom. Received October 27, 2000, revised March 26, 2001     

A Numerical Method to Verify the Elliptic Eigenvalue Problems Including a Uniqueness Property

We propose a numerical method to enclose the eigenvalues and eigenfunctions of second-order elliptic operators with local uniqueness. We numerically construct a set containing eigenpairs which satisfies the hypothesis of Banach's fixed point theorem in a certain Sobolev space by using a finite element approximation and constructive error estimates. We then prove the local uniqueness separately of eigenvalues and eigenfunctions. This local uniqueness assures the simplicity of the eigenvalue. Numerical examples are presented. Received: November 2, 1998; revised June 5, 1999     

High-Order Time-Accurate Parallel Schemes for Parabolic Singularly Perturbed Problems with Convection

The first boundary value problem for a singularly perturbed parabolic equation of convection-diffusion type on an interval is studied. For the approximation of the boundary value problem we use earlier developed finite difference schemes, ɛ-uniformly of a high order of accuracy with respect to time, based on defect correction. New in this paper is the introduction of a partitioning of the domain for these ɛ-uniform schemes. We determine the conditions under which the difference schemes, applied independently on subdomains may accelerate (ɛ-uniformly) the solution of the boundary value problem without losing the accuracy of the original schemes. Hence, the simultaneous solution on subdomains can in principle be used for parallelization of the computational method. Received December 3, 1999; revised April 20, 2000     

Superconvergence of a Mixed Covolume Method for Elliptic Problems

We consider a mixed covolume method for a system of first order partial differential equations resulting from the mixed formulation of a general self-adjoint elliptic problem with a variable full diffusion tensor. The system can be used to model the transport of a contaminant carried by a flow. We use the lowest order Raviart-Thomas mixed finite element space. We show the first order convergence in L ² norm and the superconvergence in certain discrete norms both for the pressure and velocity. Finally some numerical examples illustrating the error behavior of the scheme are provided. Supported by the National Natural Science Foundation of China under grant No. 10071044 and the Research Fund of Doctoral Program of High Education by State Education Ministry of China.     

Domain decomposition methods for the neutron diffusion problem

The neutronic simulation of a nuclear reactor core is performed using the neutron transport equation, and leads to an eigenvalue problem in the steady-state case. Among the deterministic resolution methods, simplified transport (S_PN$S{P}_N$) or diffusion approximations are often used. The MINOS solver developed at CEA Saclay uses a mixed dual finite element method for the resolution of these problems, and has shown his efficiency. In order to take into account the heterogeneities of the geometry, a very fine mesh is generally required, and leads to expensive calculations for industrial applications. In order to take advantage of parallel computers, and to reduce the computing time and the local memory requirement, we propose here two domain decomposition methods based on the MINOS solver. The first approach is a component mode synthesis method on overlapping subdomains: several eigenmodes solutions of a local problem on each subdomain are taken as basis functions used for the resolution of the global problem on the whole domain. The second approach is an iterative method based on a non-overlapping domain decomposition with Robin interface conditions. At each iteration, we solve the problem on each subdomain with the interface conditions given by the solutions on the adjacent subdomains estimated at the previous iteration. Numerical results on parallel computers are presented for the diffusion model on realistic 2D and 3D cores.     

Using integral equations and the immersed interface method to solve immersed boundary problems with stiff forces

We propose a fast, explicit numerical method for computing approximations for the immersed boundary problem in which the boundaries that separate the fluid into two regions are stiff. In the numerical computations of such problems, one frequently has to contend with numerical instability, as the stiff immersed boundaries exert large forces on the local fluid. When the boundary forces are treated explicitly, prohibitively small time-steps may be required to maintain numerical stability. On the other hand, when the boundary forces are treated implicitly, the restriction on the time-step size is reduced, but the solution of a large system of coupled non-linear equations may be required. In this work, we develop an efficient method that combines an integral equation approach with the immersed interface method. The present method treats the boundary forces explicitly. To reduce computational costs, the method uses an operator-splitting approach: large time-steps are used to update the non-stiff advection terms, and smaller substeps are used to advance the stiff boundary. At each substep, an integral equation is computed to yield fluid velocity local to the boundary; those velocity values are then used to update the boundary configuration. Fluid variables are computed over the entire domain, using the immersed interface method, only at the end of the large advection time-steps. Numerical results suggest that the present method compares favorably with an implementation of the immersed interface method that employs an explicit time-stepping and no fractional stepping.     

A Refined Finite Element Convergence Theory for Highly Indefinite Helmholtz Problems

It is well known that standard h-version finite element discretisations using lowest order elements for Helmholtz' equation suffer from the following stability condition: ``The mesh width h of the finite element mesh has to satisfy k <sup>2</sup> h≲1', where k denotes the wave number. This condition rules out the reliable numerical solution of Helmholtz equation in three dimensions for large wave numbers k≳50. In our paper, we will present a refined finite element theory for highly indefinite Helmholtz problems where the stability of the discretisation can be checked through an ``almost invariance' condition. As an application, we will consider a one-dimensional finite element space for the Helmholtz equation and apply our theory to prove stability under the weakened condition hk≲1 and optimal convergence estimates. Dedicated to Prof. Dr. Ivo Babuška on the occasion of his 80th birthday.     

On the existence and convergence of the solution of PML equations

In this article we study the mesh termination method in computational scattering theory known as the method of Perfectly Matched Layer (PML). This method is based on the idea of surrounding the scatterer and its immediate vicinity with a fictitious absorbing non-reflecting layer to damp the echoes coming from the mesh termination surface. The method can be formulated equivalently as a complex stretching of the exterior domain. The article is devoted to the existence and convergence questions of the solutions of the resulting equations. We show that with a special choice of the fictitious absorbing coefficient, the PML equations are solvable for all wave numbers, and as the PML layer is made thicker, the PML solution converge exponentially towards the actual scattering solution. The proofs are based on boundary integral methods and a new type of near-field version of the radiation condition, called here the double surface radiation condition. Partly supported by the Finnish Academy, project 37692.     

On the inf–sup Condition for the P mod 3 / P disc 2 Element

We consider a recently introduced triangular nonconforming finite element of third-order accuracy in the energy norm called P^mod₃ element. We show that this finite element is appropriate for approximating the velocity in incompressible flow problems since it satisfies an inf-sup condition for discontinuous piecewise quadratic pressures.     

Parallel adaptive time domain decomposition for stiff systems of ODEs/DAEs

Time domain decompositions to solve ODEs/DAEs have been numerically investigated by introducing adaptivity in the definition of the refinement of the time grid, time domain splitting. We show that the parareal method [Lions J-L, Maday Y, Turinici G. Résolution d’EDP par un schéma en temps “pararéel”, CRAS Sér I Math 2000;332(7):661-8] is a particular case of the multiple shooting method of Deuflhard. Numerical evidences of the limitation of this method to solve very stiff problems are exhibited, leading us to propose an adaptive parallel extrapolation method.     

A variational approximation method for 2nd order elliptic eigenvalue problems in a composite structure with nonstandard boundary conditions

In this paper we deal with the finite element analysis of a class of eigenvalue problems (EVPs) in a composite structure in the plane, consisting of rectangular subdomains which enclose an intermediate region. Nonlocal boundary conditions (BCs) of Robin type are imposed on the inner boundaries, i.e. on the interfaces of the respective subdomains with the intermediate region. On the eventual interfaces between two subdomains we impose discontinuous transition conditions (TCs). Finally, we have classical local BCs at the outer boundaries. Such problems are related to some heat transfer problems e.g. in a horizontal cross section of a wall enclosing an air cave.     

Parallel -Matrix Arithmetics on Shared Memory Systems

-matrices, as they were introduced in previous papers, allow the usage of the common matrix arithmetic in an efficient, almost optimal way. This article is concerned with the parallelisation of this arithmetics, in particular matrix building, matrix-vector multiplication, matrix multiplication and matrix inversion.Of special interest is the design of algorithms, which reuse as much as possible of the corresponding sequential methods, thereby keeping the effort to update an existing implementation at a minimum. This could be achieved by making use of the properties of shared memory systems as they are widely available in the form of workstations or compute servers. These systems provide a simple and commonly supported programming interface in the form of POSIX-threads.The theoretical results for the parallel algorithms are confirmed with numerical examples from BEM and FEM applications.     

Weighted Error Estimates for Finite Element Solutions of Variational Inequalities

In this note the studies begun in Blum and Suttmeier (1999) on adaptive finite element discretisations for nonlinear problems described by variational inequalities are continued. Similar to the concept proposed, e.g., in Becker and Rannacher (1996) for variational equalities, weighted a posteriori estimates for controlling arbitrary functionals of the discretisation error are constructed by using a duality argument. Numerical results for the obstacle problem demonstrate the derived error bounds to be reliable and, used for an adaptive grid refinement strategy, to produce economical meshes. Received September 6, 1999; revised February 8, 2000     

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.     

Ordering Techniques for Two- and Three-Dimensional Convection-Dominated Elliptic Boundary Value Problems

Multigrid methods with simple smoothers have been proven to be very successful for elliptic problems with no or only moderate convection. In the presence of dominant convection or anisotropies as it might appear in equations of computational fluid dynamics (e.g. in the Navier-Stokes equations), the convergence rate typically decreases. This is due to a weakened smoothing property as well as to problems in the coarse grid correction. In order to obtain a multigrid method that is robust for convection-dominated problems, we construct efficient smoothers that obtain their favorable properties through an appropriate ordering of the unknowns. We propose several ordering techniques that work on the graph associated with the (convective part of the) stiffness matrix. The ordering algorithms provide a numbering together with a block structure which can be used for block iterative methods. We provide numerical results for the Stokes equations with a convective term illustrating the improved convergence properties of the multigrid algorithm when applied with an appropriate ordering of the unknowns. Received July 12, 1999; revised October 1, 1999