Singular integral transforms and fast numerical algorithms

Fast algorithms for the accurate evaluation of some singular integral operators that arise in the context of solving certain partial differential equations within the unit circle in the complex plane are presented. These algorithms are generalizations and extensions of a fast algorithm of Daripa [11]. They are based on some recursive relations in Fourier space and the FFT (Fast Fourier Transform), and have theoretical computational complexity of the order O(N) per point, where N² is the total number of grid points. An application of these algorithms to quasiconformal mappings of doubly connected domains onto annuli is presented in a follow-up paper.     

Conjugate function method for numerical conformal mappings

We present a method for numerical computation of conformal mappings from simply or doubly connected domains onto so-called canonical domains, which in our case are rectangles or annuli. The method is based on conjugate harmonic functions and properties of quadrilaterals. Several numerical examples are given.     

Numerische Ermittlung quasikonformer Abbildungen mit finiten Elementen

Summary In this note we consider so called p-analytic mappings of simply or doubly connected domains on rectangles or circular rings. Real and imaginary parts of the mappings can be described by minimal-principles. By minimizing the corresponding functionals in a class of linear or bilinear finite elements we obtain an approximation of the mapping and also upper and lower bounds for the p-module of a domain with polygonal boundary. Error bounds are given for smooth and for piecewise constant functionsp. We present numerical experiments.

     

Doubly Connected Minimal Surfaces and Extremal Harmonic Mappings

The concept of a conformal deformation has two natural extensions: quasiconformal and harmonic mappings. Both classes do not preserve the conformal type of the domain, however they cannot change it in an arbitrary way. Doubly connected domains are where one first observes nontrivial conformal invariants. Herbert Gr?tzsch and Johannes C.C.?Nitsche addressed this issue for quasiconformal and harmonic mappings, respectively. Combining these concepts we obtain sharp estimates for quasiconformal harmonic mappings between doubly connected domains. We then apply our results to the Cauchy problem for minimal surfaces, also known as the Bj?rling problem. Specifically, we obtain a sharp estimate of the modulus of a doubly connected minimal surface that evolves from its inner boundary with a given initial slope.     

Baryzentrische Formeln zur trigonometrischen Interpolation (II) Stabilität und Anwendung auf die Fourieranalyse bei ungleichabständigen Stützstellen

Summary In Part I we have presented barycentric formulas for trigonometric interpolation. Here we show that these formulas make it possible to calculate Fourier coefficients easily and efficiently. The only inconvenience is their instability when the number of interpolating points becomes large; this instability can be avoided in a special case. The formulas can be used to approximate the inverse of a periodic function, for instance of the boundary correspondence function in numerical conformal mapping.

---

Résumé Dans la première partie, nous avons présenté des formules barycentriques pour l'interpolation trigonométrique. Ici, nous montrons que ces formules permettent une analyse de Fourier particuliérement simple et efficiente; leur seul inconvénient réside dans leur instabilité lorsque le nombre de noeuds croît, instabilité qui peut être évitée dans un cas particulier. Elles sont applicables à l'approximation de l'inverse d'une fonction périodique, par exemple de la fonction de correspondance des frontières en application conforme numérique.

     

Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems

Summary A forward error analysis is presented for the Björck-Pereyra algorithms used for solving Vandermonde systems of equations. This analysis applies to the case where the points defining the Vandermonde matrix are nonnegative and are arranged in increasing order. It is shown that for a particular class of Vandermonde problems the error bound obtained depends on the dimensionn and on the machine precision only, being independent of the condition number of the coefficient matrix. By comparing appropriate condition numbers for the Vandermonde problem with the forward error bounds it is shown that the Björck-Pereyra algorithms introduce no more uncertainty into the numerical solution than is caused simply by storing the right-hand side vector on the computer. A technique for computing running a posteriori error bounds is derived. Several numerical experiments are presented, and it is observed that the ordering of the points can greatly affect the solution accuracy.     

Axisymmetric free surface seepage

Summary Seepage through porous media in most instances is not a two-dimensional flow phenomenon. One such situation which is investigated herein is the flow from a pond with a bottom formed by the rotation of a curve consisting of a small segment being horizontal and the remainder being an arbitrary convex shaped curve. The approach used to solve this free surface axisymmetric seepage problem is an alternating iteration scheme in conjunction with the Baiocchi transformation and method. The problem is split into two overlapping regions, one in which the free surface is treated and the other in which the singularity is treated. This approach does not require moving meshes and allows a very general prescribed shape for the pond boundary. The numerical approach to the reformulated seepage problem is presented along with several numerical results and comparisons. Also presented is a proof of uniqueness of the solution for such problems provided we make a certain smoothness assumption for the free surface.The alternating iteration scheme is proved to converge provided existence and certain smoothness for the iterates and for their free surfaces are assumed. The iterates involved are solutions of certain complementarity systems. The existence and regularity of these solutions is not investigated in this paper.     

Numerical conformal mapping of multiply connected regions onto the second, third and fourth categories of Koebe?s canonical slit domains

This paper presents a boundary integral method for approximating the conformal mappings from any bounded or unbounded multiply connected region G onto the second, third and fourth categories of Koebe?s canonical slit domains. The method can be also used for calculating the conformal mappings of simply and doubly connected regions. The method is an extension of the author?s method for the first category of Koebe?s canonical slit domains (see [M.M.S. Nasser, Numerical conformal mapping via a boundary integral equation with the generalized Neumann kernel, SIAM J. Sci. Comput. 31 (2009) 1695-1715]). Three numerical examples are presented to illustrate the performance of the proposed method.     

Adams methods for neutral functional differential equations

Summary In this paper Adams type methods for the special case of neutral functional differential equations are examined. It is shown thatk-step methods maintain orderk+1 for sufficiently small step size in a sufficiently smooth situation. However, when these methods are applied to an equation with a non-smooth solution the order of convergence is only one. Some computational considerations are given and numerical experiments are presented.     

Some topics in regenerative steady-state simulation

This paper offers a short introduction to the regenerative method of steady-state simulation output analysis. The paper also contains several new results. In particular, it is shown that regenerative methods necessarily apply to steady-state simulations that are well-posed in a certain precise sense. The paper also describes a bias-reduction algorithm that takes advantage of regenerative structure.     

Perturbation theory and backward error forAX−XB=C

Because of the special structure of the equationsAX–XB=C the usual relation for linear equations backward error = relative residual does not hold, and application of the standard perturbation result forAx=b yields a perturbation bound involving sep (A, B)^–1 that is not always attainable. An expression is derived for the backward error of an approximate solutionY; it shows that the backward error can exceed the relative residual by an arbitrary factor. A sharp perturbation bound is derived and it is shown that the condition number it defines can be arbitrarily smaller than the sep(A, B)^–1-based quantity that is usually used to measure sensitivity. For practical error estimation using the residual of a computed solution an LAPACK-style bound is shown to be efficiently computable and potentially much smaller than a sep-based bound. A Fortran 77 code has been written that solves the Sylvester equation and computes this bound, making use of LAPACK routines.Nuffield Science Research Fellow. This work was carried out while the author was a visitor at the Institute for Mathematics and its Applications, University of Minnesota.     

Parabolic boundary integral operators symbolic representation and basic properties

In this paper we develop a theory of parabolic pseudodifferential operators in anisotropic spaces. We construct a symbolic calculus for a class of symbols globally defined on ⁿ⁺¹× ⁿ⁺¹, and then develop a periodisation procedure for the calculus of symbols on the cylinder ×. We show Gårding's inequality for suitable operators and precise estimates for the essential norm in anisotropic Sobolev spaces. These new mapping properties are needed in localization arguments for the analysis of numerical approximation methods.     

A necessary condition forB-convergence of Runge-Kutta methods

Algebraic stability is a well-known property necessary forB-convergence of a Runge-Kutta method, provided its nodesc _i are such thatc _i – c _j wheneveri j. In this paper a slightly weaker property is established which becomes algebraic stability as soon asc _i – c _j , wheneveri j is excluded.Using this condition it is shown that the Lobatto IIIA methods with more than two stages cannot beB-convergent.This paper was written while the author was visiting the Rijksuniversiteit Leiden in the Netherlands, supported by the Netherlands Organization for Scientific Research (N.W.O.) and by an Erwin Schrödinger scholarship from the Fonds zur Förderung der wissenschaftlichen Forschung.     

Some Ramsey-Turán type results for hypergraphs

To everyk-graphG let(G) be the minimal real number such that for every>0 andn>n ₀(,G) everyk-graphH withn vertices and more than (+) ( ) edges contains a copy ofG. The real number (G) is defined in the same way adding the constraint that all independent sets of vertices inH have sizeo(n). Answering a problem of Erds and Sós it is shown that there exist infinitely manyk-graphs with 0<(G)<(G) for everyk3. It is worth noting that we were unable to find a singleG with the above property.This paper was written while the authors were visiting AT&T Bell Laboratories, Murray Hill, NJ 07974.     

A-stable spline-collocation methods of multivalue type

In this paper the general classV of spline-collocation methods presented by Mülthei is investigated. The methods ofV approximate solutions of first order initial value problems. ClassV contains as subclass the methods of so-called multivalue type, and in particular contains the generalized singly-implicit methods treated by Butcher.Any multivalue type representativeU V yields a matrix valued function corresponding toU, which characterizes the region of absolute stability ofU. If a sequence (U()) of multivalue type representatives ofV tending to some singlevalue type representative V is considered, it can easily be seen by the structure of , that the sequence of the greatest eigenvalues of the (.,) tends to the stability function corresponding to . This fact allows one to construct one-parameter families of A-stable methods of multivalue type.     

Perturbation analysis of the orthogonal procrustes problem

Given two arbitrary real matricesA andB of the same size, the orthogonal Procrustes problem is to find an orthogonal matrixM such that the Frobenius norm MA – B is minimized. This paper treats the common case when the orthogonal matrixM is required to have a positive determinant. The stability of the problem is studied and supremum results for the perturbation bounds are derived.     

Multiple discrete solutions of the incompressible steady-state Navier-Stokes equations

Summary This paper discusses the computation of multiple solutions of various discretizations of the steady state incompressible Navier-Stokes equations. Solution paths (,R) satisfying the discrete system of equationsH(,R)=0, where represents the discrete flow field andR is the Reynolds number, are computed using a pseudo arc-length continuation procedure. For flows over the back end of an axially symmetric body with a cusped tail in a coaxial circular cylinder, the solution paths often exhibit hairpin turning points. Dependence of the paths on the mesh spacing and various selections for the discretizations of the convective and diffusive terms are presented.Dedicated to Professor Ivo Babuka on the occasion of his 60th birthdayThis research was supported in part by the Naval Surface Warfare Center Independent Research Fund, the Naval Sea Systems Command, and the Office for Naval Research under Contracts N001484WR24012 and N0001486R24209, and was performed in part under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under contract number W-7405-ENG-48. Partial support under contract Number W-7405-ENG-48 was provided by the Applied Mathematical Sciences Program of the Office of Energy Research     

$L^2$-Approximations of power and logarithmic functions with applications to numerical conformal mapping

Summary. For a bounded Jordan domain G with quasiconformal boundary L, two-sided estimates are obtained for the error in best polynomial approximation to functions of the form , and , where . Furthermore, Andrievskii's lemma that provides an upper bound for the norm of a polynomial in terms of the norm of is extended to the case when a finite linear combination (independent of n) of functions of the above form is added to . For the case when the boundary of G is piecewise analytic without cusps, the results are used to analyze the improvement in rate of convergence achieved by using augmented, rather than classical, Bieberbach polynomial approximants of the Riemann mapping function of G onto a disk. Finally, numerical results are presented that illustrate the theoretical results obtained. Received September 1, 1999 / Published online August 17, 2001     

Roundoff analyses and sparse data

Summary Techniques are emerging which automatically determine the effects of rounding error upon numerical methods of a certain type. Meaningful testing presupposes a reasonable basis for comparison. Typically, the error's effects upon a given method are compared either (i) with the effects of perturbing the computational problem or (ii) with the effects of rounding error upon a competing method. We show that the result of a type (ii) comparison often remains valid when the two methods are adapted for sparse data, though the comparison might be based upon a model of error propagation which requires that special care be taken. This observation sometimes provides a rationale for preferring comparisons (ii), since the results of type (i) comparisons may well not carry over to sparse data.Partially supported by NSF Grants GJ-42968 and MCS 76-13561 A01