Sparse convolution quadrature for time domain boundary integral formulations of the wave equation

S. A. Sauter Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland ^{Many important physical applications are governed by the waveequation. The formulation as time domain boundary integral equationsinvolves retarded potentials. For the numerical solution ofthis problem, we employ the convolution quadrature method forthe discretization in time and the Galerkin boundary elementmethod for the space discretization. We introduce a simple apriori cut-off strategy where small entries of the system matricesare replaced by zero. The threshold for the cut-off is determinedby an a priori analysis which will be developed in this paper.This analysis will also allow to estimate the effect of additionalperturbations such as panel clustering and numerical integrationon the overall discretization error. This method reduces thestorage complexity for time domain integral equations from O(M2N)to O(M2N logM), where N denotes the number of time steps andM is the dimension of the boundary element space.}     

A Fourth-order Tridiagonal Finite Difference Method for General Two-point Boundary Value Problems with Non-linear Boundary Conditions

We present a fourth-order finite difference method for the generalsecond-order nonlinear differential equation y^" = f(x, y, y‘)subject to non-linear two-point boundary conditions g₁(y(a), — y^’()) = 0, g₂(y(b), y'(b)) = 0. When both the differential equation and the boundary conditionsare linear, the method leads to a tridiagonal linear system.We show that the finite difference method is O(h⁴)-convergent.Numerical examples are given to illustrate the method and itsfourth-order convergence. The present paper extends the methodgiven in Chawla (1978) to the case of non-linear boundary conditions.     

Supraconvergence of a finite difference scheme for solutions in Hs(0, L)

^** Email: silvia{at}mat.uc.pt^*** Email: ferreira{at}mat.uc.pt^**** Email: grigo{at}math.tu-berlin.de In this paper we study the convergence of a centred finite differencescheme on a non-uniform mesh for a 1D elliptic problem subjectto general boundary conditions. On a non-uniform mesh, the schemeis, in general, only first-order consistent. Nevertheless, weprove for s (1/2, 2] order O(h^s)-convergence of solution andgradient if the exact solution is in the Sobolev space H^1+s(0,L), i.e. the so-called supraconvergence of the method. It isshown that the scheme is equivalent to a fully discrete linearfinite-element method and the obtained convergence order isthen a superconvergence result for the gradient. Numerical examplesillustrate the performance of the method and support the convergenceresult.     

Overcoming the boundary effects in surface spline interpolation

Surface spline interpolation when the domain is all of R^d isknown to converge much faster to the data function f than inthe case when the domain is the unit ball. This difference isunderstood to be due to boundary effects which, as will be shown,also affect the size of the surface spline's coefficients. Wepropose a modified form of surface spline interpolation which,to a great extent, overcomes these boundary effects. This modifiedsurface spline interpolant uses only the values of f at thegiven interpolation points.     

A Fourth-order Tridiagonal Finite Difference Method for General Non-linear Two-point Boundary Value Problems with Mixed Boundary Conditions

We present a new fourth-order finite difference method for thegeneral second-order non-linear differential equation y^N = f(x,y, y') subject to mixed two-point boundary conditions. An interestingfeature of our method is that each discretization of the differentialequation at an interior grid point is based on just three evaluationsof f. We establish, under appropriate conditions, O(h⁴)-convergenceof the finite difference scheme. In the case of linear differentialequations, our finite difference scheme leads to tridiagonallinear systems. Numerical examples are considered to demonstratecomputationally the fourth order of the method.     

A finite element method for a unidimensional single-phase nonlinear free boundary problem in groundwater flow

Consider a unidimensional, single-phase nonlinear Stefan problemwith nonlinear source and permeance terms, and a Dirichlet boundarycondition depending on the free boundary function. This problemis important in groundwater flow. By immobilizing the free boundarywith the help of a Landau-type transformation, together witha homogeneous transformation dealing with the nonhomogeneousDirichlet boundary condition, an H¹-finite element method forthe problem is proposed and analyzed. Global existence of theapproximate solution is established, and optimal error estimatesin L², L, H¹ and H² norms are derived for both semi-discreteand fully discrete schemes.     

Locking-free DGFEM for elasticity problems in polygons

The h-version of the discontinuous Galerkin finite element method(h-DGFEM) for nearly incompressible linear elasticity problemsin polygons is analysed. It is proved that the scheme is robust(locking-free) with respect to volume locking, even in the absenceof H²-regularity of the solution. Furthermore, it is shown thatan appropriate choice of the finite element meshes leads torobust and optimal algebraic convergence rates of the DGFEMeven if the exact solutions do not belong to H².     

Boundary Accessibility of a Domain Quasiconformally Equivalent to a Ball

A boundary point of a domain D in Rⁿ is said to be broadly accessibleif it ‘almost lies’ on the boundary of a round ballcontained in D. If f is a quasiconformal mapping of the unitball Bⁿ onto D, then it is shown that broadly accessible boundarypoints on D correspond under f to a set of full measure on Bⁿ.2000 Mathematics Subject Classification 30C65.     

An iterative method for a Cauchy problem for the heat equation

^** Email: tomjo{at}itn.liu.se An iterative method for reconstruction of the solution to aparabolic initial boundary value problem of second order fromCauchy data is presented. The data are given on a part of theboundary. At each iteration step, a series of well-posed mixedboundary value problems are solved for the parabolic operatorand its adjoint. The convergence proof of this method in a weightedL²-space is included.     

A Sixth-order Tridiagonal Finite Difference Method for General Non-linear Two-point Boundary Value Problems

We present a sixth-order finite difference method for the generalsecond-order non-linear differential equation Y"=f(x, y, y')subject to the boundary conditions y(a) = A, y(b) = B. In thecase of linear differential equations, our finite differencescheme leads to tridiagonal linear systems. We establish, underappropriate conditions, O(h⁶)-convergence of the finite differencescheme. Numerical examples are given to illustrate the methodand its sixth-order convergence.     

On the Completeness of Sets of Solutions to the Helmholtz Equation

Completeness in L²(D) is established for sets of functions formedfrom solutions to the two-dimensional Helmholtz equation ina domain D. Each function is a linear combination of a solution(found by separation of variables) and its normal derivativeon D, so the sets may be used to solve impedance-type boundaryvalue problems. Sets that contain either regular Bessel functionsor singular Hankel functions are considered. Methods of proofare employed that provide alternatives to the conventional potential-theoreticapproaches. In the majority of cases, the domain of interestis bounded and simply connected. One completeness result fora bounded, doubly-connected domain is proved. In some circumstances,one of the methods leads to a mild but inessential eigenvaluerestriction.     

Stationary Critical Points of the Heat Flow in Spaces of Constant Curvature

The paper considers stationary critical points of the heat flowin sphere S^N and in hyperbolic space H^N, and proves severalresults corresponding to those in Euclidean space R^N which havebeen proved by Magnanini and Sakaguchi. To be precise, it isshown that a solution u of the heat equation has a stationarycritical point, if and only if u satisfies some balance lawwith respect to the point for any time. In Cauchy problems forthe heat equation, it is shown that the solution u has a stationarycritical point if and only if the initial data satisfies thebalance law with respect to the point. Furthermore, one point,say x₀, is fixed and initial-boundary value problems are consideredfor the heat equation on bounded domains containing x₀. It isshown that for any initial data satisfying the balance law withrespect to x₀ (or being centrosymmetric with respect to x₀)the corresponding solution always has x₀ as a stationary criticalpoint, if and only if the domain is a geodesic ball centredat x₀ (or is centrosymmetric with respect to x₀, respectively).     

A Method for the Numerical Solution of Problems Governed by Elliptic Systems in the Cut Plane

A method is derived for the numerical solution of boundary-valueproblems governed by systems of second order linear ellipticpartial differential equations in two independent variables.The boundary of the region in ²under consideration is requiredto consist of two parts. The first part is a straight cut offinite length while the second part C consists of an arbitrarycontour surrounding The solution to a particular boundary-valueproblem is expressed in terms of an integral taken around C.This integral may be evaluated numerically. The method shouldbe particularly useful for the solution of crack problems inanisotropic thermostatics and elastostatic     

Numerical approximation of the boundary control for the wave equation with mixed finite elements in a square

Sorin Micu ^{This paper studies the numerical approximation of the boundarycontrol for the wave equation in a square domain. It is knownthat the discrete and semi-discrete models obtained by discretizingthe wave equation with the usual finite-difference or finite-elementmethods do not provide convergent sequences of approximationsto the boundary control of the continuous wave equation as themesh size goes to zero. Here, we introduce and analyse a newsemi-discrete model based on the space discretization of thewave equation using a mixed finite-element method with two differentbasis functions for the position and velocity. The main theoreticalresult is a uniform observability inequality which allows usto construct a sequence of approximations converging to theminimal L2-norm control of the continuous wave equation. Wealso introduce a fully discrete system, obtained from our semi-discretescheme, for which we conjecture that it provides a convergentsequence of discrete approximations as both h and t, the timediscretization parameter, go to zero. We illustrate this factwith several numerical experiments.}     

A Fast Galerkin Scheme for Linear Integro-differential Equations

We describe an expansion method for the solution of first orderand second order ordinary integro-differential equations, whichis a generalization of the Fast Galerkin scheme for second kindintegral equations (Delves, 1977a; Delves, Abd-Elal & Hendry,1979). The method retains the O(N² In N) operation count ofthat scheme, and pays particular attention to the way in whichthe boundary conditions are incorporated, with the aim of retainingalso the stable structure of the Fast Galerkin equations, andits very rapid convergence. An error analysis, and numericalexamples, indicate that these aims are met.     

On the Approximate Solution of a Diffusion Problem by Galerkin Methods

Discrete-time Galerkin methods are considered for the approximatesolution of a parabolic initial boundary value problem whicharises, for example, in problems involving the diffusion ofa solute into a solid from a stirred solution of fixed volume.Optimal error estimates in the L² and H¹ norms are derived forthe Crank-Nicolson Galerkin method. For the one space variablecase optimal L estimates are also obtained. Results of numericalexperiments are presented and comparisons with finite differenceapproximations are made.     

Sinc-Collection Methods for Two-Point Boundary Value Problems

A collocation method is developed for the approximate solutionof two-point boundary-value problems with mixed boundary conditions.The method is based on replacing the exact solution by a linearcombination of Sinc functions. No integrals need to be evaluatedapproximately when setting up the resulting system of linearequations. The error of the method converges to zero like O(exp(-cN²)),as N, where N is the number of collocation points used, andwhere c is a positive constant independent of N. It is claimedthat the method is superior to the Sinc-Galerkin method dueto its simple implementation and possible extensions to moregeneral boundary-value problems.     

Piecewise Polynomial Approximate Solutions of an Automatic Control Problem

This paper considers piecewise polynomial approximate solutionsof a variational problem in which boundary conditions dependon values on the solution at interior points. The approximatesolutions are shown to converge to the solution of the variationalproblem in the L² and uniform norms, and algorithms for findingthe approximate solutions are obtained. Numerical examples arealso given.     

Initial Motion of the Free Boundary for a Non-linear Diffusion Equation

The free boundary between v > 0 and v = 0 for the porousmedium equation v₁= |v|² +nv²v can remain stationary for somepositive waiting-time and then start moving. It is of interestto know the way in which any part of the boundary first moves.It is already known that if the waiting time is given by purelylocal considerations then the boundary speed is continuous,i.e. the initial speed is zero. For cases where the boundary moves before the time found bysimply considering v(x, 0) close to the boundary, a perturbationanalysis indicates that it starts moving with positive speed.Two-dimensional problems show the possible formation of verticesin the boundary. At these points the normal velocity jumps fromzero to some positive value.     

On the Finite Element Approximation of an Elliptic Variational Inequality Arising from an Implicit Time Discretization of the Stefan Problem

A semi-discretization in time of the weak formulation of thetwo phase Stefan moving boundary problem results in an ellipticboundary value problem with a non-linear jump discontinuitywhich can be set as an elliptic variational inequality. Thepurpose of this paper is to consider a finite element approximationto the inequality. Assuming that the solution is in H² and thatthe length of the free boundary is finite an error estimateis proved. The resulting algebraic problem is one of solvinga system of nonlinear equations associated with a diagonal multivaluedmonotone mapping. An S.O.R. method is given and shown to beglobally convergent.