NAG Library Routine Document
d01gcf (md_numth)
1
Purpose
d01gcf calculates an approximation to a definite integral in up to $20$ dimensions, using the Korobov–Conroy number theoretic method.
2
Specification
Fortran Interface
Integer, Intent (In)  ::  ndim, npts, nrand, itrans  Integer, Intent (Inout)  ::  ifail  Real (Kind=nag_wp), External  ::  f  Real (Kind=nag_wp), Intent (Inout)  ::  vk(ndim)  Real (Kind=nag_wp), Intent (Out)  ::  res, err  External  ::  region 

C Header Interface
#include nagmk26.h
void 
d01gcf_ (const Integer *ndim, double (NAG_CALL *f)(const Integer *ndim, const double x[]), void (NAG_CALL *region)(const Integer *ndim, const double x[], const Integer *j, double *c, double *d), const Integer *npts, double vk[], const Integer *nrand, const Integer *itrans, double *res, double *err, Integer *ifail) 

3
Description
d01gcf calculates an approximation to the integral
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
${c}_{i}$ and
${d}_{i}$ may be functions of
${x}_{1},{x}_{2},\dots ,{x}_{i1}$, for
$i=2,3,\dots ,n$, with
${c}_{1}$ and
${d}_{1}$ constants. The integral is first of all transformed to an integral over the
$n$cube
${\left[0,1\right]}^{n}$ by the change of variables
The method then uses as its basis the number theoretic formula for the
$n$cube,
${\left[0,1\right]}^{n}$:
where
$\left\{x\right\}$ denotes the fractional part of
$x$,
${a}_{1},{a}_{2},\dots ,{a}_{n}$ are the socalled optimal coefficients,
$E$ is the error, and
$p$ is a prime integer. (It is strictly only necessary that
$p$ be relatively prime to all
${a}_{1},{a}_{2},\dots ,{a}_{n}$ 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\left({x}_{1},{x}_{2},\dots ,{x}_{n}\right)$ which is assumed to have some degree of periodicity. Depending on the choice of
${a}_{1},{a}_{2},\dots ,{a}_{n}$ the contributions from certain groups of Fourier coefficients are eliminated from the error,
$E$. Korobov shows that
${a}_{1},{a}_{2},\dots ,{a}_{n}$ can be chosen so that the error satisfies
where
$\alpha $ and
$C$ are real numbers depending on the convergence rate of the Fourier series,
$\beta $ is a constant depending on
$n$, and
$K$ is a constant depending on
$\alpha $ and
$n$. There are a number of procedures for calculating these optimal coefficients. Korobov imposes the constraint that
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
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),
$\left\{k\frac{{a}_{i}}{p}\right\}$ is replaced by
$\left\{{\alpha}_{i}+k\frac{{a}_{i}}{p}\right\}$, for
$i=1,2,\dots ,n$, where each
${\alpha}_{i}$, is uniformly distributed over
$\left[0,1\right]$. Computing the integral for each of a sequence of random vectors
$\alpha $ allows a ‘standard error’ to be estimated.
This routine provides builtin 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.
4
References
Conroy H (1967) Molecular Shroedinger equation VIII. A new method for evaluting multidimensional 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: $\mathbf{ndim}$ – IntegerInput

On entry: $n$, the number of dimensions of the integral.
Constraint:
$1\le {\mathbf{ndim}}\le 20$.
 2: $\mathbf{f}$ – real (Kind=nag_wp) Function, supplied by the user.External Procedure

f must return the value of the integrand
$f$ at a given point.
The specification of
f is:
Fortran Interface
Real (Kind=nag_wp)  ::  f  Integer, Intent (In)  ::  ndim  Real (Kind=nag_wp), Intent (In)  ::  x(ndim) 

C Header Interface
#include nagmk26.h
double 
f (const Integer *ndim, const double x[]) 

 1: $\mathbf{ndim}$ – IntegerInput

On entry: $n$, the number of dimensions of the integral.
 2: $\mathbf{x}\left({\mathbf{ndim}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the coordinates of the point at which the integrand $f$ must be evaluated.
f must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
d01gcf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: f should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
d01gcf. If your code inadvertently
does return any NaNs or infinities,
d01gcf is likely to produce unexpected results.
 3: $\mathbf{region}$ – Subroutine, supplied by the user.External Procedure

region must evaluate the limits of integration in any dimension.
The specification of
region is:
Fortran Interface
Integer, Intent (In)  ::  ndim, j  Real (Kind=nag_wp), Intent (In)  ::  x(ndim)  Real (Kind=nag_wp), Intent (Out)  ::  c, d 

C Header Interface
#include nagmk26.h
void 
region (const Integer *ndim, const double x[], const Integer *j, double *c, double *d) 

 1: $\mathbf{ndim}$ – IntegerInput

On entry: $n$, the number of dimensions of the integral.
 2: $\mathbf{x}\left({\mathbf{ndim}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: ${\mathbf{x}}\left(1\right),\dots ,{\mathbf{x}}\left(j1\right)$ contain the current values of the first $\left(j1\right)$ variables, which may be used if necessary in calculating ${c}_{j}$ and ${d}_{j}$.
 3: $\mathbf{j}$ – IntegerInput

On entry: the index $j$ for which the limits of the range of integration are required.
 4: $\mathbf{c}$ – Real (Kind=nag_wp)Output

On exit: the lower limit ${c}_{j}$ of the range of ${x}_{j}$.
 5: $\mathbf{d}$ – Real (Kind=nag_wp)Output

On exit: the upper limit ${d}_{j}$ of the range of ${x}_{j}$.
region must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
d01gcf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: region should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
d01gcf. If your code inadvertently
does return any NaNs or infinities,
d01gcf is likely to produce unexpected results.
 4: $\mathbf{npts}$ – IntegerInput

On entry: the Korobov rule to be used. There are two alternatives depending on the value of
npts.
(i) 
$1\le {\mathbf{npts}}\le 6$.
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$. 
(ii) 
${\mathbf{npts}}>6$.
npts is the number of actual points to be used with corresponding optimal coefficients supplied in the array vk. 
Constraint:
${\mathbf{npts}}\ge 1$.
 5: $\mathbf{vk}\left({\mathbf{ndim}}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: if
${\mathbf{npts}}>6$,
vk must contain the
$n$ optimal coefficients (which may be calculated using
d01gyf or
d01gzf).
If
${\mathbf{npts}}\le 6$,
vk need not be set.
On exit: if
${\mathbf{npts}}>6$,
vk is unchanged.
If
${\mathbf{npts}}\le 6$,
vk contains the
$n$ optimal coefficients used by the preset rule.
 6: $\mathbf{nrand}$ – IntegerInput

On entry: the number of random samples to be generated in the error estimation (generally a small value, say $3$ to $5$, is sufficient). The total number of integrand evaluations will be ${\mathbf{nrand}}\times {\mathbf{npts}}$.
Constraint:
${\mathbf{nrand}}\ge 1$.
 7: $\mathbf{itrans}$ – IntegerInput

On entry: indicates whether the periodising transformation is to be used.
 ${\mathbf{itrans}}=\text{'0'}$
 The transformation is to be used.
 ${\mathbf{itrans}}\ne \text{'0'}$
 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 f).
Suggested value:
${\mathbf{itrans}}=\text{'0'}$.
 8: $\mathbf{res}$ – Real (Kind=nag_wp)Output

On exit: the approximation to the integral $I$.
 9: $\mathbf{err}$ – Real (Kind=nag_wp)Output

On exit: the standard error as computed from
nrand sample values. If
${\mathbf{nrand}}=1$,
err contains zero.
 10: $\mathbf{ifail}$ – IntegerInput/Output

On entry:
ifail must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this argument you should refer to
Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{ or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{ or}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{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:
 ${\mathbf{ifail}}=1$

On entry,  ${\mathbf{ndim}}<1$, 
or  ${\mathbf{ndim}}>20$. 
 ${\mathbf{ifail}}=2$

On entry,  ${\mathbf{npts}}<1$. 
 ${\mathbf{ifail}}=3$

On entry,  ${\mathbf{nrand}}<1$. 
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7
Accuracy
An estimate of the absolute standard error is given by the value, on exit, of
err.
8
Parallelism and Performance
d01gcf 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 implementationspecific information.
The time taken by d01gcf will be approximately proportional to ${\mathbf{nrand}}\times p$, where $p$ is the number of points used.
The exact values of
res and
err on return will depend (within statistical limits) on the sequence of random numbers generated within
d01gcf by calls to
g05saf. Separate runs will produce identical answers.
10
Example
This example calculates the integral
10.1
Program Text
Program Text (d01gcfe.f90)
10.2
Program Data
None.
10.3
Program Results
Program Results (d01gcfe.r)