Adaptive sparse grid algorithms with applications to electromagnetic scattering under uncertainty

We discuss adaptive sparse grid algorithms for stochastic differential equations with a particular focus on applications to electromagnetic scattering by structures with holes of uncertain size, location, and quantity. Stochastic collocation (SC) methods are used in combination with an adaptive sparse grid approach based on nested Gauss-Patterson grids. As an error estimator we demonstrate how the nested structure allows an effective error estimation through Richardson extrapolation. This is shown to allow excellent error estimation and it also provides an efficient means by which to estimate the solution at the next level of the refinement. We introduce an adaptive approach for the computation of problems with discrete random variables and demonstrate its efficiency for scattering problems with a random number of holes. The results are compared with results based on Monte Carlo methods and with Stroud based integration, confirming the accuracy and efficiency of the proposed techniques.     

Computation of oscillating integrals

An adaptive quadrature method for the automatic computation of integrals with strongly oscillating integrand is presented. The integration method is based on a truncated Chebyshev series approximation. The algorithm uses a global subinterval division strategy. There is a protection against the influence of round-off errors. A Fortran implementation of the algorithm is given.     

Singularity cancellation method for time-domain boundary element formulation of elastodynamics: A direct approach

In the implementation of time-domain boundary element method for elasto-dynamic problems, there are two types of singularities: the wave front singularity arising when the product of wave velocity and time is equal to the distance between the source point and the field point, and the spatial singularity arising when the source point coincides with the field point. In this paper, the singularity of the first type in the integrand is eliminated by an analytical integration over time, Cauchy principal value and Hadamard finite part integral. Four types of singularities with different orders appear in the integrand after analytical time integration. In order to accurately calculate the integral, in which the integrand is piecewise continuous, the integral domain is subdivided into several patches based on the relation between the product of wave velocity and time and the distance. In singular patches, the integrands are separated into a regular part and a singular part. The regular part can be computed by traditional numerical integration method such as Gaussian integration, while the singular part can be analytically integrated. Using the proposed method, the spatial singular integrals can be calculated directly. Numerical examples using various kinds of elements are presented to verify the proposed method.     

Cubature of integrands containing derivatives

We present a new technique for the numerical integration over , a square or triangle, of an integrand of the form . This uses only function values of , , and , avoiding explicit differentiation, but is suitable only when the integrand function is regular over . The technique is analogous to Romberg integration, since it is based on using a sequence of very simple discretizations of the required integral and applying extrapolation in to provide closer approximations. A general approach to the problem of constructing discretizations is given. We provide specific cost-effective discretizations satisfying familiar, but somewhat arbitrary guidelines. As in Romberg integration, when each component function in the integrand is a polynomial, this technique leads to an exact result. Received May 10, 1996 / Revised version received November 20, 1996     

The semi-analytical method for time-dependent wave problems with uncertainties

This paper provides a constructive procedure for the computation of approximate solutions of random time-dependent hyperbolic mean square partial differential problems. Based on the theoretical representation of the solution as an infinite random improper integral, obtained via the random Fourier transform method, a double approximation process is implemented. Firstly, a random Gauss-Hermite quadrature is applied, and then, the evaluations at the nodes of the integrand are approximated by using a random Störmer numerical method. Numerical results are illustrated with examples.     

The Construction of cubature rules for multivariate highly oscillatory integrals

We present an efficient approach to evaluate multivariate highly oscillatory integrals on piecewise analytic integration domains. Cubature rules are developed that only require the evaluation of the integrand and its derivatives in a limited set of points. A general method is presented to identify these points and to compute the weights of the corresponding rule.

The accuracy of the constructed rules increases with increasing frequency of the integrand. For a fixed frequency, the accuracy can be improved by incorporating more derivatives of the integrand. The results are illustrated numerically for Fourier integrals on a circle and on the unit ball, and for more general oscillators on a rectangular domain.

     

Numerical integration of functions with poles near the interval of integration

An automatic quadrature scheme is presented for approximating integrals of functions that are analytic in the interval of integration but contain pole (or poles) of order 2, i.e., a double pole on the real axis or a complex conjugate pair of double poles, near the interval of integration. The present scheme is based on product integration rules of interpolatory type, using function values of the abscissae only in the interval of integration. The integral is approximated and evaluated by using recurrence relations and some extrapolation method after the smooth part of the integrand is expanded in terms of the Chebyshev polynomials. The fast Fourier transform (FFT) technique is used to generate efficiently the sequence of the finite Chebyshev series expansions until an approximation of the integral satisfying the required tolerance is obtained with an adequate estimate of the error. Numerical examples are included to illustrate the performance of the method.     

A hybrid approach for the integration of a rational function

A hybrid integration algorithm obtaining an indefinite integral of a rational function (say q/r, q and r are polynomials) with floating-point but real coefficients is proposed. The algorithm consists of four steps and is based on combinations of symbolic and numeric computations (hybrid computation). The first step is a hybrid preprocessing stage. An integrand is decomposed into rational and logarithmic parts by using an approximate Horowitz' method which allows floating-point coefficients. Here, we replace the Euclidean GCD algorithm with an approximate-GCD algorithm which was proposed by Sasaki and Noda recently. It is easy to integrate the rational part. The logarithmic part is integrated numerically in the second step. Zeros of a denominator of it are computed by the numerical Durand-Kerner method which computes all zeros of a polynomial equation simultaneously. The integrand is then decomposed into partial fractions in the third step. Coefficients of partial fractions are determined by residue theory. Finally, in the fourth step, partial fractions are transformed into the resulting indefinite integral by using well-known rules of integrals. The hybrid algorithm proposed here gives both indefinite integrals and accurate values of definite integrals. Numerical errors in the hybrid algorithm depend only on errors in the second step. The algorithm evaluates some problems where numerical methods are inefficient or incapable, or a pure symbolic method is theoretically insufficient.     

Construction dʼun champ continu de métriques

Adaptive computation using adaptive meshes is now recognized as essential for solving complex PDE problems. This computation requires, at each step, the definition of a continuous metric field to govern the generation of the adapted meshes. In practice, via an appropriate a posteriori error estimation, metrics are calculated at the vertices of the computational domain mesh. In order to obtain a continuous metric field, the discrete field is interpolated in the whole domain mesh. In this Note, a new method for interpolating discrete metric fields, based on a so-called “natural decomposition” of metrics, is introduced. The proposed method is based on known matrix decompositions and is computationally robust and efficient. Some qualitative comparisons with classical methods are made to show the relevance of this methodology.     

偏微分方程的区间小波自适应精细积分法

利用插值小波理论构造了拟Shannon区间小波,并结合外推法给出了一种求解非线性常微分方程组的时间步长自适应精细积分法,在此基础上构造了求解非线性偏微分方程的区间小波自适应精细积分法（AIWPIM）．数值结果表明,该方法在计算精度上优于将小波和四阶Runge-Kutta法组合得到的偏微分方程的数值求解方法,而计算量则相差不大．该文方法通过Burgers方程给出,但适用于一般情形．     

A localic theory of lower and upper integrals

An account of lower and upper integration is given. It is constructive in the sense of geometric logic. If the integrand takes its values in the non‐negative lower reals, then its lower integral with respect to a valuation is a lower real. If the integrand takes its values in the non‐negative upper reals, then its upper integral with respect to a covaluation and with domain of integration bounded by a compact subspace is an upper real. Spaces of valuations and of covaluations are defined. Riemann and Choquet integrals can be calculated in terms of these lower and upper integrals. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Extrapolation methods in numerical integration

Extrapolation methods have been used for many years for numerical integration. The most well-known of these methods is Romberg integration. A survey by Joyce on the use of extrapolation in numerical analysis appeared in 1971 in which a substantial portion is devoted to numerical integration. In this paper, we shall survey progress made in this field since 1971. The topics surveyed include partition-extrapolation methods for dealing with singular integrands, the work of Lyness and others in generating asymptotic expansions for the error functional in one and several dimensions, the work of de Doncker and others on adaptive extrapolation and the work of Sidi and others on the evaluation of highly oscillatory infinite integrals by extrapolation. Other extrapolation techniques will be mentioned briefly.     

Computation of Feynman loop integrals

We address multivariate integration and extrapolation techniques for the computation of Feynman loop integrals. Loop integrals are required for perturbation calculations in high energy physics, as they contribute corrections to the scattering amplitude and the cross section for the collision of elementary particles. We use iterated integration to calculate the multivariate integrals. The combined integration and extrapolation methods aim for an automatic calculation, where little or no analytic manipulation is required before the numeric approximation. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

DECUHR: an algorithm for automatic integration of singular functions over a hyperrectangular region

We describe an automatic cubature algorithm for functions that have a singularity on the surface of the integration region. The algorithm combines an adaptive subdivision strategy with extrapolation. The extrapolation uses a non-uniform subdivision that can be directly incorporated into the subdivision strategy used for the adaptive algorithm. The algorithm is designed to integrate a vector function over ann-dimensional rectangular region and a FORTRAN implementation is included.Supported by the Norwegian Research Council for Science and the Humanities.     

On the estimation of multi-dimensional integrals with strongly oscillating integrands

The estimation of integrals with rapidly oscillating integrands is difficult, as positive and negative contributions will cancel nearly completely. The effect becomes more pronounced as the number of dimensions of the region of integration is increased. The article shows how an integral over ann-dimensional region can be reduced to integrals over itsn?1 dimensional surfaces in such a manner that the oscillating character of the integrand is taken into account. The method can be interpreted as the repeated application of integration by parts along lines normal to the wave fronts which are determined by the integrand. The remaining integral is estimated by the second mean value theorem of integral calculus. The integrations by parts appear only indirectly in the form of an application of Gauss' integral theorem to a vector field which is determined by the integrand.     

Global extrapolation with a parallel splitting method

Extrapolation with a parallel splitting method is discussed. The parallel splitting method reduces a multidimensional problem into independent one-dimensional problems and can improve the convergence order of space variables to an order as high as the regularity of the solution permits. Therefore, in order to match the convergence order of the space variables, a high order method should also be used for the time integration. Second and third order extrapolation methods are used to improve the time convergence and it was found that the higher order extrapolation method can produce a more accurate solution than the lower order extrapolation method, but the convergence order of high order extrapolation may be less than the actual order of the extrapolation. We also try to show a fact that has not been studied in the literature, i.e. when the extrapolation is used, it may decrease the convergence of the space variables. The higher the order of the extrapolation method, the more it decreases the convergence of the space variables. The global extrapolation method also improves the parallel degree of the parallel splitting method. Numerical tests in the paper are done in a domain of a unit circle and a unit square.Supported by the Academy of Finland.     

Convergence of a step-doubling Galerkin method for parabolic problems

We analyze a single step method for solving second-order parabolic initial-boundary value problems. The method uses a step-doubling extrapolation scheme in time based on backward Euler and a Galerkin approximation in space. The technique is shown to be a second-order correct approximation in time. Since step-doubling can be used as a mechanism for step-size control, the analysis is done for variable time steps. The stability properties of step-doubling are contrasted with those of Crank-Nicolson, as well as those of more general extrapolated theta-weighted schemes. We provide an example computation that illustrates both the use of step-doubling for adaptive time step control and the application of step-doubling to a nonlinear system.

     

An Alternative Strategy for Cautions Adaptive Quadrature

An algorithm for adaptive quadrature is presented which attemptsto ensure that the quadrature used is valid for the behaviourof the integrand. This is achieved by using another algorithmto examine the finite differences of the integrand. The orderof the quadrature and the interval subdivision strategy usedform an integral part of this algorithm. The resulting adaptivequadrature algorithm is very reliable while its efficiency appearsto be of the order of other adaptive quadrature algorithms inthe literature.     

On solving general algebraic equations by integrals of elementary functions

We obtain an integral formula for a solution to a general algebraic equation. In this formula the integrand is an elementary function and integration is carried out over an interval. The advantage of this formula over the well-known Mellin formula is that the integral has a broader convergence domain. This circumstance makes it possible to describe the monodromy of a solution for trinomial equations.     

Simple Monte Carlo and the Metropolis algorithm

We study the integration of functions with respect to an unknown density. Information is available as oracle calls to the integrand and to the non-normalized density function. We are interested in analyzing the integration error of optimal algorithms (or the complexity of the problem) with emphasis on the variability of the weight function. For a corresponding large class of problem instances we show that the complexity grows linearly in the variability, and the simple Monte Carlo method provides an almost optimal algorithm. Under additional geometric restrictions (mainly log-concavity) for the density functions, we establish that a suitable adaptive local Metropolis algorithm is almost optimal and outperforms any non-adaptive algorithm.