A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

Finite element approximation of multi-scale elliptic problems using patches of elements

In this paper we present a method for the numerical solution of elliptic problems with multi-scale data using multiple levels of not necessarily nested grids. The method consists in calculating successive corrections to the solution in patches whose discretizations are not necessarily conforming. This paper provides proofs of the results published earlier (see C. R. Acad. Sci. Paris, Ser. I 337 (2003) 679–684), gives a generalization of the latter to more than two domains and contains extensive numerical illustrations. New results including the spectral analysis of the iteration operator and a numerical method to evaluate the constant of the strengthened Cauchy-Buniakowski-Schwarz inequality are presented. Supported by CTI Project 6437.1 IWS-IW.     

An active set strategy to generate quadrilateral grids

We consider the problem of the generation of quadrilateral grids on planar domains. This problem is numerically solved by a two phases method: an iterative procedure based on the well-known variational approach, and an active set procedure to obtain unfolded quadrilaterals. This second phase is performed only when it is really necessary, in fact the first phase alone gives satisfactory results on a large number of domains. This two phases approach provides a robust method with low computational cost. Numerical experiments show that this method is able to generate unfolded grids also on complex domains.     

Error analysis for a potential problem on locally refined grids

Summary. For the simulation of biomolecular systems in an aqueous solvent a continuum model is often used for the solvent. The accurate evaluation of the so-called solvation energy coming from the electrostatic interaction between the solute and the surrounding water molecules is the main issue in this paper. In these simulations, we deal with a potential problem with jumping coefficients and with a known boundary condition at infinity. One of the advanced ways to solve the problem is to use a multigrid method on locally refined grids around the solute molecule. In this paper, we focus on the error analysis of the numerical solution and the numerical solvation energy obtained on the locally refined grids. Based on a rigorous error analysis via a discrete approximation of the Greens function, we show how to construct the composite grid, to discretize the discontinuity of the diffusion coefficient and to interpolate the solutions at interfaces between the fine and coarse grids. The error analysis developed is confirmed by numerical experiments. Received June 25, 1998 / Revised version received July 14, 1999 / Published online June 8, 2000     

Convergence estimates of a projection-difference method for an operator-differential equation

This article investigates the projection-difference method for a Cauchy problem for a linear operator-differential equation with a leading self-adjoint operator A(t) and a subordinate linear operator K(t) in Hilbert space. This method leads to the solution of a system of linear algebraic equations on each time level; moreover, the projection subspaces are linear spans of eigenvectors of an operator similar to A(t). The convergence estimates are obtained. The application of the developed method for solving the initial boundary value problem is given.     

On the coupled BEM and FEM for a nonlinear exterior Dirichlet problem in R2

Summary In this paper we apply the coupling of boundary integral and finite element methods to solve a nonlinear exterior Dirichlet problem in the plane. Specifically, the boundary value problem consists of a nonlinear second order elliptic equation in divergence form in a bounded inner region, and the Laplace equation in the corresponding unbounded exterior region, in addition to appropriate boundary and transmission conditions. The main feature of the coupling method utilized here consists in the reduction of the nonlinear exterior boundary value problem to an equivalent monotone operator equation. We provide sufficient conditions for the coefficients of the nonlinear elliptic equation from which existence, uniqueness and approximation results are established. Then, we consider the case where the corresponding operator is strongly monotone and Lipschitz-continuous, and derive asymptotic error estimates for a boundary-finite element solution. We prove the unique solvability of the discrete operator equations, and based on a Strang type abstract error estimate, we show the strong convergence of the approximated solutions. Moreover, under additional regularity assumptions on the solution of the continous operator equation, the asymptotic rate of convergenceO (h) is obtained.The first author's research was partly supported by the U.S. Army Research Office through the Mathematical Science Institute of Cornell University, by the Universidad de Concepción through the Facultad de Ciencias, Dirección de Investigación and Vicerretoria, and by FONDECYT-Chile through Project 91-386.     

On local convergence of a symmetric semi-discrete scheme for an abstract analogue of the Kirchhoff equation

The present work considers a nonlinear abstract hyperbolic equation with a self-adjoint positive definite operator, which represents a generalization of the Kirchhoff string equation. A symmetric three-layer semi-discrete scheme is constructed for an approximate solution of a Cauchy problem for this equation. Value of the gradient in the nonlinear term of the scheme is taken at the middle point. It makes possible to find an approximate solution at each time step by inverting the linear operator. Local convergence of the constructed scheme is proved. Numerical calculations for different model problems are carried out using this scheme.     

A new cement to glue non-conforming grids with Robin interface conditions: The finite volume case

Summary Robin interface conditions in domain decomposition methods enable the use of non overlapping subdomains and a speed up in the convergence. Non conforming grids make the grid generation much easier and faster since it is then a parallel task. The goal of this paper is to propose and analyze a new discretization scheme which allows to combine the use of Robin interface conditions with non-matching grids. We consider both a symmetric definite positive operator and the convection-diffusion equation discretized by finite volume schemes. Numerical results are shown. Received December 22, 1999 / Revised version received December 21, 2000 / Published online December 18, 2001 Correspondence to: F. Nataf     

On the balancing principle for some problems of Numerical Analysis

We discuss a choice of weight in penalization methods. The motivation for the use of penalization in computational mathematics is to improve the conditioning of the numerical solution. One example of such improvement is a regularization, where a penalization substitutes an ill-posed problem for a well-posed one. In modern numerical methods for PDEs a penalization is used, for example, to enforce a continuity of an approximate solution on non-matching grids. A choice of penalty weight should provide a balance between error components related with convergence and stability, which are usually unknown. In this paper we propose and analyze a simple adaptive strategy for the choice of penalty weight which does not rely on a priori estimates of above mentioned components. It is shown that under natural assumptions the accuracy provided by our adaptive strategy is worse only by a constant factor than one could achieve in the case of known stability and convergence rates. Finally, we successfully apply our strategy for self-regularization of Volterra-type severely ill-posed problems, such as the sideways heat equation, and for the choice of a weight in interior penalty discontinuous approximation on non-matching grids. Numerical experiments on a series of model problems support theoretical results.     

Comparison of different spatial grids for numerical schemes of geophysical fluid dynamics

The generation of computational grids is an important component contributing to the efficiency of numerical schemes of atmosphere/ocean dynamics. In this study the problem of construction of the most uniform grids based on conformal mappings of spherical domains is considered. Stereographic, cylindrical and conic grids for computational rectangles are developed and their uniformity is compared. Numerical experiments with two schemes approximating shallow water equations are performed in order to assess the practical efficiency of the constructed grids and to compare the numerical results with analytical evaluations.     

A finite element — Capacitance method for elliptic problems on regions partitioned into subregions

Summary A method is given for the solution of linear equations arising in the finite element method applied to a general elliptic problem. This method reduces the original problem to several subproblems (of the same form) considered on subregions, and an auxiliary problem. Very efficient iterative methods with the preconditioning operator and using FFT are developed for the auxiliary problem.     

On an iterative algorithm with superquadratic convergence for solving nonlinear operator equations

We study an iterative method with order for solving nonlinear operator equations in Banach spaces. Algorithms for specific operator equations are built up. We present the received new results of the local and semilocal convergence, in case when the first-order divided differences of a nonlinear operator are Hölder continuous. Moreover a quadratic nonlinear majorant for a nonlinear operator, according to the conditions laid upon it, is built. A priori and a posteriori estimations of the method’s error are received. The method needs almost the same number of computations as the classical Secant method, but has a higher order of convergence. We apply our results to the numerical solving of a nonlinear boundary value problem of second-order and to the systems of nonlinear equations of large dimension.     

Efficient computable error bounds for discontinuous Galerkin approximations of elliptic problems

We present guaranteed and computable both sided error bounds for the discontinuous Galerkin (DG) approximations of elliptic problems. These estimates are derived in the full DG-norm on purely functional grounds by the analysis of the respective differential problem, and thus, are applicable to any qualified DG approximation. Based on the triangle inequality, the underlying approach has the following steps for a given DG approximation: (1) computing a conforming approximation in the energy space using the Oswald interpolation operator, and (2) application of the existing functional a posteriori error estimates to the conforming approximation. Various numerical examples with varying difficulty in computing the error bounds, from simple problems of polynomial-type analytic solution to problems with analytic solution having sharp peaks, or problems with jumps in the coefficients of the partial differential equation operator, are presented which confirm the efficiency and the robustness of the estimates.     

Superlinear convergence rates for the Lanczos method applied to elliptic operators

Summary. This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic differential operator via inverse iteration (without shifts). Superlinear convergence rates are established, and their sharpness is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem. Received March 8, 1996     

Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

On the approximation of derivatives using divided difference operators preserving the local convergence order of iterative methods

A development of an inverse first-order divided difference operator for functions of several variables is presented. Two generalized derivative-free algorithms built up from Ostrowski’s method for solving systems of nonlinear equations are written and analyzed. A direct computation of the local order of convergence for these variants of Ostrowski’s method is given. In order to preserve the local order of convergence, any divided difference operator is not valid. Two counterexamples of computation of a classical divided difference operator without preserving the order are presented. A rigorous study to know a priori if the new method will preserve the order of the original modified method is presented. The conclusion is that this fact does not depend on the method but on the systems of equations and if the associated divided difference verifies a particular condition. A new divided difference operator solving this problem is proposed. Furthermore, a computation that approximates the order of convergence is generated for the examples and it confirms in a numerical way that the order of the methods is well deduced. This study can be applied directly to other Newton’s type methods where derivatives are approximated by divided differences.     

Monotonicity of control volume methods

Robustness of numerical methods for multiphase flow problems in porous media is important for development of methods to be used in a wide range of applications. Here, we discuss monotonicity for a simplified problem of single-phase flow, but where the simulation grids and media are allowed to be general, posing challenges to control-volume methods. We discuss discrete formulations of the maximum principle and derive sufficient criteria for discrete monotonicity for arbitrary nine-point control-volume discretizations for conforming quadrilateral grids in 2D. These criteria are less restrictive than the M-matrix property. It is shown that it is impossible to construct nine-point methods which unconditionally satisfy the monotonicity criteria when the discretization satisfies local conservation and exact reproduction of linear potential fields. Numerical examples are presented which show the validity of the criteria for monotonicity. Further, the impact of nonmonotonicity is studied. Different behavior for different discretization methods is illuminated, and simple ideas are presented for improvement in terms of monotonicity.     

Eigenanalysis of some preconditioned Helmholtz problems

Summary. In this work we calculate the eigenvalues obtained by preconditioning the discrete Helmholtz operator with Sommerfeld-like boundary conditions on a rectilinear domain, by a related operator with boundary conditions that permit the use of fast solvers. The main innovation is that the eigenvalues for two and three-dimensional domains can be calculated exactly by solving a set of one-dimensional eigenvalue problems. This permits analysis of quite large problems. For grids fine enough to resolve the solution for a given wave number, preconditioning using Neumann boundary conditions yields eigenvalues that are uniformly bounded, located in the first quadrant, and outside the unit circle. In contrast, Dirichlet boundary conditions yield eigenvalues that approach zero as the product of wave number with the mesh size is decreased. These eigenvalue properties yield the first insight into the behavior of iterative methods such as GMRES applied to these preconditioned problems. Received March 24, 1998 / Revised version received September 28, 1998     

Finite element methods of an operator splitting applied to population balance equations

In population balance equations, the distribution of the entities depends not only on space and time but also on their own properties referred to as internal coordinates. The operator splitting method is used to transform the whole time-dependent problem into two unsteady subproblems of a smaller complexity. The first subproblem is a time-dependent convection-diffusion problem while the second one is a transient transport problem with pure advection. We use the backward Euler method to discretize the subproblems in time. Since the first problem is convection-dominated, the local projection method is applied as stabilization in space. The transport problem in the one-dimensional internal coordinate is solved by a discontinuous Galerkin method. The unconditional stability of the method will be presented. Optimal error estimates are given. Numerical tests confirm the theoretical results.     

Discrete Galerkin method for Fredholm integro-differential equations with weakly singular kernels

Approximations to a solution and its derivatives of a boundary value problem of an nth order linear Fredholm integro-differential equation with weakly singular or other nonsmooth kernels are determined. These approximations are piecewise polynomial functions on special graded grids. For their finding a discrete Galerkin method and an integral equation reformulation of the boundary value problem are used. Optimal global convergence estimates are derived and an improvement of the convergence rate of the method for a special choice of parameters is obtained. To illustrate the theoretical results a collection of numerical results of a test problem is presented.