nag_quad_md_sphere (d01fdc) (PDF version)
d01 Chapter Contents
d01 Chapter Introduction
NAG C Library Manual

NAG Library Function Document

nag_quad_md_sphere (d01fdc)

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_quad_md_sphere (d01fdc) calculates an approximation to a definite integral in up to 30 dimensions, using the method of Sag and Szekeres (see Sag and Szekeres (1964)). The region of integration is an n-sphere, or by built-in transformation via the unit n-cube, any product region.

2  Specification

#include <nag.h>
#include <nagd01.h>
void  nag_quad_md_sphere (Integer ndim,
double (*f)(Integer ndim, const double x[], Nag_Comm *comm),
double sigma,
void (*region)(Integer ndim, const double x[], Integer j, double *c, double *d, Nag_Comm *comm),
Integer limit, double r0, double u, double *result, Integer *ncalls, Nag_Comm *comm, NagError *fail)

3  Description

nag_quad_md_sphere (d01fdc) calculates an approximation to
n-sphere of radius  σ f x1,x2,,xn dx1 dx2 dxn (1)
or, more generally,
c1 d1 dx1 cn dn dxn f x1,,xn (2)
where each ci and di may be functions of xj j<i.
The function uses the method of Sag and Szekeres (1964), which exploits a property of the shifted p-point trapezoidal rule, namely, that it integrates exactly all polynomials of degree <p (see Krylov (1962)). An attempt is made to induce periodicity in the integrand by making a parameterized transformation to the unit n-sphere. The Jacobian of the transformation and all its direct derivatives vanish rapidly towards the surface of the unit n-sphere, so that, except for functions which have strong singularities on the boundary, the resulting integrand will be pseudo-periodic. In addition, the variation in the integrand can be considerably reduced, causing the trapezoidal rule to perform well.
Integrals of the form (1) are transformed to the unit n-sphere by the change of variables:
xi = yi σr tanh ur 1-r2
where r2=i=1nyi2 and u is an adjustable parameter.
Integrals of the form (2) are first of all transformed to the n-cube -1,1n by a linear change of variables
xi=di+ci+di-ciyi/2
and then to the unit sphere by a further change of variables
yi=tanhuzi 1-r
where r2=i=1nzi2 and u is again an adjustable parameter.
The parameter u in these transformations determines how the transformed integrand is distributed between the origin and the surface of the unit n-sphere. A typical value of u is 1.5. For larger u, the integrand is concentrated toward the centre of the unit n-sphere, while for smaller u it is concentrated toward the perimeter.
In performing the integration over the unit n-sphere by the trapezoidal rule, a displaced equidistant grid of size h is constructed. The points of the mesh lie on concentric layers of radius
ri=h4n+8i-1,  i=1,2,3,.
The function requires you to specify an approximate maximum number of points to be used, and then computes the largest number of whole layers to be used, subject to an upper limit of 400 layers.
In practice, the rapidly-decreasing Jacobian makes it unnecessary to include the whole unit n-sphere and the integration region is limited by a user-specified cut-off radius r0<1. The grid-spacing h is determined by r0 and the number of layers to be used. A typical value of r0 is 0.8.
Some experimentation may be required with the choice of r0 (which determines how much of the unit n-sphere is included) and u (which determines how the transformed integrand is distributed between the origin and surface of the unit n-sphere), to obtain best results for particular families of integrals. This matter is discussed further in Section 8.

4  References

Krylov V I (1962) Approximate Calculation of Integrals (trans A H Stroud) Macmillan
Sag T W and Szekeres G (1964) Numerical evaluation of high-dimensional integrals Math. Comput. 18 245–253

5  Arguments

1:     ndimIntegerInput
On entry: n, the number of dimensions of the integral.
Constraint: 1ndim30.
2:     ffunction, supplied by the userExternal Function
f must return the value of the integrand f at a given point.
The specification of f is:
double  f (Integer ndim, const double x[], Nag_Comm *comm)
1:     ndimIntegerInput
On entry: n, the number of dimensions of the integral.
2:     x[ndim]const doubleInput
On entry: the coordinates of the point at which the integrand f must be evaluated.
3:     commNag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to f.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void *. Before calling nag_quad_md_sphere (d01fdc) you may allocate memory and initialize these pointers with various quantities for use by f when called from nag_quad_md_sphere (d01fdc) (see Section 3.2.1 in the Essential Introduction).
3:     sigmadoubleInput
On entry: indicates the region of integration.
sigma0.0
The integration is carried out over the n-sphere of radius sigma, centred at the origin.
sigma<0.0
The integration is carried out over the product region described by region.
4:     regionfunction, supplied by the userExternal Function
If sigma<0.0, region must evaluate the limits of integration in any dimension.
The specification of region is:
void  region (Integer ndim, const double x[], Integer j, double *c, double *d, Nag_Comm *comm)
1:     ndimIntegerInput
On entry: n, the number of dimensions of the integral.
2:     x[ndim]const doubleInput
On entry: x[0],,x[j-2] contain the current values of the first j-1 variables, which may be used if necessary in calculating cj and dj.
3:     jIntegerInput
On entry: the index j for which the limits of the range of integration are required.
4:     cdouble *Output
On exit: the lower limit cj of the range of xj.
5:     ddouble *Output
On exit: the upper limit dj of the range of xj.
6:     commNag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to region.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void *. Before calling nag_quad_md_sphere (d01fdc) you may allocate memory and initialize these pointers with various quantities for use by region when called from nag_quad_md_sphere (d01fdc) (see Section 3.2.1 in the Essential Introduction).
If sigma0.0, region is not called by nag_quad_md_sphere (d01fdc), but the NAG defined null function pointer NULLFN may be supplied.
5:     limitIntegerInput
On entry: the approximate maximum number of integrand evaluations to be used.
Constraint: limit100.
6:     r0doubleInput
On entry: the cut-off radius on the unit n-sphere, which may be regarded as an adjustable parameter of the method.
Suggested value: a typical value is r0=0.8. (See also Section 8.)
Constraint: 0.0<r0<1.0.
7:     udoubleInput
On entry: must specify an adjustable parameter of the transformation to the unit n-sphere.
Suggested value: a typical value is u=1.5. (See also Section 8.)
Constraint: u>0.0.
8:     resultdouble *Output
On exit: the approximation to the integral I.
9:     ncallsInteger *Output
On exit: the actual number of integrand evaluations used. (See also Section 8.)
10:   commNag_Comm *Communication Structure
The NAG communication argument (see Section 3.2.1.1 in the Essential Introduction).
11:   failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_INT
On entry, limit=value.
Constraint: limit100.
On entry, ndim=value.
Constraint: ndim30.
On entry, ndim=value.
Constraint: ndim1.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_REAL
On entry, r0=value.
Constraint: r0<1.0.
On entry, r0=value.
Constraint: r0>0.0.
On entry, u=value.
Constraint: u>0.0.

7  Accuracy

No error estimate is returned, but results may be verified by repeating with an increased value of limit (provided that this causes an increase in the returned value of ncalls).

8  Further Comments

The time taken by nag_quad_md_sphere (d01fdc) will be approximately proportional to the returned value of ncalls, which, except in the circumstances outlined in (b) below, will be close to the given value of limit.
(a) Choice of r0 and u 
If the chosen combination of r0 and u is too large in relation to the machine accuracy it is possible that some of the points generated in the original region of integration may transform into points in the unit n-sphere which lie too close to the boundary surface to be distinguished from it to machine accuracy (despite the fact that r0<1). To be specific, the combination of r0 and u is too large if
ur0 1-r02 >0.3465t-1,   if ​sigma0.0,
or
ur0 1-r0 > 0.3465t- 1,   if ​ sigma< 0.0,
where t is the number of bits in the mantissa of a double number.
The contribution of such points to the integral is neglected. This may be justified by appeal to the fact that the Jacobian of the transformation rapidly approaches zero towards the surface. Neglect of these points avoids the occurrence of overflow with integrands which are infinite on the boundary.
(b) Values of limit and ncalls
limit is an approximate upper limit to the number of integrand evaluations, and may not be chosen less than 100. There are two circumstances when the returned value of ncalls (the actual number of evaluations used) may be significantly less than limit.
Firstly, as explained in (a), an unsuitably large combination of r0 and u may result in some of the points being unusable. Such points are not included in the returned value of ncalls.
Secondly, no more than 400 layers will ever be used, no matter how high limit is set. This places an effective upper limit on ncalls as follows:
n=1: 56 n=2: 1252 n=3: 23690 n=4: 394528 n=5: 5956906

9  Example

This example calculates the integral
s dx1dx2dx3 σ2-r2 =22.2066
where s is the 3-sphere of radius σ, r2=x12+x22+x32 and σ=1.5. Both sphere-to-sphere and general product region transformations are used. For the former, we use r0=0.9 and u=1.5; for the latter, r0=0.8 and u=1.5.

9.1  Program Text

Program Text (d01fdce.c)

9.2  Program Data

Program Data (d01fdce.d)

9.3  Program Results

Program Results (d01fdce.r)


nag_quad_md_sphere (d01fdc) (PDF version)
d01 Chapter Contents
d01 Chapter Introduction
NAG C Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012