Industries

Product

Technology

Team

Careers

Press

Sign In

Try Developer Platform

Monte Carlo Integration of Nonlinear Functions Using UxHw

General

General

In the domain of numerical analysis, the integration of functions that are high-dimensional, discontinuous, or which lack closed-form solutions poses a formidable challenge. Traditional deterministic methods, such as Riemann sums or Gaussian quadrature, often struggle with such functions, due to their computational inefficiency and sensitivity to dimensionality [1]. Monte Carlo integration offers one solution to this challenge: Instead of using a structured grid, Monte Carlo integration randomly chooses points at which to evaluate the integrand and it then estimates the integral by averaging the function values at those points. Despite its reliance on random sampling, Monte Carlo integration often outperforms conventional methods in high-dimensional problems [2]. This technology explainer describes how you can design algorithms that run on instances of Signaloid's UxHw technology such as the Signaloid Cloud Compute Engine (SCCE) or the Signaloid hardware modules, achieving all the benefits of Monte Carlo integration, but with faster execution and higher accuracy.

Why It Matters

Monte Carlo integration is a valuable and often-used tool for computing intractable integrals, across quantum chemistry, Bayesian statistics, and finance, among others, outperforming traditional methods which are plagued by the "curse of dimensionality". Unfortunately, however, achieving higher accuracy with Monte Carlo itegration requires expending significant compute resources, as the accuracy only improves as the square root of the factor by which the expended floating point operations are increased. Signaloid's UxHw technology allows numerical analysts to achieve the same kinds of results as Monte Carlo, but at significantly lower computational costs, with accuracy that improves faster as a function of the number of floating-point operations (n) expended (scales as n compared to scaling as the square root of n). This makes it possible to compute integrals of more complex functions, faster and more accurately, in domains ranging from molecular energy estimation in chemistry, to derivatives pricing in finance [3,4,5]. In relevant use cases, solutions running on Signaloid's UxHw platforms are more than 1000-fold faster with 10,000-fold improvements in accuracy.

The Technical Details

Monte Carlo integration estimates an integral by randomly sampling points from the function’s domain. Instead of summing function values at fixed intervals, it selects points at random and averages their contributions. While this method is flexible, it converges more slowly than traditional techniques. The accuracy improves at a rate proportional to the square root of the number of samples (i.e., need a hundred times more samples to reduce the error by a factor of ten [1]). This also means that accuracy improves at a rate proportional to the square root of the aggregate number of floating-point operations expended in evaluating the integrand. To improve efficiency, researchers apply many refinements to this basic procedure. For example, importance sampling selects points where the function has the most influence, reducing unnecessary calculations [6]. Stratified sampling divides the domain into sections and ensures each is well represented, leading to better accuracy [7]. Quasi-Monte Carlo methods replace purely-random points with structured sequences, allowing for faster convergence [1].

Figure 1: A rough sketch of three steps of the Monte Carlo integration procedure. The sketch illustrates how, for three different random samples, Monte Carlo integration evaluates the function value at that sample point and scales it with the width of the domain. By the law of large numbers, the average of these values should converge to the integral of the function as the number of samples tend to infinity.

Signaloid's UxHw technology enables a compelling alternative to Monte Carlo integration: deterministic computation on probability distributions, eliminating the need for repeated sampling while preserving the ability to handle uncertainty.

Instead of drawing billions of random points from a high-dimensional space, an integration algorithm running on top of an implementation of Signaloid's UxHw technology can treat each variable in the integrand expression as a continuous uniform distribution within the defined hypercube. The integrand function can then be evaluated across the entire distributional space, in a single execution, without repeated sampling. The first moment of the resulting distribution, akin to the expected value, provides an immediate estimate of the integral; this can then be scaled by the volume of the hypercube. The result is deterministic: it remains consistent every time the algorithm is rerun, in stark contrast to the fluctuating estimates of traditional Monte Carlo methods.

The need for repeated sampling and function evaluations, as is the case in Monte Carlo integration, goes away, significantly reducing computational costs and removing statistical noise. And, although a single execution using Signaloid's UxHw technology requires more floating-point arithmetic operations than a single iteration of Monte Carlo, as described previously, Signaloid's UxHw technology makes better use of the floating-point arithmetic operations it expends, improving in accuracy with number of floating-point operations (n) expended fast (improving as n) than Monte Carlo (improving as  √n).

At the same time, convergence, a challenge for Monte Carlo methods in high-dimensional settings, is no longer a concern, making Signaloid's UxHw technology not just more efficient but also more reliable than Monte Carlo, making it particularly attractive for applications where stability is paramount, such as financial risk assessment and engineering simulations.

To demonstrate the benefits of using Signaloid's UxHw technology in numerical integration applications where Monte Carlo integration is traditionally employed, the following presents the results of an application which evaluates a multidimensional integral involving a Gaussian-like function. (The integrand in the example is chosen to have a known exact value, to enable error analysis.)

Consider a Monte Carlo integration which samples points from a predefined box spanning -5 to 5 in each dimension, evaluates the function, and scales the mean result by the box volume. We conducted experiments in dimensions 2, 4, 6, 8, and 10, using 1 million and 20 million sample points, respectively, and repeated them 100 times, with extreme values removed using a standard-deviation-based filter.

We measure performance by evaluating accuracy and computation time. To assess accuracy, we compare Monte Carlo estimates to the exact value of the integral (we chose an integrand to enable such an error analysis), while we record execution time to analyze speed. We ran all the Monte Carlo executions on an Intel Xeon platform (AWS r7iz EC2 instance). We then compare these results with timing performance and accuracy (compared to the exact analytic result) for a variant of the numerical integration that takes advantage of Signaloid's UxHw technology and ran on the Signaloid C0Pro-Xs+ core on the Signaloid Cloud Compute Engine, as Figure 2 and Figure 3 show.

When running on top of compute platforms implementing Signaloid's UxHw technology, the integration treats each variable in the integrand's function as a uniform distribution over a hypercube, with extremes of -5 and 5 in each dimension. Instead of relying on random sampling, the integration running on Signaloid's UxHw evaluates the function across the entire distributional space in a single execution pass. The first moment of the resulting output distribution provides the integral estimate.

The results show how, in high dimensions, the errors for Monte Carlo grow and computations become prohibitively expensive. UxHw-based numerical integration offers a promising alternative by improving efficiency and ensuring stability. This example underscores the advantages of deterministic integration for applications requiring high accuracy and repeatability.

Relevant Code Example
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <uxhw.h>

double kLower               = -5;
double kUpper               = 5;
double kNumberOfDimensions  = 10;

/*
 *  The function we are integrating
 */
double function(double *x, int numberOfDimensions) 
{
    double product = 1.0;
    for (int i = 0; i < numberOfDimensions; i++) 
    {
        product *= exp(-x[i] * x[i]);
    }
    return product;
}

/*
 *  The kernel doing the numerical integration
 */
double signaloidIntegrate() 
{
    double width = kUpper - kLower;
    double* x = (double*)malloc(kNumberOfDimensions * sizeof(double));

    for (int j = 0; j < kNumberOfDimensions; j++) 
    {
        x[j] = UxHwDoubleUniformDist(kLower, kUpper);
    }

    double functionEvaluation = function(x, kNumberOfDimensions);
    free(x);
    
    return pow(width, kNumberOfDimensions) * UxHwDoubleNthMoment(functionEvaluation,1);
}

int main() 
{
    double signaloidResult = signaloidIntegrate();
    double analyticResult = pow(M_PI , (kNumberOfDimensions / 2));
    
    printf("Signaloid Integration Result:  %.32lf\n", signaloidResult);
    printf("Analytic Result: %.32lf\n", analyticResult);
    printf("Signaloid error: %.32lf\n", (analyticResult - signaloidResult));
    
    return 0;
}

Figure 2: Accuracy, on a logarithmic scale, of the classic Monte Carlo integration versus the UxHw numerical integration (on the Signaloid C0Pro-Xs+ core) as compared to the analytical solution of the gaussian integral problem. Consistently, for increasing dimensions, UxHw numerical integration is at least 10,000 times more accurate than Monte Carlo with 1,000,000 and 20,000,000 samples respectively.

Figure 3: Timing performance, on a logarithmic scale, of Monte Carlo integration versus the UxHw numerical integration (on the Signaloid C0Pro-Xs+ core) for increasing dimension d of the domain. Consistently, for increasing dimensions, UxHw numerical integration is at least 100-fold and 1000-fold faster than Monte Carlo with 1,000,000 and 20,000,000 samples, respectively.

The Takeaway

While Monte Carlo integration remains a practical tool for high-dimensional problems, its accuracy and efficiency degrade as dimensions increase. The integration methods that take advantage of Signaloid's UxHw technology provide a deterministic alternative, by computing integrals directly over probability distributions, eliminating variance and ensuring consistent results. The UxHw-enhanced numerical integration achieves similar or better accuracy than Monte Carlo while improving computational efficiency. For applications where reliability and stability are critical, this presents a compelling option, reducing computational costs and mitigating the challenges associated with high-dimensional numerical integration, with speedups for the example evaluated of greater than 1000-fold, and with 10,000-fold better accuracy.

References

  1. Caflisch, R. E. (1998). "Monte Carlo and quasi-Monte Carlo methods." Acta Numerica, 7, 1-49.

  2. Metropolis, N., & Ulam, S. (1949). "The Monte Carlo Method." Journal of the American Statistical Association, 44(247), 335-341.

  3. Ceperley, D. M., & Alder, B. J. (1980). "Ground State of the Electron Gas by a Stochastic Method." Physical Review Letters, 45(7), 566.

  4. Neal, R. M. (1993). "Probabilistic Inference Using Markov Chain Monte Carlo Methods." Technical Report CRG-TR-93-1, University of Toronto.

  5. Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering. Springer.

  6. Owen, A. B. (1997). "Monte Carlo variance of scrambled net quadrature." SIAM Journal on Numerical Analysis, 34(5), 1884-1910.

  7. Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods. Springer.

Schedule a Demo Call

Schedule a Call

Request Whitepaper
Schedule a Demo Call

Schedule a Call

Request Whitepaper
Schedule a Demo Call

Schedule a Call

Request Whitepaper