NAG FL Interface
d01gdf (md_​numth_​vec)

Settings help

FL Name Style:


FL Specification Language:


1 Purpose

d01gdf calculates an approximation to a definite integral in up to 20 dimensions, using the Korobov–Conroy number theoretic method. This routine is designed to be particularly efficient on vector processors.

2 Specification

Fortran Interface
Subroutine d01gdf ( ndim, vecfun, vecreg, npts, vk, nrand, itrans, res, err, ifail)
Integer, Intent (In) :: ndim, npts, nrand, itrans
Integer, Intent (Inout) :: ifail
Real (Kind=nag_wp), Intent (Inout) :: vk(ndim)
Real (Kind=nag_wp), Intent (Out) :: res, err
External :: vecfun, vecreg
C Header Interface
#include <nag.h>
void  d01gdf_ (const Integer *ndim,
void (NAG_CALL *vecfun)(const Integer *ndim, const double x[], double fv[], const Integer *m),
void (NAG_CALL *vecreg)(const Integer *ndim, const double x[], const Integer *j, double c[], double d[], const Integer *m),
const Integer *npts, double vk[], const Integer *nrand, const Integer *itrans, double *res, double *err, Integer *ifail)
The routine may be called by the names d01gdf or nagf_quad_md_numth_vec.

3 Description

d01gdf calculates an approximation to the integral
I= c1 d1 cn dn f (x1,,xn) dxn dx1 (1)
using the Korobov–Conroy number theoretic method (see Korobov (1957), Korobov (1963) and Conroy (1967)). The region of integration defined in (1) is such that generally ci and di may be functions of x1 , x2 ,, xi-1 , for i= 2 , 3 ,, n , with c1 and d1 constants. The integral is first of all transformed to an integral over the n-cube [0,1] n by the change of variables
xi = ci + (di-ci) yi ,   i= 1 , 2 ,, n .  
The method then uses as its basis the number theoretic formula for the n-cube, [0,1] n :
01 01 g (x1,,xn) dxn dx1 = 1p k=1p g ({ka1p},,{kanp}) - E (2)
where {x} denotes the fractional part of x, a1 ,, an are the so-called optimal coefficients, E is the error, and p is a prime integer. (It is strictly only necessary that p be relatively prime to all a1 ,, an and is in fact chosen to be even for some cases in Conroy (1967).) The method makes use of properties of the Fourier expansion of g (x1,,xn) which is assumed to have some degree of periodicity. Depending on the choice of a1 ,, an the contributions from certain groups of Fourier coefficients are eliminated from the error, E. Korobov shows that a1 ,, an can be chosen so that the error satisfies
ECK p-α ln αβ p (3)
where α and C are real numbers depending on the convergence rate of the Fourier series, β is a constant depending on n, and K is a constant depending on α and n. There are a number of procedures for calculating these optimal coefficients. Korobov imposes the constraint that
a1 = 1   and   ai = ai-1 (mod p) (4)
and gives a procedure for calculating the argument, a, to satisfy the optimal conditions.
In this routine the periodisation is achieved by the simple transformation
xi = yi2 (3-2yi) ,   i= 1 , 2 ,, n .  
More sophisticated periodisation procedures are available but in practice the degree of periodisation does not appear to be a critical requirement of the method.
An easily calculable error estimate is not available apart from repetition with an increasing sequence of values of p which can yield erratic results. The difficulties have been studied by Cranley and Patterson (1976) who have proposed a Monte Carlo error estimate arising from converting (2) into a stochastic integration rule by the inclusion of a random origin shift which leaves the form of the error (3) unchanged; i.e., in the formula (2), {k ai p } is replaced by {αi+k ai p } , for i= 1 , 2 ,, n , where each αi , is uniformly distributed over [0,1] . Computing the integral for each of a sequence of random vectors α allows a ‘standard error’ to be estimated.
This routine provides built-in sets of optimal coefficients, corresponding to six different values of p. Alternatively, the optimal coefficients may be supplied by you. Routines d01gyf and d01gzf compute the optimal coefficients for the cases where p is a prime number or p is a product of two primes, respectively.
This routine is designed to be particularly efficient on vector processors, although it is very important that you also code vecfun and vecreg efficiently.

4 References

Conroy H (1967) Molecular Shroedinger equation VIII. A new method for evaluting multi-dimensional integrals J. Chem. Phys. 47 5307–5318
Cranley R and Patterson T N L (1976) Randomisation of number theoretic methods for mulitple integration SIAM J. Numer. Anal. 13 904–914
Korobov N M (1957) The approximate calculation of multiple integrals using number theoretic methods Dokl. Acad. Nauk SSSR 115 1062–1065
Korobov N M (1963) Number Theoretic Methods in Approximate Analysis Fizmatgiz, Moscow

5 Arguments

1: ndim Integer Input
On entry: n, the number of dimensions of the integral.
Constraint: 1ndim20.
2: vecfun Subroutine, supplied by the user. External Procedure
vecfun must evaluate the integrand at a specified set of points.
The specification of vecfun is:
Fortran Interface
Subroutine vecfun ( ndim, x, fv, m)
Integer, Intent (In) :: ndim, m
Real (Kind=nag_wp), Intent (In) :: x(m,ndim)
Real (Kind=nag_wp), Intent (Out) :: fv(m)
C Header Interface
void  vecfun (const Integer *ndim, const double x[], double fv[], const Integer *m)
1: ndim Integer Input
On entry: n, the number of dimensions of the integral.
2: x(m,ndim) Real (Kind=nag_wp) array Input
On entry: the coordinates of the m points at which the integrand must be evaluated. x(i,j) contains the jth coordinate of the ith point.
3: fv(m) Real (Kind=nag_wp) array Output
On exit: fv(i) must contain the value of the integrand of the ith point, i.e., fv(i)=f (x(i,1),x(i,2),,x(i,ndim)), for i=1,2,,m.
4: m Integer Input
On entry: the number of points m at which the integrand is to be evaluated.
vecfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d01gdf is called. Arguments denoted as Input must not be changed by this procedure.
Note: vecfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d01gdf. If your code inadvertently does return any NaNs or infinities, d01gdf is likely to produce unexpected results.
3: vecreg Subroutine, supplied by the user. External Procedure
vecreg must evaluate the limits of integration in any dimension for a set of points.
The specification of vecreg is:
Fortran Interface
Subroutine vecreg ( ndim, x, j, c, d, m)
Integer, Intent (In) :: ndim, j, m
Real (Kind=nag_wp), Intent (In) :: x(m,ndim)
Real (Kind=nag_wp), Intent (Out) :: c(m), d(m)
C Header Interface
void  vecreg (const Integer *ndim, const double x[], const Integer *j, double c[], double d[], const Integer *m)
1: ndim Integer Input
On entry: n, the number of dimensions of the integral.
2: x(m,ndim) Real (Kind=nag_wp) array Input
On entry: for i=1,2,,m, x(i,1), x(i,2),,x(i,j-1) contain the current values of the first (j-1) coordinates of the ith point, which may be used if necessary in calculating the m values of cj and dj.
3: j Integer Input
On entry: the index j for which the limits of the range of integration are required.
4: c(m) Real (Kind=nag_wp) array Output
On exit: c(i) must be set to the lower limit of the range for x(i,j), for i=1,2,,m.
5: d(m) Real (Kind=nag_wp) array Output
On exit: d(i) must be set to the upper limit of the range for x(i,j), for i=1,2,,m.
6: m Integer Input
On entry: the number of points m at which the limits of integration must be specified.
vecreg must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d01gdf is called. Arguments denoted as Input must not be changed by this procedure.
Note: vecreg should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d01gdf. If your code inadvertently does return any NaNs or infinities, d01gdf is likely to produce unexpected results.
4: npts Integer Input
On entry: the Korobov rule to be used. There are two alternatives depending on the value of npts.
  1. (i)1npts6.
    In this case one of six preset rules is chosen using 2129, 5003, 10007, 20011, 40009 or 80021 points depending on the respective value of npts being 1, 2, 3, 4, 5 or 6.
  2. (ii)npts>6.
    npts is the number of actual points to be used with corresponding optimal coefficients supplied in the array vk.
Constraint: npts1.
5: vk(ndim) Real (Kind=nag_wp) array Input/Output
On entry: if npts>6, vk must contain the n optimal coefficients (which may be calculated using d01gyf or d01gzf).
If npts6, vk need not be set.
On exit: if npts>6, vk is unchanged.
If npts6, vk contains the n optimal coefficients used by the preset rule.
6: nrand Integer Input
On entry: the number of random samples to be generated (generally a small value, say 3 to 5, is sufficient). The estimate, res, of the value of the integral returned by the routine is then the average of nrand calculations with different random origin shifts. If npts>6, the total number of integrand evaluations will be nrand×npts. If 1npts6, the number of integrand evaluations will be nrand×p, where p is the number of points corresponding to the six preset rules. For reasons of efficiency, these values are calculated a number at a time in vecfun.
Constraint: nrand1.
7: itrans Integer Input
On entry: indicates whether the periodising transformation is to be used.
itrans=0
The transformation is to be used.
itrans0
The transformation is to be suppressed (to cover cases where the integrand may already be periodic or where you want to specify a particular transformation in the definition of vecfun).
Suggested value: itrans=0.
8: res Real (Kind=nag_wp) Output
On exit: the approximation to the integral I.
9: err Real (Kind=nag_wp) Output
On exit: the standard error as computed from nrand sample values. If nrand=1, err contains zero.
10: ifail Integer Input/Output
On entry: ifail must be set to 0, −1 or 1 to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of 0 causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of −1 means that an error message is printed while a value of 1 means that it is not.
If halting is not appropriate, the value −1 or 1 is recommended. If message printing is undesirable, then the value 1 is recommended. Otherwise, the value 0 is recommended. When the value -1 or 1 is used it is essential to test the value of ifail on exit.
On exit: ifail=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry ifail=0 or −1, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
ifail=1
On entry, ndim=value.
Constraint: 1ndim20.
ifail=2
On entry, npts=value.
Constraint: npts1.
ifail=3
On entry, nrand=value.
Constraint: nrand1.
ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
ifail=-399
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
ifail=-999
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

If nrand>1, an estimate of the absolute standard error is given by the value, on exit, of err.

8 Parallelism and Performance

d01gdf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

d01gdf performs the same computation as d01gcf. However, the interface has been modified so that it can perform more efficiently on machines with vector processing capabilities. In particular, vecfun and vecreg must calculate the integrand and limits of integration at a set of points. For some problems the amount of time spent in these two subroutines, which must be supplied by you, may account for a significant part of the total computation time. For this reason it is vital that you consider the possibilities for vectorization in the code supplied for these two subroutines.
The time taken will be approximately proportional to nrand×p, where p is the number of points used, but may depend significantly on the efficiency of the code provided by you in vecfun and vecreg.
The exact values of res and err on return will depend (within statistical limits) on the sequence of random numbers generated within d01gdf by calls to g05saf. Separate runs will produce identical answers.

10 Example

This example calculates the integral
01 01 01 01 cos(0.5+2(x1+x2+x3+x4)-4) dx1 dx2 dx3 dx4 .  

10.1 Program Text

Program Text (d01gdfe.f90)

10.2 Program Data

None.

10.3 Program Results

Program Results (d01gdfe.r)