On Cayley-Transform Methods for the Discretization of Lie-Group Equations

In this paper we develop in a systematic manner the theory of time-stepping methods based on the Cayley transform. Such methods can be applied to discretize differential equations that evolve in some Lie groups, in particular in the orthogonal group and the symplectic group. Unlike many other Lie-group solvers, they do not require the evaluation of matrix exponentials. Similarly to the theory of Magnus expansions in [13], we identify terms in a Cayley expansion with rooted trees, which can be constructed recursively. Each such term is an integral over a polytope but all such integrals can be evaluated to high order by using special quadrature formulas similar to the construction in [13]. Truncated Cayley expansions (with exact integrals) need not be time-symmetric, hence the method does not display the usual advantages associated with time symmetry, e.g., even order of approximation. However, time symmetry (with its attendant benefits) is attained when exact integrals are replaced by certain quadrature formulas.     

Error estimates for generalized compound quadrature formulas

We define quadrature formulas for integrals with weight functionsby applying a given approximation method locally. This allowsthe generalisation of different quadrature formulas, e.g., thecompound Newton-Cotes formulas, Gauss summation formulas, orGregory's formulas, to the case of weighted integrals, as wellas to construct new quadrature formulas, and to derive errorestimates for all these quadrature formulas. The estimates consideredhere are mainly of the form |R[f]|c||f^(r)||, provided the underlyingapproximation method is exact for polynomials of degree <r(R[f] is the quadrature error). Explicit, asymptotically sharperror estimates are obtained for arbitrary integrable weightfunctions. Further, estimates are obtained for the case thatthe quadrature error is of higher order than the approximationerror.     

Hybrid Galerkin boundary elements: theory and implementation

Summary. In this paper we present a new quadrature method for computing Galerkin stiffness matrices arising from the discretisation of 3D boundary integral equations using continuous piecewise linear boundary elements. This rule takes as points some subset of the nodes of the mesh and can be used for computing non-singular Galerkin integrals corresponding to pairs of basis functions with non-intersecting supports. When this new rule is combined with standard methods for the singular Galerkin integrals we obtain a “hybrid” Galerkin method which has the same stability and asymptotic convergence properties as the true Galerkin method but a complexity more akin to that of a collocation or Nystr?m method. The method can be applied to a wide range of singular and weakly-singular first- and second-kind equations, including many for which the classical Nystr?m method is not even defined. The results apply to equations on piecewise-smooth Lipschitz boundaries, and to non-quasiuniform (but shape-regular) meshes. A by-product of the analysis is a stability theory for quadrature rules of precision 1 and 2 based on arbitrary points in the plane. Numerical experiments demonstrate that the new method realises the performance expected from the theory. Received January 22, 1998 / Revised version received May 26, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

Discrete boundary element methods on general meshes in 3D

Abstract. This paper is concerned with the stability and convergence of fully discrete Galerkin methods for boundary integral equations on bounded piecewise smooth surfaces in . Our theory covers equations with very general operators, provided the associated weak form is bounded and elliptic on , for some . In contrast to other studies on this topic, we do not assume our meshes to be quasiuniform, and therefore the analysis admits locally refined meshes. To achieve such generality, standard inverse estimates for the quasiuniform case are replaced by appropriate generalised estimates which hold even in the locally refined case. Since the approximation of singular integrals on or near the diagonal of the Galerkin matrix has been well-analysed previously, this paper deals only with errors in the integration of the nearly singular and smooth Galerkin integrals which comprise the dominant part of the matrix. Our results show how accurate the quadrature rules must be in order that the resulting discrete Galerkin method enjoys the same stability properties and convergence rates as the true Galerkin method. Although this study considers only continuous piecewise linear basis functions on triangles, our approach is not restricted in principle to this case. As an example, the theory is applied here to conventional “triangle-based” quadrature rules which are commonly used in practice. A subsequent paper [14] introduces a new and much more efficient “node-based” approach and analyses it using the results of the present paper. Received December 10, 1997 / Revised version received May 26, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

On Quadrature Methods for Highly Oscillatory Integrals and Their Implementation

The main theme of this paper is the construction of efficient, reliable and affordable error bounds for two families of quadrature methods for highly oscillatory integrals. We demonstrate, using asymptotic expansions, that the error can be bounded very precisely indeed at the cost of few extra derivative evaluations. Moreover, in place of derivatives it is possible to use finite difference approximations, with spacing inversely proportional to frequency. This renders the computation of error bounds even cheaper and, more importantly, leads to a new family of quadrature methods for highly oscillatory integrals that can attain arbitrarily high asymptotic order without computation of derivatives. AMS subject classification (2000) Primary 65D30, secondary 34E05.Received June 2004. Accepted October 2004. Communicated by Lothar Reichel.     

Cubature Formulas of a Nonalgebraic Degree of Precision

We deal with cubature formulas that are exact for polynomials and also for polynomials multiplied by r, where r is the Euclidean distance to the origin. A general lower bound for the number of nodes for a specified degree of precision is given. This bound is improved for centrally symmetric integrals. A set of constraints (consistency conditions) is introduced for the construction of fully symmetric formulas. For one dimension and arbitrary degree, it is shown that the lower bound is sharp for centrally symmetric integrals. For higher dimensions, as an illustration, cubature formulas are only constructed for low degrees. March 6, 2000. Date revised: April 30, 2001. Date accepted: May 31, 2001.     

Integral representations for computing real parabolic cylinder functions

Summary. Integral representations are derived for the parabolic cylinder functions U(a,x), V(a,x) and W(a,x) and their derivatives. The new integrals will be used in numerical algorithms based on quadrature. They follow from contour integrals in the complex plane, by using methods from asymptotic analysis (saddle point and steepest descent methods), and are stable starting points for evaluating the functions U(a,x), V(a,x) and W(a,x) and their derivatives by quadrature rules. In particular, the new representations can be used for large parameter cases. Relations of the integral representations with uniform asymptotic expansions are also given. The algorithms will be given in a future paper.Mathematics Subject Classification (2000): 33C15, 41A60, 65D20Revised version received July 25, 2003     

Convergence and computation of simultaneous rational quadrature formulas

We discuss the convergence and numerical evaluation of simultaneous quadrature formulas which are exact for rational functions. The problem consists in integrating a single function with respect to different measures using a common set of quadrature nodes. Given a multi-index n, the nodes of the integration rule are the zeros of the multi-orthogonal Hermite–Padé polynomial with respect to (S, α, n), where S is a collection of measures, and α is a polynomial which modifies the measures in S. The theory is based on the connection between Gauss-type simultaneous quadrature formulas of rational type and multipoint Hermite–Padé approximation. The numerical treatment relies on the technique of modifying the integrand by means of a change of variable when it has real poles close to the integration interval. The output of some tests show the power of this approach in comparison with other ones in use.     

A Systematic “Saddle Point Near a Pole” Asymptotic Method with Application to the Gauss Hypergeometric Function

In recent works [ 1 ] and [ 2 ], we have proposed more systematic versions of the Laplace’s and saddle point methods for asymptotic expansions of integrals. Those variants of the standard methods avoid the classical change of variables and give closed algebraic formulas for the coefficients of the expansions. In this work we apply the ideas introduced in [ 1 ] and [ 2 ] to the uniform method “saddle point near a pole.” We obtain a computationally more systematic version of that uniform asymptotic method for integrals having a saddle point near a pole that, in many interesting examples, gives a closed algebraic formula for the coefficients. The asymptotic sequence is given, in general, in terms of exponential integrals of fractional order (or incomplete gamma functions). In particular, when the order of the saddle point is two, the basic approximant is given in terms of the error function (as in the standard method). As an application, we obtain new asymptotic expansions of the Gauss Hypergeometric function ₂F₁(a, b, c; z) for large b and c with c > b + 1 .     

Error bounds for quadrature methods involving lower order derivatives

Quadrature methods for approximating the definite integral of a function f(t) over an interval [a,b] are in common use. Examples of such methods are the Newton–Cotes formulas (midpoint, trapezoidal and Simpson methods etc.) and the Gauss–Legendre quadrature rules, to name two types of quadrature. Error bounds for these approximations involve higher order derivatives. For the Simpson method, in particular, the error bound involves a fourth-order derivative. Discounting the fact that calculating a fourth-order derivative requires a lot of differentiation, the main concern is that an error bound for the Simpson method, for example, is only relevant for a function that is four times differentiable, a rather stringent condition. This paper caters for functions for which derivatives exist only of order lower than normally required. A number of quadrature methods are considered and error bounds derived involving only lower order derivatives that can be used depending on the smoothness of the function.     

Talbot quadratures and rational approximations

Many computational problems can be solved with the aid of contour integrals containing e ^z in the integrand: examples include inverse Laplace transforms, special functions, functions of matrices and operators, parabolic PDEs, and reaction-diffusion equations. One approach to the numerical quadrature of such integrals is to apply the trapezoid rule on a Hankel contour defined by a suitable change of variables. Optimal parameters for three classes of such contours have recently been derived: (a) parabolas, (b) hyperbolas, and (c) cotangent contours, following Talbot in 1979. The convergence rates for these optimized quadrature formulas are very fast: roughly O(3^-N ), where N is the number of sample points or function evaluations. On the other hand, convergence at a rate apparently about twice as fast, O(9.28903^-N ), can be achieved by using a different approach: best supremum-norm rational approximants to e ^z for z∈(–∞,0], following Cody, Meinardus and Varga in 1969. (All these rates are doubled in the case of self-adjoint operators or real integrands.) It is shown that the quadrature formulas can be interpreted as rational approximations and the rational approximations as quadrature formulas, and the strengths and weaknesses of the different approaches are discussed in the light of these connections. A MATLAB function is provided for computing Cody–Meinardus–Varga approximants by the method of Carathéodory–Fejér approximation. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65D30, 41A20     

Poly-Locality in Quantum Computing

A polynomial depth quantum circuit affects, by definition, a poly-local unitary transformation of a tensor product state space. It is a reasonable belief [Fe], [L], [FKW] that, at a fine scale, these are precisely the transformations which will be available from physics to solve computational problems. The poly-locality of a discrete Fourier transform on cyclic groups is at the heart of Shor's factoring algorithm. We describe a class of poly-local transformations, which include the discrete orthogonal wavelet transforms, in the hope that these may be helpful in constructing new quantum algorithms. We also observe that even a rather mild violation of poly-locality leads to a model without one-way functions, giving further evidence that poly-locality is an essential concept. March 1, 2000. Final version received: October 23, 2001.     

Uniform Asymptotic Expansions of Symmetric Elliptic Integrals

Symmetric standard elliptic integrals are considered when two or more parameters are larger than the others. The distributional approach is used to derive seven expansions of these integrals in inverse powers of the asymptotic parameters. Some of these expansions also involve logarithmic terms in the asymptotic variables. These expansions are uniformly convergent when the asymptotic parameters are greater than the remaining ones. The coefficients of six of these expansions involve hypergeometric functions with less parameters than the original integrals. The coefficients of the seventh expansion again involve elliptic integrals, but with less parameters than the original integrals. The convergence speed of any of these expansions increases for an increasing difference between the asymptotic variables and the remaining ones. All the expansions are accompanied by an error bound at any order of the approximation. January 31, 2000. Date revised: May 18, 2000. Date accepted: August 4, 2000.     

Multi-point Taylor expansions of analytic functions

Taylor expansions of analytic functions are considered with respect to several points, allowing confluence of any of them. Cauchy-type formulas are given for coefficients and remainders in the expansions, and the regions of convergence are indicated. It is explained how these expansions can be used in deriving uniform asymptotic expansions of integrals. The method is also used for obtaining Laurent expansions in several points as well as Taylor-Laurent expansions.

     

Numerical calculation of singular integrals appearing in three-dimensional potential flow problems

Two approximate methods for calculating singular integrals appearing in the numerical solution of three-dimensional potential flow problems are presented. The first method is a self-adaptive, fully numerical method based on special copy formulas of Gaussian quadrature rules. The singularity is treated by refining the partitions of the copy formula in the vicinity of the singular point. The second method is a semianalytic method based on asymptotic considerations. Under the small curvature hypothesis, asymptotic expansions are derived for the integrals that are involved in the calculation of the scalar potential, the velocity as well as the deformation field induced from curved quadrilateral surface elements. Compared to other methods, the proposed integration schemes, when applied to practical flow field calculations, require less computational effort.     

非线性积分方程迭代配置法的渐近展开及其外推

非线性积分方程迭代配置法的渐近展开及其外推韩国强（华南理工大学计算机工程与科学系）ＡＳＹＭＰＴＯＴＩＣＥＲＲＯＲＥＸＭＮＳＩＯＮＳＡＮＤＥＸＴＲＡＰＯＬＡＴＩＯＮＦＯＲＴＨＥＩＴＥＲＡＴＥＤＣＯＬＬＯＣＡＴＩＯＮＭＥＴＨＯＤＳＯＦＮＯＮＬＩＮＥＡＲＩ...     

Numerical evaluation of finite Fourier integrals

A computationally efficient algorithm for evaluating Fourier integrals ∫¹_?1?(x)e^iωxdx using interpolatory quadrature formulas on any set of collocation points is presented. Examples are given to illustrate the performances of interpolatory formulas which are based on the applications of the Fejér, Clenshaw—Curtis, Basu and the Newton—Cotes points. Initially, the formulas for nonoscillatory integrals are generated and then generalizations to finite Fourier integrals are made. Extensions of this algorithm to some other weighted integrals are also considered.     

On some multi-dimensional quadrature formulas with number-theoretic nets

In the present paper some multi-dimensional quadrature formulas of periodic functions are established by means of the number-theoretic method. Some results of Hua and Wang^[2] are generalized or improved.This project is supported by the National Natural Science Foundation of China.     

Sharp quadrature formulas and inequalities between various metrics for rational functions

We obtain the sharp quadrature formulas for integrals of complex rational functions over circles, segments of the real axis, and the real axis itself. Among them there are formulas for calculating the L₂-norms of rational functions. Using the quadrature formulas for rational functions, in particular, for simple partial fractions and polynomials, we derive some sharp inequalities between various metrics (Nikol’ski?-type inequalities).     

Error estimates of anti-Gaussian quadrature formulae

Anti-Gauss quadrature formulae associated with four classical Chebyshev weight functions are considered. Complex-variable methods are used to obtain expansions of the error in anti-Gaussian quadrature formulae over the interval [−1,1]$[-1,1]$. The kernel of the remainder term in anti-Gaussian quadrature formulae is analyzed. The location on the elliptic contours where the modulus of the kernel attains its maximum value is investigated. This leads to effective L^∞$L^{\infty }$-error bounds of anti-Gauss quadratures. Moreover, the effective L¹$L^1$-error estimates are also derived. The results obtained here are an analogue of some results of Gautschi and Varga (1983) [11], Gautschi et al. (1990) [9] and Hunter (1995) [10] concerning Gaussian quadratures.