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.     

<Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-minimization methods for Hamilton–Jacobi equations: the one-dimensional case

A new approximation technique based on L ¹-minimization is introduced. It is proven that the approximate solution converges to the viscosity solution in the case of one-dimensional stationary Hamilton–Jacobi equation with convex Hamiltonian. This material is based upon work supported by the National Science Foundation grant DMS-0510650. J.-L. Guermond is on leave from LIMSI, UPRR 3251 CNRS, BP 133, 91403 Orsay Cedex, France.     

On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation

Summary It is shown analytically in this work that the conjugate gradient method is an efficient means of solving the singular capacitance matrix equations arising from the Neumann problem of the Poisson equation. The total operation count of the algorithm does not exceed constant timesN ²logN(N=1/h) for any bounded domain with sufficiently smooth boundary.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385. Also partially supported by the Energy Research and Development Administration     

Two-level additive Schwarz preconditioners for C 0 interior penalty methods

We study two-level additive Schwarz preconditioners that can be used in the iterative solution of the discrete problems resulting from C⁰ interior penalty methods for fourth order elliptic boundary value problems. We show that the condition number of the preconditioned system is bounded by C(1+(H³/δ³)), where H is the typical diameter of a subdomain, δ measures the overlap among the subdomains and the positive constant C is independent of the mesh sizes and the number of subdomains. This work was supported in part by the National Science Foundation under Grant No. DMS-03-11790.     

Operator-splitting galerkin methods for one kind of oin reaction model for the pollution in groundwater

Abstract. The operator-splitting methods for the mathematic model of one kind of oin reactionsfor the problem of groundwater are considered. Optimal error estimates in Lz and Hl norm areobtained for the approximation solution.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver     

Interior penalty method for the indefinite time-harmonic Maxwell equations

Summary In this paper, we introduce and analyze the interior penalty discontinuous Galerkin method for the numerical discretization of the indefinite time-harmonic Maxwell equations in the high-frequency regime. Based on suitable duality arguments, we derive a-priori error bounds in the energy norm and the L²-norm. In particular, the error in the energy norm is shown to converge with the optimal order (h^min{s,}) with respect to the mesh size h, the polynomial degree , and the regularity exponent s of the analytical solution. Under additional regularity assumptions, the L²-error is shown to converge with the optimal order (h⁺¹). The theoretical results are confirmed in a series of numerical experiments.Supported by the EPSRC (Grant GR/R76615).Supported by the Swiss National Science Foundation under project 21-068126.02.Supported in part by the Natural Sciences and Engineering Council of Canada.     

Convergence rate estimate for a domain decomposition method

Summary We provide a convergence rate analysis for a variant of the domain decomposition method introduced by Gropp and Keyes for solving the algebraic equations that arise from finite element discretization of nonsymmetric and indefinite elliptic problems with Dirichlet boundary conditions in ². We show that the convergence rate of the preconditioned GMRES method is nearly optimal in the sense that the rate of convergence depends only logarithmically on the mesh size and the number of substructures, if the global coarse mesh is fine enough.This author was supported by the National Science Foundation under contract numbers DCR-8521451 and ECS-8957475, by the IBM Corporation, and by the 3M Company, while in residence at Yale UniversityThis author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract W-31-109-Eng-38This author was supported by the National Science Foundation under contract number ECS-8957475, by the IBM Corporation, and by the 3M Company     

DOMAIN DECOMPOSITION METHOD FOR PARABOLIC EQUATION ON GENERAL DOMAIN

The nonoxerlapping domain deoomposition method for parabolic partial differential equation on general domain is considered. A kind of domain decomposition that uses the finite element procedure ks given. The problem.over the domains can be implemented on parallel computer. Convergence analysis is also presented.     

Preconditioning nonconforming finite element methods for treating Dirichlet boundary conditions. II

Summary This work deals with theH ¹ condition numbers and the distribution of theB _h singular values of the preconditioned operators {B _h ^–1 A _h }_{0, whereA h andB h are finite element discretizations of second order elliptic operators,A andB respectively.B is also assumed to be self-adjoint and positive definite. For conforming finite elements, Parter and Wong have shown that the singular values cluster in a positive finite interval. Goldstein also has derived results on the spectral distribution ofB h ^–1 A h using a different approach. As a generalization of the results of Parter and Wong, the current work includes nonconforming finite element methods which deal with Dirichlet boundary conditions. It will be shown that, in this more general setting, the singular values also cluster in a positive finite interval. In particular, if the leading part ofB is the same as the leading part ofA, then the singular values cluster about the point {1}. Two specific methods are given as applications of this theory. They are the penalty method of Babuka and the method of nearly zero boundary conditions of Nitsche. Finally, it will be shown that the same results can be proven by an approach generalized from the work of Goldstein.This research was supported by the National Science Foundation under grant number DMS-8913091.}     

Additive Schwarz methods for thep-version finite element method

Summary In this paper, we study some additive Schwarz methods (ASM) for thep-version finite element method. We consider linear, scalar, self adjoint, second order elliptic problems and quadrilateral elements in the finite element discretization. We prove a constant bound independent of the degreep and the number of subdomainsN, for the condition number of the ASM iteration operator. This optimal result is obtained first in dimension two. It is then generalized to dimensionn and to a variant of the method on the interface. Numerical experiments confirming these results are reported. As is the case for other additive Schwarz methods, our algorithms are highly parallel and scalable.This work was supported in part by the Applied Math. Sci. Program of the U.S. Department of Energy under contract DE-FG02-88ER25053 and, in part, by the National Science Foundation under Grant NSF-CCR-9204255     

Analysis of a one-dimensional free boundary flow problem

A one-dimensional free surface problem is considered. It consists in Burgers’ equation with an additional diffusion term on a moving interval. The well-posedness of the problem is investigated and existence and uniqueness results are obtained locally in time. A semi-discretization in space with a piecewise linear finite element method is considered. A priori and a posteriori error estimates are given for the semi-discretization in space. A time splitting scheme allows to obtain numerical results in agreement with the theoretical investigations.Supported by the Swiss National Science Foundation     

PreconditioningP 1 nonconforming finite elements: Condition numbers and singular value distributions

Summary This work deals with the condition numbers and the distribution of theB _h singular values of the preconditioned operators {B _h ^–1 A _h }_{0, whereA h andB h are discretizations of second order elliptic operatorsA andB usingP 1 nonconforming finite elements of Crouzeix and Raviart.B is also assumed to be self-adjoint and positive definite. For conforming finite elements, Parter and Wong have shown that the singular values cluster in a positive finite interval. These reults are being extended to the aforementioned nonconforming finite elements. It will be shown that, for quasiuniform grids, theB h singular values are bounded above and below by positive constants which are independent of the grid sizeh. Moreover, they also cluster in a smaller but usually estimable interval. Issues of implementation are also discussed.This research was supported by the National Science Foundation under grant number DMS-8913091}     

An approximation of incompressible miscible displacement in porous media by mixed finite element method and characteristics-mixed finite element method

An approximation scheme is defined for incompressible miscible displacement in porous media. This scheme is constructed by using two methods. Standard mixed finite element is used for the Darcy velocity equation. A characteristics-mixed finite element method is presented for the concentration equation. Characteristic approximation is applied to handle the convection part of the concentration equation, and a lowest-order mixed finite element spatial approximation is adopted to deal with the diffusion part. Thus, the scalar unknown concentration and the diffusive flux can be approximated simultaneously. In order to derive the optimal L²$L^2$-norm error estimates, a post-processing step is included in the approximation to the scalar unknown concentration. This scheme conserves mass globally; in fact, on the discrete level, fluid is transported along the approximate characteristics. Numerical experiments are presented finally to validate the theoretical analysis.     

Co-volume methods for degenerate parabolic problems

Summary A complementary volume (co-volume) technique is used to develop a physically appealing algorithm for the solution of degenerate parabolic problems, such as the Stefan problem. It is shown that, these algorithms give rise to a discrete semigroup theory that parallels the continuous problem. In particular, the discrete Stefan problem gives rise to nonlinear semigroups in both the discreteL ¹ andH ^–1 spaces.The first author was supported by a grant from the Hughes foundation, and the second author was supported by the National Science Foundation Grant No. DMS-9002768 while this work was undertaken. This work was supported by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.     

On conjugate gradient type methods and polynomial preconditioners for a class of complex non-hermitian matrices

Summary We consider conjugate gradient type methods for the solution of large linear systemsA x=b with complex coefficient matrices of the typeA=T+iI whereT is Hermitian and a real scalar. Three different conjugate gradient type approaches with iterates defined by a minimal residual property, a Galerkin type condition, and an Euclidean error minimization, respectively, are investigated. In particular, we propose numerically stable implementations based on the ideas behind Paige and Saunder's SYMMLQ and MINRES for real symmetric matrices and derive error bounds for all three methods. It is shown how the special shift structure ofA can be preserved by using polynomial preconditioning, and results on the optimal choice of the polynomial preconditioner are given. Also, we report on some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation.This work was supported in part by Cooperatives Agreement NCC 2-387 between the National Aeronautics and Space Administration (NASA) and the Universities Space Research Association (USRA) and by National Science Foundation Grant DCR-8412314     

Quadratic spline collocation methods for elliptic partial differential equations

We consider Quadratic Spline Collocation (QSC) methods for linear second order elliptic Partial Differential Equations (PDEs). The standard formulation of these methods leads to non-optimal approximations. In order to derive optimal QSC approximations, high order perturbations of the PDE problem are generated. These perturbations can be applied either to the PDE problem operators or to the right sides, thus leading to two different formulations of optimal QSC methods. The convergence properties of the QSC methods are studied. OptimalO(h ^3–j ) global error estimates for thejth partial derivative are obtained for a certain class of problems. Moreover,O(h ^4–j ) error bounds for thejth partial derivative are obtained at certain sets of points. Results from numerical experiments verify the theoretical behaviour of the QSC methods. Performance results also show that the QSC methods are very effective from the computational point of view. They have been implemented efficiently on parallel machines.This research was supported in part by David Ross Foundation (U.S.A) and NSERC (Natural Sciences and Engineering Research Council of Canada).     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

A new class of Zienkiewicz-type non-conforming element in any dimensions

In this paper, a new class of Zienkiewicz-type non-conforming finite element, in n spatial dimensions with n ≥ 2, is proposed. The new finite element is proved to be convergent for the biharmonic equation. The work was supported by the National Natural Science Foundation of China (10571006). This work was supported in part by NSF DMS-0209497 and NSF DMS-0215392 and the Changjiang Professorship through Peking University.     

Error estimates for a mixed finite volume method for the p-Laplacian problem

In this work we propose and analyze a mixed finite volume method for the p-Laplacian problem which is based on the lowest order Raviart–Thomas element for the vector variable and the P1 nonconforming element for the scalar variable. It is shown that this method can be reduced to a P1 nonconforming finite element method for the scalar variable only. One can then recover the vector approximation from the computed scalar approximation in a virtually cost-free manner. Optimal a priori error estimates are proved for both approximations by the quasi-norm techniques. We also derive an implicit error estimator of Bank–Weiser type which is based on the local Neumann problems.This work was supported by the Post-doctoral Fellowship Program of Korea Science & Engineering Foundation (KOSEF).