Résolution approchée de problèmes aux limites elliptiques par des schémas aux éléments finis a plusieurs fonctions arbitraires

Summary The present paper is devoted to the approximate solution of variational elliptic boundary value problems of the form: α(u, v)=(f, v)v ∈V by using approximations of the Hilbert spaceV with several degrees of freedom as constructed in a preceding paper [7]. These approximations lead to finite difference schemes involving several arbitrary parameters, whose solution converge to the exact solution of the boundary value problem if the values of these parameters are small enough. This fact can be utilized to diminish the error between the exact and the approximate solution by a suitable choice of these arbitrary parameters, so as to avoid the use of very small step lengths. The method may prove useful in cases where the coercivity constant of the bilinear form α (u, v) is small when compated to its continuity constant, and more generally for problems of the form: α (u, v)−λ (u. v.)=(f, v) where the constant λ is close to an eigenvalue of the boundary value problem.      

Efficient removal of boundary-divergence errors in time-splitting methods

A normal mode analysis is presented and numerical tests are performed to assess the effectiveness of a new time-splitting algorithm proposed recently in Karniadakiset al. (1990) for solving the incompressible Navier-Stokes equations. This new algorithm employs high-order explicit pressure boundary conditions and mixed explicit/implicit stiffly stable time-integration schemes, which can lead to arbitrarily high-order accuracy in time. In the current article we investigate both the time accuracy of the new scheme as well as the corresponding reduction in boundary-divergence errors for two model flow problems involving solid boundaries. The main finding is that time discretization errors, induced by the nondivergent splitting mode, scale with the order of the accuracy of the integration rule employed if a proper rotational form of the pressure boundary condition is used; otherwise a first-order accuracy in time similar to the classical splitting methods is achieved. In the former case the corresponding errors in divergence can be completely eliminated, while in the latter case they scale asO(vt)_1/2.     

A uniform numerical method for quasilinear singular perturbation problems without turning points

A numerical method for singularly perturbed quasilinear boundary value problems without turning points is proposed: the continuous problem is transformed by introducing a special new independent variable and then finite-difference schemes are applied. The first order convergence uniform in the perturbation parameter is proved in the discreteL ¹-norm. The numerical results show the pointwise convergence, too.     

Mixed Discontinuous Galerkin Finite Element Method for the Biharmonic Equation

In this paper, we first split the biharmonic equation Δ² u=f with nonhomogeneous essential boundary conditions into a system of two second order equations by introducing an auxiliary variable v=Δu and then apply an hp-mixed discontinuous Galerkin method to the resulting system. The unknown approximation v _h of v can easily be eliminated to reduce the discrete problem to a Schur complement system in u _h , which is an approximation of u. A direct approximation v _h of v can be obtained from the approximation u _h of u. Using piecewise polynomials of degree p≥3, a priori error estimates of u−u _h in the broken H ¹ norm as well as in L ² norm which are optimal in h and suboptimal in p are derived. Moreover, a priori error bound for v−v _h in L ² norm which is suboptimal in h and p is also discussed. When p=2, the preset method also converges, but with suboptimal convergence rate. Finally, numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.     

On Parabolic Boundary Layers for Convection–Diffusion Equations in a Channel: Analysis and Numerical Applications

In this article we discuss singularly perturbed convection–diffusion equations in a channel in cases producing parabolic boundary layers. It has been shown that one can improve the numerical resolution of singularly perturbed problems involving boundary layers, by incorporating the structure of the boundary layers into the finite element spaces, when this structure is available; see e.g. [Cheng, W. and Temam, R. (2002). Comput. Fluid. V.31, 453–466; Jung, C. (2005). Numer. Meth. Partial Differ. Eq. V.21, 623–648]. This approach is developed in this article for a convection–diffusion equation. Using an analytical approach, we first derive an approximate (simplified) form of the parabolic boundary layers (elements) for our problem; we then develop new numerical schemes using these boundary layer elements. The results are performed for the perturbation parameter ε in the range 10⁻¹–10⁻¹⁵ whereas the discretization mesh is in the range of order 1/10–1/100 in the x-direction and of order 1/10–1/30 in the y-direction. Indications on various extensions of this work are briefly described at the end of the Introduction.Dedicated to David Gottlieb on his 60th birthday.     

Harmonic Wavelet Transform and Image Approximation

In 2006, Saito and Remy proposed a new transform called the Laplace Local Sine Transform (LLST) in image processing as follows. Let f be a twice continuously differentiable function on a domain Ω. First we approximate f by a harmonic function u such that the residual component v=f−u vanishes on the boundary of Ω. Next, we do the odd extension for v, and then do the periodic extension, i.e. we obtain a periodic odd function v ^*. Finally, we expand v ^* into Fourier sine series. In this paper, we propose to expand v ^* into a periodic wavelet series with respect to biorthonormal periodic wavelet bases with the symmetric filter banks. We call this the Harmonic Wavelet Transform (HWT). HWT has an advantage over both the LLST and the conventional wavelet transforms. On the one hand, it removes the boundary mismatches as LLST does. On the other hand, the HWT coefficients reflect the local smoothness of f in the interior of Ω. So the HWT algorithm approximates data more efficiently than LLST, periodic wavelet transform, folded wavelet transform, and wavelets on interval. We demonstrate the superiority of HWT over the other transforms using several standard images.     

A Supra-Convergent Finite Difference Scheme for the Poisson and Heat Equations on Irregular Domains and Non-Graded Adaptive Cartesian Grids

We present finite difference schemes for solving the variable coefficient Poisson and heat equations on irregular domains with Dirichlet boundary conditions. The computational domain is discretized with non-graded Cartesian grids, i.e., grids for which the difference in size between two adjacent cells is not constrained. Refinement criteria is based on proximity to the irregular interface such that cells with the finest resolution is placed on the interface. We sample the solution at the cell vertices (nodes) and use quadtree (in 2D) or octree (in 3D) data structures as efficient means to represent the grids. The boundary of the irregular domain is represented by the zero level set of a signed distance function. For cells cut by the interface, the location of the intersection point is found by a quadratic fitting of the signed distance function, and the Dirichlet boundary value is obtained by quadratic interpolation. Instead of using ghost nodes outside the interface, we use directly this intersection point in the discretization of the variable coefficient Laplacian. These methods can be applied in a dimension-by-dimension fashion, producing schemes that are straightforward to implement. Our method combines the ability of adaptivity on quadtrees/octrees with a quadratic treatment of the Dirichlet boundary condition on the interface. Numerical results in two and three spatial dimensions demonstrate second-order accuracy for both the solution and its gradients in the L ¹ and L ^∞ norms.     

Fast Tensor-Product Solvers: Partially Deformed Three-dimensional Domains

We discuss the numerical solution of partial differential equations in a particular class of three-dimensional geometries; the two-dimensional cross section (in the xy-plane) can have a general shape, but is assumed to be invariant with respect to the third direction. Earlier work has exploited such geometries by approximating the solution as a truncated Fourier series in the z-direction. In this paper we propose a new solution algorithm which also exploits the tensor-product feature between the xy-plane and the z-direction. However, the new algorithm is not limited to periodic boundary conditions, but works for general Dirichlet and Neumann type of boundary conditions. The proposed algorithm also works for problems with variable coefficients as long as these can be expressed as a separable function with respect to the variation in the xy-plane and the variation in the z-direction. For problems where the new method is applicable, the computational cost is very competitive with the best iterative solvers. The new algorithm is easy to implement, and useful, both in a serial and parallel context. Numerical results demonstrating the superiority of the method are presented for three-dimensional Poisson and Helmholtz problems using both low order finite elements and high order spectral element discretizations.     

Calculation of exponential integrals of real order

In a previous paper a numerical method was presented for the generalized exponential integral function E _v (x), (x>0, v?R), of interest for applications in astrophysics and nuclear physics in a general treatment context of this function. In the present work, we are mainly concerned with numerical features, above all as regards the relevant computational procedure and execution. Comparisons performed by means of a different algorithm ensure efficiency of the evaluation technique and the corresponding implementation, ERA, whose accuracy is confirmed by the results of the related error analysis.     

Integrating Standard Dependency Schemes in QCSP Solvers

Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers.In this paper we apply variab...     

High-order compact scheme for boundary points

In this paper, we introduce a new high-order scheme for boundary points when calculating the derivative of smooth functions by compact scheme. The primitive function reconstruction method of ENO schemes is applied to obtain the conservative form of the compact scheme. Equations for approximating the derivatives around the boundary points 1 and N are determined. For the Neumann (and mixed) boundary conditions, high-order equations are derived to determine the values of the function at the boundary points, 1 and N, before the primitive function reconstruction method is applied. We construct a subroutine that can be used with Dirichlet, Neumann, or mixed boundary conditions. Numerical tests are presented to demonstrate the capabilities of this new scheme, and a comparison to the lower-order boundary scheme shows its advantages.     

General <Emphasis Type="Italic">E</Emphasis>-unification with Eager Variable Elimination and a Nice Cycle Rule

We present a goal-directed E-unification procedure with eager Variable Elimination and a new rule, Cycle, for the case of collapsing equations – that is, equations of the type x ≈ v where x ∈Var(v). Cycle replaces Variable Decomposition (or the so-called Root Imitation) and thus removes possibility of some obviously unnecessary infinite paths of inferences in the E-unification procedure. We prove that, as in other approaches, such inferences into variable positions in our goal-directed procedure are not needed. Our system is independent of selection rule and complete for any E-unification problem.     

Convex ENO Schemes for Hamilton–Jacobi Equations

In one dimension, viscosity solutions of Hamilton–Jacobi (HJ) equations can be thought as primitives of entropy solutions for conservation laws. Based on this idea, both theoretical and numerical concepts used for conservation laws can be passed to HJ equations even in several dimensions. In this paper, we construct convex ENO (CENO) schemes for HJ equations. This construction is a generalization from the work by Liu and Osher on CENO schemes for conservation laws. Several numerical experiments are performed. L ¹ and L ^∞ error and convergence rate are calculated as well.     

Tension Spline for the Solution of Self-adjoint Singular Perturbation Problems

A numerical method based on spline in tension is given for the self-adjoint singularly perturbed two point boundary value problems. The schemes derived in this method are second order accurate. One numerical example is given to support the predicted theory.     

A numerical study of the convergence properties of ENO schemes

We report numerical results obtained with finite difference ENO schemes for the model problem of the linear convection equation with periodic boundary conditions. For the test function sin(x), the spatial and temporal errors decrease at the rate expected from the order of local truncation errors as the discretization is refined. If we take sin⁴(x) as our test function, however, we find that the numerical solution does not converge uniformly and that an improved discretization can result in larger errors. This difficulty is traced back to the linear stability characteristics of the individual stencils employed by the ENO algorithm. If we modify the algorithm to prevent the use of linearly unstable stencils, the proper rate of convergence is reestablished. The way toward recovering the correct order of accuracy of ENO schemes appears to involve a combination of fixed stencils in smooth regions and ENO stencils in regions of strong gradients —a concept that is developed in detail in a companion paper by Shu (this issue, 1990).     

Invariant Regions and asymptotic behaviour for the numerical solution of reaction-diffusion systems by a class of alternating direction methods

In this paper we study the asymptotic behaviour of the numerical solution of systems of nonlinear reaction-diffusion equations, with homogeneous Dirichlet boundary conditions. We construct a class of alternating direction methods. In order to obtain a good simulation of the analytical solution, we require the difference schemes to be of positive type; this fact enables us to prove that, if an invariant setS exists for the analytical solutions,S is also invariant for the numerical solution and, moreover, to find a time-independent error estimate, if the nonlinear termF satisfies a monotonicity condition.     

Delphi: geometry-based connectivity prediction in triangle mesh compression

Delphi is a new geometry-guided predictive scheme for compressing the connectivity of triangle meshes. Both compression and decompression algorithms traverse the mesh using the EdgeBreaker state machine. However, instead of encoding the EdgeBreaker clers symbols that capture connectivity explicitly, they estimate the location of the unknown vertex, v , of the next triangle. If the predicted location lies sufficiently close to the nearest vertex, w , on the boundary of the previously traversed portion of the mesh, then Delphi estimates that v coincides with w . When the guess is correct, a single confirmation bit is encoded. Otherwise, additional bits are used to encode the rectification of that prediction. When v coincides with a previously visited vertex that is not adjacent to the parent triangle (EdgeBreaker S case), the offset, which identifies the vertex v , must be encoded, mimicking the cut-border machine compression proposed by Gumhold and Strasser. On models where 97% of Delphi predictions are correct, the connectivity is compressed down to 0.19 bits per triangle. Compression rates decrease with the frequency of wrong predictors, but remains below 1.50 bits per triangle for all models tested.     

A new fourth-order difference scheme for solving an N-carrier system with Neumann boundary conditions

In this paper, a numerical method is developed to solve an N-carrier system with Neumann boundary conditions. First, we apply the compact finite difference scheme of fourth order for discretizing spatial derivatives at the interior points. Then, we develop a new combined compact finite difference scheme for the boundary, which also has fourth-order accuracy. Lastly, by using a Padé approximation method for the resulting linear system of ordinary differential equations, a new compact finite difference scheme is obtained. The present scheme has second-order accuracy in time direction and fourth-order accuracy in space direction. It is shown that the scheme is unconditionally stable. The present scheme is tested by two numerical examples, which show that the convergence rate with respect to the spatial variable from the new scheme is higher and the solution is much more accurate when compared with those obtained by using other previous methods.     

Dispersion Analysis of Discontinuous Galerkin Schemes Applied to Poincaré, Kelvin and Rossby Waves

A technique for analyzing dispersion properties of numerical schemes is proposed. The method is able to deal with both non dispersive or dispersive waves, i.e. waves for which the phase speed varies with wavenumber. It can be applied to unstructured grids and to finite domains with or without periodic boundary conditions. We consider the discrete version L of a linear differential operator ℒ. An eigenvalue analysis of L gives eigenfunctions and eigenvalues (l _i ,λ _i ). The spatially resolved modes are found out using a standard a posteriori error estimation procedure applied to eigenmodes. Resolved eigenfunctions l _i ’s are used to determine numerical wavenumbers k _i ’s. Eigenvalues’ imaginary parts are the wave frequencies ω _i and a discrete dispersion relation ω _i =f(k _i ) is constructed and compared with the exact dispersion relation of the continuous operator ℒ. Real parts of eigenvalues λ _i ’s allow to compute dissipation errors of the scheme for each given class of wave. The method is applied to the discontinuous Galerkin discretization of shallow water equations in a rotating framework with a variable Coriolis force. Such a model exhibits three families of dispersive waves, including the slow Rossby waves that are usually difficult to analyze. In this paper, we present dissipation and dispersion errors for Rossby, Poincaré and Kelvin waves. We exhibit the strong superconvergence of numerical wave numbers issued of discontinuous Galerkin discretizations for all families of waves. In particular, the theoretical superconvergent rates, demonstrated for a one dimensional linear transport equation, for dissipation and dispersion errors are obtained in this two dimensional model with a variable Coriolis parameter for the Kelvin and Poincaré waves.     

Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: Theory

Large sparse nonsymmetric problems of the form A u = b are frequently solved using restarted conjugate gradient-type algorithms such as the popular GCR and GMRES algorithms. In this study we define a new class of algorithms which generate the same iterates as the standard GMRES algorithm but require as little as half of the computational expense. This performance improvement is obtained by using short economical three-term recurrences to replace the long recurrence used by GMRES. The new algorithms are shown to have good numerical properties in typical cases, and the new algorithms may be easily modified to be as numerically safe as standard GMRES. Numerical experiments with these algorithms are given in Part II, in which we demonstrate the improved performance of the new schemes on different computer architectures.