Source-linked AI summary
A Multilevel Stochastic Collocation Method for Partial Differential Equations with Random Input Data
Aretha L. Teckentrup, Peter Jantsch, Clayton G. Webster, Max Gunzburger
TL;DR
Stochastic collocation for PDEs with random input data can become prohibitively expensive as stochastic dimension increases. The paper proposes MLSC, combining spatial and stochastic approximation hierarchies, and reports reduced costs versus single-level methods and better results than multilevel Monte Carlo on its model problem through 20 dimensions.
Problem
Stochastic collocation for PDEs with random inputs faces increasing computational effort as the stochastic dimension grows.
Source: §1 · p. 2, §7 · p. 23Method
MLSC combines a hierarchy of spatial approximations with a sequence of stochastic approximations of increasing fidelity.
Source: §3.3 · p. 6, §7 · p. 24Results
The numerical results show significant complexity reductions versus single-level methods across the considered problems, and MLSC outperformed multilevel Monte Carlo on the model problem through N = 20 dimensions.
Source: §7 · p. 24Takeaways & Limitations
The authors conclude that multilevel methods improve efficiency over single-level sampling, while multilevel approaches delay the curse of dimensionality for stochastic collocation and improve its effectiveness versus Monte Carlo.
Source: §7 · p. 24
Abstract
from arXiv · showhide
Stochastic collocation methods for approximating the solution of partial differential equations with random input data (e.g., coefficients and forcing terms) suffer from the curse of dimensionality whereby increases in the stochastic dimension cause an explosion of the computational effort. We propose and analyze a multilevel version of the stochastic collocation method that, as is the case for multilevel Monte Carlo (MLMC) methods, uses hierarchies of spatial approximations to reduce the overall computational complexity. In addition, our proposed approach utilizes, for approximation in stochastic space, a sequence of multi-dimensional interpolants of increasing fidelity which can then be used for approximating statistics of the solution as well as for building high-order surrogates featuring faster convergence rates. A rigorous convergence and computational cost analysis of the new multilevel stochastic collocation method is provided, demonstrating its advantages compared to standard single-level stochastic collocation approximations as well as MLMC methods. Numerical results are provided that illustrate the theory and the effectiveness of the new multilevel method.
1. Introduction.
The paper introduces multilevel stochastic collocation (MLSC) to reduce the cost of stochastic collocation for elliptic PDEs with random inputs. It analyzes convergence and computational complexity, including new interpolation error bounds for functionals of the solution.
1. Introduction.
- The study targets elliptic PDEs with random input data, assuming a finite-dimensional random vector and seeking the solution or statistics such as its expected value or variance.The model has random coefficients and forcing on a bounded Lipschitz domain in one to three spatial dimensions.Source: §1 · p. 1, §2 · p. 3
- Monte Carlo sampling has dimension-independent convergence but is generally slow, while stochastic collocation uses deterministic sample points and interpolation and can converge faster for smooth solutions in moderate stochastic dimension.The interpolation may use global Lagrange polynomials or local hierarchical basis functions.Source: §1 · p. 2
- MLSC combines a hierarchy of spatial approximations with stochastic discretizations to reduce standard single-level collocation cost; the analysis also establishes interpolation error bounds for solution functionals.The bounds are needed for the computational-complexity analysis.Source: §1 · p. 2
2. Problem Setting.
The problem setting represents the random inputs using finitely many parameters and studies the resulting parametric elliptic PDE under assumptions ensuring a unique solution. The finite-dimensional representation may require truncation, which introduces additional error.
2. Problem Setting.
- The model is a diffusion-type elliptic PDE with random coefficient and forcing, homogeneous Dirichlet boundary data, and a unique solution in the stated function spaces.The assumptions include finite-dimensional noise and bounded, coercive coefficients.Source: §2 · p. 3
- The random fields are represented by a finite vector of random variables; the setting assumes bounded parameter ranges and a joint density, with independent parameters also allowed.The parameter domain is taken as [−1, 1]^N, and the independent-parameter case uses a product density.Source: §2 · p. 3
- When the random inputs are not finite-dimensional, truncating a spectral expansion such as the Karhunen–Loève expansion can produce inputs satisfying the finite-dimensional assumption, but introduces additional error.The text points to separate analyses of this truncation error.Source: §2 · p. 4
- The stated boundedness and support assumptions can be weakened to allow unbounded random variables, and the method can also accommodate coefficients that are not uniformly coercive, with modifications or cited analyses.The paper also notes applicability to higher-order PDEs and other boundary conditions.Source: §2 · p. 4
3. Hierarchical multilevel stochastic collocation methods.
The method couples spatial and stochastic approximation hierarchies, applying interpolants of different fidelity to finite-element differences across levels. Its cost balance relies on spatial approximation and stochastic interpolation error properties.
3. Hierarchical multilevel stochastic collocation methods.
- The multilevel method combines spatial and parameter-space approximations of different fidelities because accurate single-level approximations may require many expensive PDE solves as stochastic dimension grows.The spatial discretization can use a hierarchy of finite-element spaces; the framework does not depend on that particular discretization.Source: §3 · p. 4, §3.1 · p. 5
3.1. Spatial approximation.
- Nested finite-element spaces approximate the solution by Galerkin projection, with spatial error controlled by a rate that depends on solution regularity and the coefficient, forcing, and domain.The spaces need not be nested if consecutive mesh sizes have bounded ratios.Source: §3.1 · p. 5
3.2. Stochastic interpolation.
- Stochastic interpolation operators approximate parameter dependence, with interpolation error proportional to the size of the interpolated function; generalized sparse-grid Lagrange interpolation is one stated example.The interpolation bounds are used to balance spatial and stochastic discretizations, and the stochastic approximation at a level may remain unchanged as spatial fidelity increases.Source: §3.2 · pp. 5–6
3.3. Formulation of the multilevel method.
- The multilevel construction telescopes spatial approximations into differences and interpolates each difference at a different fidelity, using the most accurate interpolation on the coarsest level and the least accurate on the finest.As levels increase, less accurate interpolation can estimate the differences while maintaining the required accuracy.Source: §3.3 · p. 6
4. Analysis of the multilevel approximation.
The analysis balances spatial and stochastic interpolation errors, then bounds the computational cost of the multilevel approximation and compares it with single-level collocation. It extends the cost analysis to functionals of the solution.
4.1. Convergence analysis.
- Convergence analysis splits total error into spatial and stochastic interpolation contributions, choosing the interpolants so the latter converges at the spatial error rate.The stated aim is for stochastic interpolation error to match spatial discretization error, yielding a total-error convergence result.Source: §4.1 · p. 7
4.2. Cost analysis.
- The ε-cost analysis selects levels and interpolation point counts to bound both error contributions, assuming α ≥ min(β, µγ).It chooses K to bound spatial error and optimizes the point counts subject to a stochastic interpolation-error constraint.Source: §4.2 · p. 8
- When consecutive levels use the same interpolation operator, terms cancel, so their interpolants need not be computed and actual cost can fall below the theorem's estimate.The text notes that sparse-grid methods often reuse an interpolation grid across consecutive levels.Source: §4.2 · p. 10
4.2.1. Comparison to single level collocation methods.
- The multilevel method is shown to be superior to single-level collocation; its savings depend on whether work is concentrated on coarse, balanced, or fine levels.For β>γµ, savings are (h/h0)^γ ≂ ε^γ/α; for β=γµ, they are of order ε^γ/α up to a log factor.Source: §4.2.1 · pp. 10–11
4.3. Multilevel approximation of functionals.
- For functionals ψ(u), an analogous multilevel ε-cost bound holds under assumptions essentially inherited from Theorem 4.2; bounded linear functionals satisfy this inheritance.The paper also mentions nonlinear functionals with this property.Source: §4.3 · p. 11
5. Global sparse grid interpolation.
The section constructs multidimensional sparse-grid interpolants from one-dimensional levels and analyzes their convergence under analytic regularity. It then applies this analysis to multilevel approximations of PDE solutions and solution functionals, with convergence rates that deteriorate as stochastic dimension grows.
5.1. Construction and convergence analysis of multi-dimensional in-
- Sparse-grid construction combines one-dimensional interpolation levels through a multi-index and total level, with growth choices defining the point sets and polynomial spaces.The level index here constructs a sparse-grid interpolant; it is distinct from the spatial and stochastic hierarchy indices used elsewhere.Source: §5.1 · pp. 12–13, §5 · p. 12
- Nested Clenshaw–Curtis abscissas yield nested sparse grids and preserve a Lagrange interpolant, whereas non-nested points do not guarantee interpolation and may introduce additional errors.Anisotropic weights can reflect the relative importance of stochastic dimensions.Source: §5.1 · pp. 13–14
5.1.1. General convergence analysis for multidimensional interpolants.
- For functions analytic in each stochastic direction, the interpolation error is bounded in terms of the number of sparse-grid points, with constants and convergence rate depending on dimension.Anisotropic approximation can account for direction-dependent analyticity; isotropic grids use the worst-case rate across directions.Source: §5.1.1 · p. 14
- Sparse-grid convergence rates generally deteriorate as stochastic dimension grows, and MLSC can improve on MLMC only when standard stochastic collocation outperforms standard Monte Carlo.Sparse-grid SC is of interest where its rate µ is at least 1/2, so its error converges faster than the corresponding Monte Carlo sampling error.Source: §5.1.1 · pp. 14–15
5.2. Multilevel approximation using sparse grids.
- For analytic solution functionals, the sparse-grid analysis satisfies the functional regularity condition and yields optimal convergence rates in spatial mesh size h for stochastic interpolation error.The result applies provided the functional ψ is analytic as a function of the solution u.Source: §5.2 · p. 16
6. Numerical Examples.
Numerical tests in 10- and 20-variable settings confirm convergence assumptions used in the cost analysis and show multilevel collocation outperforming standard stochastic collocation. A practical adaptive implementation meets the required error bound while reducing computational cost.
6. Numerical Examples.
- In the N = 10, two-dimensional test, expected-value finite-element error is consistent with α = 2, while ζ is bounded for ψ(uh) and decays quadratically for ψ(uh) − ψ(u2h).The reported fit for the scaled interpolation errors is C = 0.05 and µ = 1.4.Source: §6 · pp. 18–19, Figure 6.1 · p. 19
- For D = (0, 1)2 and N = 10, MLSC outperforms standard SC in both formula and best settings, and both collocation methods outperform MC and MLMC.Figure 6.2 compares computational cost against relative error.Source: §6 · p. 19, Figure 6.2 · p. 20
- For the alternative quantity ψ(u) = ∥u∥L2(D), all collocation methods outperform Monte Carlo, and MLSC again outperforms standard SC.The interpolation error in ψ(uh) − ψ(u2h) also scales with h2.Source: §6 · p. 20, Figure 6.3 · p. 20
- In the N = 20, one-dimensional test, Figure 6.4 confirms F1, F2, and F3 with α = 2 and β = 2, and reports a best fit C = 0.005 and µ = 0.8.The test uses expected solution values and a reference mesh width h* = 1/1024.Source: §6 · p. 21, Figure 6.4 · p. 21
- For D = (0, 1) and N = 20, MLSC eventually outperforms standard SC, while both collocation methods outperform Monte Carlo; the formula variant scales like ε^-1.25 and the best variant appears slower for small ε.The predicted cost rates are ε^-1.25 for MLSC and ε^-1.75 for standard SC.Source: §6 · pp. 21–22, Figure 6.5 · p. 22
6.3. Practical implementation.
- The practical procedure estimates α, β, µ, and C from coarse meshes and interpolation levels, then increases the finest level until the interpolation and spatial errors are each below ε/2.The implementation estimates α ≈ 2.1, assumes β = α, and estimates C ≈ 0.01 and µ ≈ 0.8.Source: §6.3 · p. 22
- For the N = 20 model, balancing upward and downward sparse-grid rounding meets the required error bound and significantly reduces cost toward the manually found minimum.For large ε, the adaptive procedure overestimated finite-element error and selected a larger K than the manual reference-based choice.Source: §6.3 · p. 23, Table 6.1 · p. 23
7. Concluding remarks.
Multilevel stochastic collocation reduced complexity relative to single-level methods in the problems considered and outperformed multilevel Monte Carlo on the model problem through N = 20 dimensions. The paper also proposes practical measures to reduce inefficiency from growing stochastic grids and to avoid requiring a reference solution.
7. Concluding remarks.
- The method combines hierarchies of spatial and stochastic approximations, with a computational cost analysis and a framework for multilevel methods with decoupled spatial and stochastic degrees of freedom.The analysis reports sufficient cost improvement over single-level methods in all cases.Source: §7 · p. 24
- Numerical results showed reduced complexity versus single-level methods across the problems considered, while multilevel SC outperformed multilevel MC on the model problem through N = 20 dimensions.The table caption identifies a comparison at N = 20 of stochastic interpolation and spatial errors and computational cost, but supplies no cell values.Source: §7 · p. 24, Table 6.2 · p. 24
- Rounding schemes mitigated inefficiency from rapid growth in grid points between levels, and a tested algorithm dispensed with the need for a reference solution to estimate constants.The reference-solution issue arose in most example problems.Source: §7 · p. 24