Weighted Smolyak algorithm for solution of stochastic differential equations on non‐uniform probability measures

Nitin Agarwal, N. R. AluruInternational Journal for Numerical Methods in Engineering 2010 · DOI

TL;DR

This paper introduces a "weighted Smolyak algorithm" to more efficiently solve differential equations with random inputs, especially when the probability distributions of these inputs are unevenly spread (non-uniform). By intelligently placing more computational "effort" (support nodes) in regions of higher probability, the method significantly speeds up the calculation of key statistics (moments) of the solution without sacrificing accuracy.

What Problem Does This Paper Address?

Many real-world systems are governed by differential equations, but some parameters within these equations are uncertain. These uncertainties can be modeled as random variables. To understand how these uncertainties affect the system's behavior, we need to solve stochastic differential equations (SDEs). A popular numerical technique for this is stochastic collocation, which approximates the solution by sampling it at specific points (nodes) in the "random domain" defined by the uncertain inputs.

The standard approach uses the Smolyak algorithm to create "sparse grids" of these nodes, which is much more efficient than using a full tensor product grid. However, these standard sparse grids assume the random inputs are uniformly distributed. This is problematic when the probability of certain input values is much higher than others (e.g., a parameter is almost always close to a specific value). In such cases, a uniform grid wastes computational resources by placing many nodes in low-probability regions where the solution's behavior is less critical for calculating overall statistics like the mean or variance. This paper addresses the challenge of efficiently solving SDEs with non-uniform probability measures by developing a method that accounts for these probability distributions when selecting the sampling nodes.

Methods

The core contribution is the weighted Smolyak algorithm. This algorithm builds upon the standard Smolyak sparse grid construction but modifies how the sampling nodes are chosen.

Here's the breakdown:

  • Univariate Node Selection (Algorithm 1): For each individual random variable (dimension), the algorithm uses its marginal probability distribution to determine where to place nodes. Instead of uniform spacing, it strategically places more nodes in regions where the probability density is higher. This is achieved by a recursive partitioning process that considers the "weight" (probability density) of each sub-interval.
  • Weighted Sparse Grid Construction: These weighted univariate node sets are then combined using the standard Smolyak algorithm's framework to create multi-dimensional weighted sparse grids. The key is that these grids are "nested," meaning higher-level grids contain the nodes of lower-level grids, allowing for efficient reuse of computations.
  • Piecewise Linear Basis Functions: The interpolation is based on piecewise linear basis functions, which are known to be applicable to a wider range of problems, including those with less smooth solutions.

The standard Smolyak algorithm uses uniform nodes, while this new approach adapts node placement based on the probability measure.

Datasets

The paper does not introduce new datasets. Instead, it uses established benchmark problems for evaluating numerical methods for SDEs and uncertainty quantification. These include:

  • Genz test functions: A suite of standard functions used to test the accuracy of multi-dimensional integration and approximation algorithms.
  • Kraichnan-Orszag (K-O) problem: A well-known chaotic system used to test the ability of numerical methods to handle non-linear dynamics with random initial conditions.

The paper evaluates the algorithms using various probability distributions, including Uniform, Beta, and Gaussian distributions, and also a custom mixture density to demonstrate robustness.

Key Insights and Ideas

  • Probability Matters for Node Placement: The most significant insight is that ignoring the probability distribution of random inputs when selecting sampling nodes for sparse grids is inefficient, especially for non-uniform distributions.
  • Targeted Computation: By concentrating computational effort (more nodes) in high-probability regions, the weighted Smolyak algorithm can achieve the same accuracy in calculating moments (mean, variance) with significantly fewer function evaluations.
  • Efficiency for Moments: The primary benefit of the weighted approach is its efficiency in computing moments. While the interpolation error itself might not be drastically reduced compared to uniform grids at the same level, the weighted integration for moments benefits immensely.
  • General Applicability: The method is shown to work well for various probability distributions, including non-standard ones, as long as the joint probability distribution can be expressed as a product of marginal distributions (tensor product structure).
  • Nested Grids are Key: The nested nature of the generated sparse grids is crucial for computational efficiency, allowing for adaptive refinement and reuse of previous calculations.

Key Results

The paper demonstrates the effectiveness of the weighted Smolyak algorithm through several numerical examples:

  • Significant Reduction in Functional Evaluations: For computing moments (mean and variance) of test functions, the weighted algorithm consistently required fewer functional evaluations to achieve a target accuracy compared to the uniform Smolyak algorithm. For instance, in one case, achieving ~10⁻⁴ accuracy in variance for the oscillatory function required ~10⁴ evaluations with the uniform method versus ~2×10³ with the weighted method.
  • Improved Accuracy for Moments: In many cases, the weighted algorithm showed a noticeable reduction in the error of computed moments, sometimes by an order of magnitude, especially for highly skewed or localized probability measures.
  • Comparable Interpolation Error: While the primary gain is in moment computation, the interpolation error itself (approximating the solution function) was comparable or only slightly worse than the uniform method at the same grid level. This is because the weighted grids are supersets of uniform grids, meaning they include all the uniform nodes plus additional ones in high-probability areas.
  • Robustness: The algorithm performed well across different test functions, probability distributions (including a mixture density), and dimensions (up to n=6).
  • Kraichnan-Orszag Problem: For this chaotic system, the weighted algorithm showed up to two orders of magnitude improvement in accuracy for moments compared to the uniform algorithm, requiring significantly fewer nodes for a given accuracy level.

Limitations and Future Work

  • Tensor Product Assumption: The method assumes that the joint probability distribution of the random inputs admits a tensor product structure (i.e., can be written as a product of marginal distributions). This is a common assumption in many SDE solution methods but might not hold for all problems.
  • Rosenblatt Transformation Comparison: The paper briefly discusses the Rosenblatt transformation as an alternative for handling non-uniform distributions. While it can map to a uniform domain, the authors argue it doesn't guarantee good performance for arbitrary probability measures, especially for interpolation-based methods, due to potentially highly skewed node distributions. They suggest their weighted approach offers better performance and convergence guarantees.
  • Future Work: The authors hint at the potential for adaptive refinement approaches that incorporate observed output behavior, in addition to a priori knowledge of input probabilities, for even greater efficiency. They also mention that the theoretical convergence rate for their modified node distribution might differ slightly from existing estimates for uniform grids.

Summary updated

Abstract

Abstract This paper deals with numerical solution of differential equations with random inputs, defined on bounded random domain with non‐uniform probability measures. Recently, there has been a growing interest in the stochastic collocation approach, which seeks to approximate the unknown stochastic solution using polynomial interpolation in the multi‐dimensional random domain. Existing approaches employ sparse grid interpolation based on the Smolyak algorithm, which leads to orders of magnitude reduction in the number of support nodes as compared with usual tensor product. However, such sparse grid interpolation approaches based on piecewise linear interpolation employ uniformly sampled nodes from the random domain and do not take into account the probability measures during the construction of the sparse grids. Such a construction based on uniform sparse grids may not be ideal, especially for highly skewed or localized probability measures. To this end, this work proposes a weighted Smolyak algorithm based on piecewise linear basis functions, which incorporates information regarding non‐uniform probability measures, during the construction of sparse grids. The basic idea is to construct piecewise linear univariate interpolation formulas, where the support nodes are specially chosen based on the marginal probability distribution. These weighted univariate interpolation formulas are then used to construct weighted sparse grid interpolants, using the standard Smolyak algorithm. This algorithm results in sparse grids with higher number of support nodes in regions of the random domain with higher probability density. Several numerical examples are presented to demonstrate that the proposed approach results in a more efficient algorithm, for the purpose of computation of moments of the stochastic solution, while maintaining the accuracy of the approximation of the solution. Copyright © 2010 John Wiley & Sons, Ltd.
BibTeX
@article{agarwal2010weighted,
  author = {Nitin Agarwal and N. R. Aluru},
  title = {{Weighted Smolyak algorithm for solution of stochastic differential equations on non‐uniform probability measures}},
  journal = {International Journal for Numerical Methods in Engineering},
  year = {2010},
  doi = {10.1002/nme.3019},
}
Figure