Convergence of a staggered Lax-Friedrichs scheme for nonlinear conservation laws on unstructured two-dimensional grids

Summary. Based on Nessyahu and Tadmor's nonoscillatory central difference schemes for one-dimensional hyperbolic conservation laws [16], for higher dimensions several finite volume extensions and numerical results on structured and unstructured grids have been presented. The experiments show the wide applicability of these multidimensional schemes. The theoretical arguments which support this are some maximum-principles and a convergence proof in the scalar linear case. A general proof of convergence, as obtained for the original one-dimensional NT-schemes, does not exist for any of the extensions to multidimensional nonlinear problems. For the finite volume extension on two-dimensional unstructured grids introduced by Arminjon and Viallon [3,4] we present a proof of convergence for the first order scheme in case of a nonlinear scalar hyperbolic conservation law. Received April 8, 2000 / Published online December 19, 2000     

Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids

Summary. We consider two level overlapping Schwarz domain decomposition methods for solving the finite element problems that arise from discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Standard finite element interpolation from the coarse to the fine grid may be used. Our theory requires no assumption on the substructures that constitute the whole domain, so the substructures can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved, and neither the coarse mesh nor the fine mesh need be quasi-uniform. In addition, the domains defined by the fine and coarse grid need not be identical. The one important constraint is that the closure of the coarse grid must cover any portion of the fine grid boundary for which Neumann boundary conditions are given. In this general setting, our algorithms have the same optimal convergence rate as the usual two level overlapping domain decomposition methods on structured meshes. The condition number of the preconditioned system depends only on the (possibly small) overlap of the substructures and the size of the coarse grid, but is independent of the sizes of the subdomains. Received March 23, 1994 / Revised version received June 2, 1995     

Error estimate for a stabilised domain decomposition method with nonmatching grids

Summary. In this paper, we analyse a stabilisation technique for the so-called three-field formulation for nonoverlapping domain decomposition methods. The stabilisation is based on boundary bubble functions in each subdomain which are then eliminated by static condensation. The discretisation grids in the subdomains can be chosen independently as well as the grid for the final interface problem. We present the analysis of the method and we construct a set of bubble functions which guarantees the optimal rate of convergence. Received May 12, 1998 / Revised version received November 21, 2000 / Published online June 7, 2001     

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     

Multigrid methods with web-splines

Summary. We describe and analyze a multigrid algorithm for finite element approximations of second order elliptic boundary value problems with weightedextended b-splines (web-splines). This new technique provides high accuracy with relatively low-dimensional subspaces, does not require any grid generation, and is ideally suited for hierarchical solution techniques. In particular, we show that the standard W-cycle yields uniform convergence, i.e., the required number of iterations is bounded independent of the grid width. Received August 17, 2000 / Published online August 17, 2001     

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 of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 2000     

Convergence analysis and error estimates for a parallel algorithm for solving the Navier-Stokes equations

Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The results justify the observed accuracy of related numerical results. Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986     

A multilevel algorithm for the solution of second order elliptic differential equations on sparse grids

A multilevel algorithm is presented that solves general second order elliptic partial differential equations on adaptive sparse grids. The multilevel algorithm consists of several V-cycles in - and -direction. A suitable discretization provide that the discrete equation system can be solved in an efficient way. Numerical experiments show a convergence rate of order for the multilevel algorithm. Received April 19, 1996 / Revised version received December 9, 1996     

Generalized p-FEM in homogenization

Summary. A new finite element method for elliptic problems with locally periodic microstructure of length is developed and analyzed. It is shown that the method converges, as , to the solution of the homogenized problem with optimal order in and exponentially in the number of degrees of freedom independent of . The computational work of the method is bounded independently of . Numerical experiments demonstrate the feasibility and confirm the theoretical results. Received September 11, 1998 / Published online April 20, 2000     

Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition

Summary. Wavelet methods allow to combine high order accuracy, multilevel preconditioning techniques and adaptive approximation, in order to solve efficiently elliptic operator equations. One of the main difficulty in this context is the efficient treatment of non-homogeneous boundary conditions. In this paper, we propose a strategy that allows to append such conditions in the setting of space refinement (i.e. adaptive) discretizations of second order problems. Our method is based on the use of compatible multiscale decompositions for both the domain and its boundary, and on the possibility of characterizing various function spaces from the numerical properties of these decompositions. In particular, this allows the construction of a lifting operator which is stable for a certain range of smoothness classes, and preserves the compression of the solution in the wavelet basis. An explicit construction of the wavelet bases and the lifting is proposed on fairly general domains, based on conforming domain decomposition techniques. Received November 2, 1998 / Published online April 20, 2000     

Two-level preconditioners for regularized inverse problems I: Theory

Summary. We compare additive and multiplicative Schwarz preconditioners for the iterative solution of regularized linear inverse problems, extending and complementing earlier results of Hackbusch, King, and Rieder. Our main findings are that the classical convergence estimates are not useful in this context: rather, we observe that for regularized ill-posed problems with relevant parameter values the additive Schwarz preconditioner significantly increases the condition number. On the other hand, the multiplicative version greatly improves conditioning, much beyond the existing theoretical worst-case bounds. We present a theoretical analysis to support these results, and include a brief numerical example. More numerical examples with real applications will be given elsewhere. Received May 28, 1998 / Published online: July 7, 1999     

Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains

Summary. Three iterative domain decomposition methods are considered: simultaneous updates on all subdomains (Additive Schwarz Method), flow directed sweeps and double sweeps. By using some techniques of formal language theory we obtain a unique criterion of convergence for the three methods. The convergence rate is a function of the criterion and depends on the algorithm. Received October 24, 1994 / Revised version received November 27, 1995     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems

Summary. We present a Lagrange multiplier based two-level domain decomposition method for solving iteratively large-scale systems of equations arising from the finite element discretization of high-frequency exterior Helmholtz problems. The proposed method is essentially an extension of the regularized FETI (Finite Element Tearing and Interconnecting) method to indefinite problems. Its two key ingredients are the regularization of each subdomain matrix by a complex interface lumped mass matrix, and the preconditioning of the interface problem by an auxiliary coarse problem constructed to enforce at each iteration the orthogonality of the residual to a set of carefully chosen planar waves. We show numerically that the proposed method is scalable with respect to the mesh size, the subdomain size, and the wavenumber. We report performance results for a submarine application that highlight the efficiency of the proposed method for the solution of high frequency acoustic scattering problems discretized by finite elements. Received March 17, 1998 / Revised version received June 7, 1999 / Published online January 27, 2000     

Multigrid methods for a parameter dependent problem in primal variables

Summary. In this paper we consider multigrid methods for the parameter dependent problem of nearly incompressible materials. We construct and analyze multilevel-projection algorithms, which can be applied to the mixed as well as to the equivalent, non-conforming finite element scheme in primal variables. For proper norms, we prove that the smoothing property and the approximation property hold with constants that are independent of the small parameter. Thus we obtain robust and optimal convergence rates for the W-cycle and the variable V-cycle multigrid methods. The numerical results pretty well conform the robustness and optimality of the multigrid methods proposed. Received June 17, 1998 / Revised version received October 26, 1998 / Published online September 7, 1999     

On the convergence of a dual-primal substructuring method

Summary.   In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains, but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated. The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number, assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for a wide class of finite elements for the Reissner-Mindlin plate model. Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000     

Convergence of finite volume monotone schemes for scalar conservation laws on bounded domains

Summary. This paper is devoted to the study of the finite volume methods used in the discretization of conservation laws defined on bounded domains. General assumptions are made on the data: the initial condition and the boundary condition are supposed to be measurable bounded functions. Using a generalized notion of solution to the continuous problem (namely the notion of entropy process solution, see [9]) and a uniqueness result on this solution, we prove that the numerical solution converges to the entropy weak solution of the continuous problem in for every . This also yields a new proof of the existence of an entropy weak solution. Received May 18, 2000 / Revised version received November 21, 2000 / Published online June 7, 2001     

Efficient orthogonal spline collocation methods for solving linear second order hyperbolic problems on rectangles

Summary. Piecewise Hermite bicubic orthogonal spline collocation Laplace-modified and alternating-direction schemes for the approximate solution of linear second order hyperbolic problems on rectangles are analyzed. The schemes are shown to be unconditionally stable and of optimal order accuracy in the and discrete maximum norms for space and time, respectively. Implementations of the schemes are discussed and numerical results presented which demonstrate the accuracy and rate of convergence using various norms. Received November 7, 1994 / Revised version received April 29, 1996