A uniformly convergent scheme for a system of reaction–diffusion equations

In this work a system of two parabolic singularly perturbed equations of reaction–diffusion type is considered. The asymptotic behaviour of the solution and its partial derivatives is given. A decomposition of the solution in its regular and singular parts has been used for the asymptotic analysis of the spatial derivatives. To approximate the solution we consider the implicit Euler method for time stepping and the central difference scheme for spatial discretization on a special piecewise uniform Shishkin mesh. We prove that this scheme is uniformly convergent, with respect to the diffusion parameters, having first-order convergence in time and almost second-order convergence in space, in the discrete maximum norm. Numerical experiments illustrate the order of convergence proved theoretically.     

Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation

The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH ¹-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.This research was supported in part by funds from the National Science Foundation grant CCR-9103451.     

Fourth-order compact schemes with adaptive time step for monodomain reaction–diffusion equations

Multigrid applied to fourth-order compact schemes for monodomain reaction–diffusion equations in two dimensions has been developed. The scheme accounts for the anisotropy of the medium, allows for any cellular activation model to be used, and incorporates an adaptive time step algorithm. Numerical simulations show up to a 40% reduction in computational time for complex cellular models as compared to second-order schemes for the same solution error. These results point to high-order schemes as valid alternatives for the efficient solution of the cardiac electrophysiology problem when complex cellular activation models are used.     

Stable three-point wavelet bases on general meshes

Summary. Recently, we introduced a wavelet basis on general, possibly locally refined linear finite element spaces. Each wavelet is a linear combination of three nodal basis functions, independently of the number of space dimensions. In the present paper, we show -stability of this basis for a range of , that in any case includes , which means that the corresponding additive Schwarz preconditioner is optimal for second order problems. Furthermore, we generalize the construction of the wavelet basis to manifolds. We show that the wavelets have at least one-, and in areas where the manifold is smooth and the mesh is uniform even two vanishing moments. Because of these vanishing moments, apart from preconditioning, the basis can be used for compression purposes: For a class of integral equation problems, the stiffness matrix with respect to the wavelet basis will be close to a sparse one, in the sense that, a priori, it can be compressed to a sparse matrix without the order of convergence being reduced. Received November 6, 1996 / Revised version received June 30, 1997     

Wavelet approximations for first kind boundary integral equations on polygons

Summary. An elliptic boundary value problem in the interior or exterior of a polygon is transformed into an equivalent first kind boundary integral equation. Its Galerkin discretization with degrees of freedom on the boundary with spline wavelets as basis functions is analyzed. A truncation strategy is presented which allows to reduce the number of nonzero elements in the stiffness matrix from to entries. The condition numbers are bounded independently of the meshwidth. It is proved that the compressed scheme thus obtained yields in operations approximate solutions with the same asymptotic convergence rates as the full Galerkin scheme in the boundary energy norm as well as in interior points. Numerical examples show the asymptotic error analysis to be valid already for moderate values of . Received March 12, 1994 / Revised version received January 9, 1995     

Trigonometric Hermite wavelet approximation for the integral equations of second kind with weakly singular kernel

This paper is concerned with a trigonometric Hermite wavelet Galerkin method for the Fredholm integral equations with weakly singular kernel. The kernel function of this integral equation considered here includes two parts, a weakly singular kernel part and a smooth kernel part. The approximation estimates for the weakly singular kernel function and the smooth part based on the trigonometric Hermite wavelet constructed by E. Quak [Trigonometric wavelets for Hermite interpolation, Math. Comp. 65 (1996) 683–722] are developed. The use of trigonometric Hermite interpolant wavelets for the discretization leads to a circulant block diagonal symmetrical system matrix. It is shown that we only need to compute and store O(N)$\mathrm{O}(N)$ entries for the weakly singular kernel representation matrix with dimensions N²$N^2$ which can reduce the whole computational cost and storage expense. The computational schemes of the resulting matrix elements are provided for the weakly singular kernel function. Furthermore, the convergence analysis is developed for the trigonometric wavelet method in this paper.     

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.     

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.     

Error estimators for advection–reaction–diffusion equations based on the solution of local problems

This paper deals with a posteriori error estimates for advection–reaction–diffusion equations. In particular, error estimators based on the solution of local problems are derived for a stabilized finite element method. These estimators are proved to be equivalent to the error, with equivalence constants eventually depending on the physical parameters. Numerical experiments illustrating the performance of this approach are reported.     

On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs

Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each subdomain. In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular, an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology. This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P)     

Nonlinear functionals of wavelet expansions – adaptive reconstruction and fast evaluation

Summary. This paper is concerned with the efficient evaluation of nonlinear expressions of wavelet expansions obtained through an adaptive process. In particular, evaluation covers here the computation of inner products of such expressions with wavelets which arise, for instance, in the context of Galerkin or Petrov Galerkin schemes for the solution of differential equations. The central objective is to develop schemes that facilitate such evaluations at a computational expense exceeding the complexity of the given expansion, i.e., the number of nonzero wavelet coefficients, as little as possible. The following issues are addressed. First, motivated by previous treatments of the subject, we discuss the type of regularity assumptions that are appropriate in this context and explain the relevance of Besov norms. The principal strategy is to relate the computation of inner products of wavelets with compositions to approximations of compositions in terms of possibly few dual wavelets. The analysis of these approximations finally leads to a concrete evaluation scheme which is shown to be in a certain sense asymptotically optimal. We conclude with a simple numerical example. Received June 25, 1998 / Revised version received June 5, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

Adaptive multilevel finite element approximations of semilinear elliptic boundary value problems

Summary. In this paper we consider two aspects of the problem of designing efficient numerical methods for the approximation of semilinear boundary value problems. First we consider the use of two and multilevel algorithms for approximating the discrete solution. Secondly we consider adaptive mesh refinement based on feedback information from coarse level approximations. The algorithms are based on an a posteriori error estimate, where the error is estimated in terms of computable quantities only. The a posteriori error estimate is used for choosing appropriate spaces in the multilevel algorithms, mesh refinements, as a stopping criterion and finally it gives an estimate of the total error. Received April 8, 1997 / Revised version received July 27, 1998 / Published online September 24, 1999     

Block method for problems on L-shaped domains

An extremely accurate, exponentially convergent solution is presented for both symmetric and non-symmetric Laplacian problems on L-shaped domains by using one-block version of the block method (BM). A simple and highly accurate formula for computing the stress intensity factor is given. Comparisons with various results in the literature are included.     

Finite element methods with numerical quadrature for elliptic problems with smooth interfaces

The purpose of this paper is to study the effect of the numerical quadrature on the finite element approximation to the exact solution of elliptic equations with discontinuous coefficients. Due to low global regularity of the solution, it seems difficult to achieve optimal order of convergence with classical finite element methods [Z. Chen, J. Zou, Finite element methods and their convergence for elliptic and parabolic interface problems, Numer. Math. 79 (1998) 175-202]. We derive error estimates in finite element method with quadrature for elliptic interface problems in a two-dimensional convex polygonal domain. Optimal order error estimates in L² and H¹ norms are shown to hold even if the regularity of the solution is low on the whole domain. Finally, numerical experiment for two dimensional test problem is presented in support of our theoretical findings.     

Multigrid method for solving convection-diffusion problems with dominant convection

A modification of the multigrid method for the solution of linear algebraic equation systems with a strongly nonsymmetric matrix obtained after difference approximation of the convection-diffusion equation with dominant convection is proposed. Specially created triangular iterative methods have been used as the smoothers of the multigrid method. Some theoretical and numerical results are presented.     

Preconditioned conjugate gradient methods for large-scale fluid flow applications

The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes.     

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.     

Global extrapolation with a parallel splitting method

Extrapolation with a parallel splitting method is discussed. The parallel splitting method reduces a multidimensional problem into independent one-dimensional problems and can improve the convergence order of space variables to an order as high as the regularity of the solution permits. Therefore, in order to match the convergence order of the space variables, a high order method should also be used for the time integration. Second and third order extrapolation methods are used to improve the time convergence and it was found that the higher order extrapolation method can produce a more accurate solution than the lower order extrapolation method, but the convergence order of high order extrapolation may be less than the actual order of the extrapolation. We also try to show a fact that has not been studied in the literature, i.e. when the extrapolation is used, it may decrease the convergence of the space variables. The higher the order of the extrapolation method, the more it decreases the convergence of the space variables. The global extrapolation method also improves the parallel degree of the parallel splitting method. Numerical tests in the paper are done in a domain of a unit circle and a unit square.Supported by the Academy of Finland.     

Fast and Robust Sixth Order Multigrid Computation for 3D Convection Diffusion Equation

We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.     

Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994