A Fast Galerkin Algorithm for Singular Integral Equations

A recent paper (Delves, 1977) described a variant of the Galerkinmethod for linear Fredholm integral equations of the secondkind with smooth kernels, for which the total solution timeusing N expansion functions is (N² ln N) compared with the standardGalerkin count of (N³). We describe here a modification of thismethod which retains this operations count and which is applicableto weakly singular Fredholm equations of the form where K₀(x, y) is a smooth kernel and Q contains a known singularity.Particular cases treated in detail include Fredholm equationswith Green's function kernels, or with kernels having logarithmicsingularities; and linear Volterra equations with either regularkernels or of Abel type. The case when g(x) and/or f(x) containsa known singularity is also treated. The method described yieldsboth a priori and a posteriori error estimates which are cheapto compute; for smooth kernels (Q = 1) it yields a modifiedform of the algorithm described in Delves (1977) with the advantagethat the iterative scheme required to solve the equations in(N²) operations is rather simpler than that given there.     

Further Studies of the Application of Constrained Minimization Methods to Fredholm Integral Equations of the First Kind

Permanent address: Department of Mathematics, University of Queensland, Australia. Following earlier work of Babolian & Delves (J. Inst. MathsApplics (1979) 24, 157–174) the Galerkin equations forintegral equations of the first kind are stablized by imposingasympotic decay rates on the expansion coefficients. Results for the formulation in the l₂ norm are compared withresults of Babolian & Delves where the l₁ norm was used. The importance of the choice of the constants which specifythe decay rates is also considered. Theoretical results andcomputational experiments show that previously used automaticselection of these constants needs to be safeguarded by monitoringthe residuals of the Galerkin equations.     

Round-off Errors and Stability in Variational Calculations

We consider the problem of the stability of a variational solutionof a linear, inhomo-geneous operator equation, in the presenceof "round-off" errors in the various inner products involved.For systems which are asymptotically diagonal (see Delves &Mead, 1971; Freeman, Delves & Reid, 1974) we produce boundson the error induced by the round-off noise, which show thatat least for sufficiently small C the solution method is stablein these cases in the sense of Mikhlin (1971) provided thatthe system is normalized ("nice" in the sense of Delves &Mead, 1971). Un-normalized A.D. systems may not be stable, butare relatively stable in a sense defined here. In addition tothese error bounds we produce estimates of the distributionof the round-off errors amongst the expansion coefficients a_i^(N).A numerical example suggests that relative stability is sufficientto ensure good variational behaviour of the calculation.     

Asymptotic Error Expansions for Numerical Solutions of Integral Equations

A general theorem dealing with asymptotic error expansions fornumerical solutions of linear operator equations is proved.This is applied to the Nystr?m, collocation, and Galerkin methodsfor second kind, Fredholm integral equations. For example, weshow that when piecewise polynomials of degree m–1 areused, the iterated Galerkin solution admits an error expansionin even powers of the step-size h, beginning with a term inh^2m.     

A Fast Implementation of the Global Element Method

A straightforward implementation of the Global Element Method(Delves & Hall, 1979) for two-dimensional partial differentialequations has an operation count: Set up equations: (MN⁶); solve: (M³N⁶) where M is the number of elements and N the number of one-dimensionalexpansion functions used in each element. We describe here analternative implementation in which both of these counts arereduced to (MN⁴). The method used generalizes to p dimensions, with operationcount (MN^2p) compared with the "standard" count (MP^3p + M³N^3p).     

A Fast Direct Method for the Least Squares Solution of Slightly Overdetermined Sets of Linear Equations

Noble (1969) has described a method for the solution of N+Mlinear equations in N unknowns, which is based on an initialpartitioning of the matrix A, and which requires only the solutionof square sets of equations. He assumed rank (A) = N. We describehere an efficient implementation of Noble's method, and showthat it generalizes in a simple way to cover also rank deficientproblems. In the common case that the equation is only slightlyoverdetermined (M << N) the resulting algorithm is muchfaster than the standard methods based on M.G.S. or Householderreduction of A, or on the normal equations, and has a very similaroperation count to the algorithm of Cline (1973). Slightly overdetermined systems arise from Galerkin methodsfor non-Hermitian partial differential equations. In these systems,rank (A) = N and advantage can be taken of the structure ofthe matrix A to yield a least squares solution in (N²) operations.     

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 Fast Method for the Solution of Fredholm Integral Equations

Methods described to date for the solution of linear Fredholmintegral equations have a computing time requirement of O(N³),where N is the number of expansion functions or discretizationpoints used. We describe here a Tchebychev expansion method,based on the FFT, which reduces this time to O(N² ln N), andreport some comparative timings obtained with it. We give alsoboth a priori and a posteriori error estimates which are cheapto compute, and which appear more reliable than those used previously.     

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².     

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.     

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.     

Semidiscrete finite element Galerkin approximations to the equations of motion arising in the Oldroyd model

In this paper, a semidiscrete finite element Galerkin methodfor the equations of motion arising in the 2D Oldroyd modelof viscoelastic fluids with zero forcing function is analysed.Some new a priori bounds for the exact solutions are derivedunder realistically assumed conditions on the data. Moreover,the long-time behaviour of the solution is established. By introducinga Stokes–Volterra projection, optimal error bounds forthe velocity in the L(L²) as well as in the L(H¹)-norms andfor the pressure in the L(L²)-norm are derived which are validuniformly in time t > 0.     

A Finite Element Galerkin Method for a Unidimensional Single-Phase Nonlinear Stefan Problem with Dirichlet Boundary Conditions

Based on straightening the free boundary, an H¹-Galerkin methodis proposed and analysed for a single-phase nonlinear Stefanproblem with Dirichlet boundary conditions. Optimal H¹ estimatesfor continuous-time Galerkin approximations are derived.     

A qualocation method for parabolic partial differential equations

In this paper a qualocation method is analysed for parabolicpartial differential equations in one space dimension. Thismethod may be described as a discrete H¹-Galerkin method inwhich the discretization is achieved by approximating the integralsby a composite Gauss quadrature rule. An O (h^4-i) rate of convergencein the W^i.p norm for i = 0, 1 and 1 p is derived for a semidiscretescheme without any quasi-uniformity assumption on the finiteelement mesh. Further, an optimal error estimate in the H² normis also proved. Finally, the linearized backward Euler methodand extrapolated Crank-Nicolson scheme are examined and analysed.     

A Factorization-Related Method for Elliptic Partial Differential Equations with Iterative Improvement

We consider a method for solving elliptic boundary-value problems.The method arises from a finite-difference discretization whichhas one form in the interior region, but is modified near theboundary. This permits the problem to be solved in terms ofsparse upper and lower triangular matrices. The result of thisdirect method is then improved by an iterative technique, whichis further enhanced by a multigrid-type process. For the type of problems we consider here, the total combinedmethod requires only O(N²) time and O(N²) space to compute thesolution of a system of N x N mesh points to good accuracy.The method is applied to a case where normal discretizationleads to a matrix that is not positive definite.     

Local Rigidity of Infinite-Dimensional Teichmuller Spaces

This paper presents a rigidity theorem for infinite-dimensionalBergman spaces of hyperbolic Riemann surfaces, which statesthat the Bergman space A¹(M), for such a Riemann surface M,is isomorphic to the Banach space of summable sequence, l¹.This implies that whenever M and N are Riemann surfaces thatare not analytically finite, and in particular are not necessarilyhomeomorphic, then A¹(M) is isomorphic to A¹(N). It is knownfrom V. Markovic that if there is a linear isometry betweenA¹(M) and A¹(N), for two Riemann surfaces M and N of non-exceptionaltype, then this isometry is induced by a conformal mapping betweenM and N. As a corollary to this rigidity theorem presented here,taking the Banach duals of A¹(M) and l¹ shows that the spaceof holomorphic quadratic differentials on M, Q(M), is isomorphicto the Banach space of bounded sequences, l. As a consequenceof this theorem and the Bers embedding, the Teichmüllerspaces of such Riemann surfaces are locally bi-Lipschitz equivalent.     

Optimal policy for a general repair replacement model: average reward case

For a general repair replacement model, we study two types ofreplacement policy.Replacement policy T replaces the systemat time T since the installation or last replacement, whilereplacement policy N replaces the system at the time of Nthfailure. Let T^* and N^* be the optimal among all policies T andN respectively. Under the expected average reward criterion,then we show that the optimal policy N^* is at least as goodas the optimal policy T^*. Furthermore, for a monotone processmodel, we determine the optimal policy N^* explicitly throughtwo different approaches.     

Shape-preserving interpolation by G1 and G2 PH quintic splines

The interpolation of a planar sequence of points p₀, ..., p_Nby shape-preserving G¹ or G² PH quintic splines with specifiedend conditions is considered. The shape-preservation propertyis secured by adjusting ‘tension’ parameters thatarise upon relaxing parametric continuity to geometric continuity.In the G² case, the PH spline construction is based on applyingNewton–Raphson iterations to a global system of equations,commencing with a suitable initialization strategy—thisgeneralizes the construction described previously in NumericalAlgorithms 27, 35–60 (2001). As a simpler and cheaperalternative, a shape-preserving G¹ PH quintic spline schemeis also introduced. Although the order of continuity is lower,this has the advantage of allowing construction through purelylocal equations.     

Use of extrapolation for improving the order of convergence of eigenelement approximations

We consider the approximation of the eigenelements of a compactintegral operator defined on C[0, 1] with a smooth kernel. Weuse the iterated collocation method based on r Gauss pointsand piecewise polynomials of degree r – 1 on each subintervalof a nonuniform partition of [0, 1]. We obtain asymptotic expansionsfor the arithmetic means of m eigenvalues and also for the associatedspectral projections. Using Richardson extrapolation, we showthat the order of convergence O(h^2r) in the iterated collocationmethod can be improved to O(h^2r+2). Similar results hold forthe Nyström method and for the iterated Galerkin method.We illustrate the improvement in the order of convergence bynumerical experiments.     

Khayyam with Cabri: experiences of pre-service mathematics teachers with Khayyam's solution of cubic equations in dynamic geometry environment

The study reported in this article deals with the observed actionsof Turkish pre-service mathematics teachers in dynamic geometryenvironment (DGE) as they were learning Khayyam's method forsolving cubic equations formed as x³ + ax = b. Having learnedthe method, modelled it in DGE and verified the correctnessof the solution, students generated their own methods for solvingdifferent types of cubic equations such as x³ + ax² = b andx³ + a = bx in the light of Khayyam's method. With the presentedteaching experiment, students realized that Khayyam's mathematicsis different from theirs. We consider that this gave them anopportunity to have an insight about the cultural and socialaspects of mathematics. In addition, the teaching experimentshowed that dynamic geometry software is an excellent tool fordoing mathematics because of their dynamic nature and accurateconstructions. And, it can be easily concluded that the historyof mathematics is useful resource for enriching mathematicslearning environment.