XML-Space Examples

Hypersphere Volume Integration

This example illustrates how to the calculate the volume of an N-Dimensional Hypersphere using parallel xml-space monte-carlo integration, a technique that we have used extensively.

Computing the volume of a hypersphere provides a relatively straightforward example of the use of this technique, also the results are interesting, and they can be checked by direct analytic calculation.

In practice, the monte-carlo model actually computes the fraction of the bounding hypercube that is occupied by a hypersphere. For example: in 3-dimensional space, this fraction is about one half: a sphere fills about half of the cube that contains it, and which touches its sides.

The hyper-volume of the hypersphere is then obtained, simply by multiplying this computed fraction by the hyper-volume of the containing hypercube.

The monte-carlo integration is implemented using xml-space parallel processing, which enables a large number of calculations to be executed very quickly. A number of computers, that are arranged in a 'compute grid', all work together in collaboration.

The Monte-Carlo Method

The ratio of the hyper-volumes of the hypersphere and the hypercube is estimated by monte-carlo integration: we choose a large number of points at random within the hypercube, and calculate the fraction of these that lie within the hypersphere. Provided that the random points are evenly distributed, this fraction is then a direct estimator of the ratio of these two hyper-volumes.

For a given point, we can determine if it lies inside or outside the hypersphere, simply by calculating its distance from the center of the hypersphere, and comparing this to the hypersphere's radius.

Those not familiar with monte-carlo integration techniques might wonder why we choose 'random' points, rather than doing more orderly 'cube counting' on an even grid, which would be less hap-hazard. It turns out that the use of random points is suprisingly efficient for higher-dimensional integration problems.

This is because, although it can take a large number of calculations for the monte-carlo integration to converge to an accurate answer, in contrast, systematic 'cube counting' methods take far longer for higher dimensional problems; and this difference becomes exponentially greater as the number of dimensions increases.

Implementation Details

We have implemented the above calculation using parallel computing: using a simple 'master-worker' compute-agent processing pattern. A single master-agent issues work tokens, and inserts these into xml-space, from where they are collected and processed by worker-agents.

The worker-agents perform the requested calculations, and return their results to xml-space, from where they are collected and combined by the master-agent. In the present example, the work tokens simply contain the number of random points to be computed, and 'N', the dimension of the hypersphere.

In this example, we have also used the XMLClientObjects utilities library, this enables the xml-space 'command' and 'response' documents to be built and manipulated programmatically, rather than by direct string manipulation and xml parsing.

The source-code for the Master.java and Worker.java classes can be viewed by following these links:

• Hypersphere Master.java
• Hypersphere Worker.java

Parallel Computing

This case provides a relatively simple example of parallel analytic computing: many worker-agents are run simultaneously across a set of machines arranged in a compute-grid, each performing their individual pieces of the calculation in parallel.

This particular situation is an example of a highly decoupled parallel computing pattern: the master-agent doesn't know anything about the worker agents servicing its requests; including, for example, how many workers there are, or their locations. In fact, in this particular implementation, if any of the workers should go off-line during a calculation, the algorithm is essentially unaffected.

Using these techniques, we have run a wide variety of types of monte-carlo simulation, some of which have executed many hundreds of billions of iterations.

Results - Computed Hypersphere Volumes

After some mental gymnastics, it becomes clear that, as the number of dimensions is increased, a hypersphere will progressively fill less and less of its bounding hypercube - essentially because the hypercube has more and more 'corners', which contain an increasingly large fraction of its hyper-volume.

This reasoning is borne out by the results shown in the table below. This compares hyper-volume ratios calculated analytically with values estimated by the parallel monte-carlo integration calculation, using either 1 Million, or 1 Billion randomly chosen points.

Results are given for the 2- and 3-dimensional cases (a circle and a sphere), together with 5-, 10- and 20-dimensional hyperspheres. It can be seen that for higher dimensional cases, the hypersphere only fills a very small amount of its containing hypercube. For example, only a quarter of one percent in the 10-dimensional case.

Note: The values given in the table above represent the hypersphere volumes as a fraction of their containing hypercubes, given in percent.

• The hypersphere image representation used above is the copyright of Helge Preuss, and is reproduced with permission.