NAG CL Interface
g05xec (bb_make_bridge_order)
1
Purpose
g05xec takes a set of input times and permutes them to specify one of several predefined Brownian bridge construction orders. The permuted times can be passed to
g05xac or
g05xcc to initialize the Brownian bridge generators with the chosen bridge construction order.
2
Specification
The function may be called by the names: g05xec or nag_rand_bb_make_bridge_order.
3
Description
The Brownian bridge algorithm (see
Glasserman (2004)) is a popular method for constructing a Wiener process at a set of discrete times,
, for
. To ease notation we assume that
has the index
so that
. Inherent in the algorithm is the notion of a
bridge construction order which specifies the order in which the
points of the Wiener process,
and
, for
, are generated. The value of
is always assumed known, and the first point to be generated is always the final time
. Thereafter, successive points are generated iteratively by an interpolation formula, using points which were computed at previous iterations. In many cases the bridge construction order is not important, since any construction order will yield a correct process. However, in certain cases, for example when using quasi-random variates to construct the sample paths, the bridge construction order can be important.
3.1
Supported Bridge Construction Orders
g05xec accepts as input an array of time points
at which the Wiener process is to be sampled. These time points are then permuted to construct the bridge. In all of the supported construction orders the first construction point is
which has index
. The remaining points are constructed by iteratively bisecting (sub-intervals of) the
time indices interval
, as
Figure 1 illustrates:
The time indices interval is processed in levels
, for
. Each level
contains
points
where
. The number of points at each level depends on the value of
. The points
for
and
are computed as follows: define
and set
By convention the maximum of the empty set is taken to be to be zero.
Figure 1 illustrates the algorithm when
is a power of two. When
is not a power of two, one must decide how to round the divisions by
. For example, if one rounds down to the nearest integer, then one could get the following:
From the series of bisections outlined above, two ways of ordering the time indices
are supported. In both cases, levels are always processed from coarsest to finest (i.e., increasing
). Within a level, the time indices can either be processed left to right (i.e., increasing
) or right to left (i.e., decreasing
). For example, when processing left to right, the sequence of time indices could be generated as:
while when processing right to left, the same sequence would be generated as:
g05xec, therefore, offers four bridge construction methods; processing either left to right or right to left, with rounding either up or down. Which method is used is controlled by the
bgord argument. For example, on the set of times
the Brownian bridge would be constructed in the following orders:
- (processing left to right, rounding down)
- (processing left to right, rounding up)
- (processing right to left, rounding down)
- (processing right to left, rounding up)
The four construction methods described above can be further modified through the use of the input array
move. To see the effect of this argument, suppose that an array
holds the output of
g05xec when
(i.e., the bridge construction order as specified by
bgord only). Let
be the array of all times identified by
move, and let
be the array
with all the elements in
removed, i.e.,
Then the output of
g05xec when
is given by
When the Brownian bridge is used with quasi-random variates, this functionality can be used to allow specific sections of the bridge to be constructed using the lowest dimensions of the quasi-random points.
4
References
Glasserman P (2004) Monte Carlo Methods in Financial Engineering Springer
5
Arguments
-
1:
– Nag_BridgeOrder
Input
-
On entry: the bridge construction order to use.
Constraint:
, , or .
-
2:
– double
Input
-
On entry: , the start value of the time interval on which the Wiener process is to be constructed.
-
3:
– double
Input
-
On entry: , the largest time at which the Wiener process is to be constructed.
-
4:
– Integer
Input
-
On entry: , the number of time points in the Wiener process, excluding and .
Constraint:
.
-
5:
– const double
Input
-
On entry: the time points, , at which the Wiener process is to be constructed. Note that the final time is not included in this array.
Constraints:
- and , for ;
- .
-
6:
– Integer
Input
-
On entry: the number of elements in the array
move.
Constraint:
.
-
7:
– const Integer
Input
-
On entry: the indices of the entries in
intime which should be moved to the front of the
times array, with
setting the
th element of
times to
. Note that
ranges from
to
ntimes. When
,
move is not referenced and may be
NULL.
Constraint:
, for
.
The elements of
move must be unique.
-
8:
– double
Output
-
On exit: the output bridge construction order. This should be passed to
g05xac or
g05xcc.
-
9:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_INT
-
On entry, and .
Constraint: .
On entry, .
Constraint: .
- NE_INT_ARRAY
-
On entry, .
Constraint: for all .
On entry, and .
Constraint: for all .
On entry,
and
both equal
.
Constraint: all elements in
move must be unique.
- 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.
See
Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library CL Interface for further information.
- NE_NOT_STRICTLY_INCREASING
-
On entry,
and
.
Constraint: the elements in
intime must be in increasing order.
- NE_REAL_2
-
On entry, and .
Constraint: .
On entry, , and .
Constraint: .
7
Accuracy
Not applicable.
8
Parallelism and Performance
Background information to multithreading can be found in the
Multithreading documentation.
g05xec 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 function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
None.
10
Example
This example calls
g05xec,
g05xac and
g05xbc to generate two sample paths of a three-dimensional free Wiener process. The array
move is used to ensure that a certain part of the sample path is always constructed using the lowest dimensions of the input quasi-random points. For further details on using quasi-random points with the Brownian bridge algorithm, please see
Section 2.6 in the
G05 Chapter Introduction.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results