Source-linked AI summary
Sparse Pseudospectral Approximation Method
Paul G. Constantine, Michael S. Eldred, Eric T. Phipps
TL;DR
Sparse-grid integration reduces node counts for high-dimensional polynomial approximation, but can produce unacceptable errors in higher-degree Fourier coefficients. The paper develops SPAM by combining tensor-grid expansions with sparse-grid weights, and reports more accurate coefficients and a pointwise-equivalent surrogate.
Problem
Sparse-grid rules offer fewer nodes than tensor products, but directly integrating Fourier coefficients can inaccurately represent higher-degree basis functions, while tensor products scale exponentially with dimension.
Method
SPAM separately computes tensor-product expansion coefficients on each constituent grid and linearly combines them using the sparse-grid rule’s weights.
Results
SPAM coefficients are much more accurate than coefficients obtained by directly applying sparse-grid integration to Fourier coefficients.
Takeaways & Limitations
For function values available at sparse-grid nodes, the paper concludes that SPAM is the proper way to approximate orthogonal-expansion Fourier coefficients, including Smolyak variants.
Takeaways & Limitations
The tensor-product equivalence breaks down when basis-term and quadrature-point counts differ or when a non-Gaussian rule approximates Fourier coefficients.
Abstract
from arXiv · showhide
Multivariate global polynomial approximations - such as polynomial chaos or stochastic collocation methods - are now in widespread use for sensitivity analysis and uncertainty quantification. The pseudospectral variety of these methods uses a numerical integration rule to approximate the Fourier-type coefficients of a truncated expansion in orthogonal polynomials. For problems in more than two or three dimensions, a sparse grid numerical integration rule offers accuracy with a smaller node set compared to tensor product approximation. However, when using a sparse rule to approximately integrate these coefficients, one often finds unacceptable errors in the coefficients associated with higher degree polynomials. By reexamining Smolyak's algorithm and exploiting the connections between interpolation and projection in tensor product spaces, we construct a sparse pseudospectral approximation method that accurately reproduces the coefficients of basis functions that naturally correspond to the sparse grid integration rule. The compelling numerical results show that this is the proper way to use sparse grid integration rules for pseudospectral approximation.
1. Introduction
Multivariate polynomial surrogates reduce the cost of uncertainty and design studies, but tensor-product methods become impractical as dimension grows. This paper introduces SPAM to obtain accurate higher-degree coefficients from sparse-grid rules.
- Motivation: High-fidelity simulations can be too costly for studies requiring many evaluations, motivating cheaper polynomial surrogate models.Surrogates support statistics, sampling, optimization, and uncertainty studies after a relatively small number of expensive runs.
- Motivation: Polynomial approximations efficiently estimate integrated quantities such as simulation-output means and variances.They are also inexpensive to evaluate across input parameters.
- Sparse grids: Sparse grids mitigate dimensionality costs by combining carefully chosen tensor-product grids with far fewer nodes than a full tensor product.Nested univariate point sets can greatly reduce the number of distinct points in the union.
- Pseudospectral approximation: Pseudospectral methods approximate truncated orthogonal-polynomial Fourier coefficients using numerical integration, including polynomial chaos expansions in uncertainty quantification.The expansion is truncated computationally and converges in the mean-squared sense as basis polynomials are added.
- Problem and contribution: The central question is which integration rule can preserve coefficient accuracy without Monte Carlo inaccuracies or tensor-product exponential scaling.Sparse-grid quadrature is promising, but its use for higher-degree coefficients motivates the proposed method.
- Problem and contribution: SPAM combines tensor-grid polynomial-expansion coefficients using the same linear weights that construct the sparse-grid integration rule.The resulting surrogate is pointwise equivalent to one formed by combining tensor-product Lagrange interpolants.
2. Background and Problem Set-up
The paper develops notation linking Gaussian-quadrature interpolation with pseudospectral projection in orthonormal polynomial bases, then extends these constructions to tensor products. Tensor grids become computationally infeasible as dimension grows, motivating sparse-grid methods.
- Assumptions: The analysis assumes square-integrable functions and focuses error-bound discussion on smoother function classes, while using separable normalized weights.The normalized product weight can be interpreted as a probability density function.
- Polynomial and pseudospectral foundations: Pseudospectral approximation truncates an orthonormal-polynomial Fourier series and estimates selected coefficients using numerical quadrature.The remaining coefficient terms are discarded.
- Univariate constructions: For univariate Gaussian quadrature, spectral collocation constructs the unique interpolating polynomial through the quadrature points.The approximation uses Lagrange cardinal functions and interpolates the function at every quadrature point.
- Univariate constructions: Using an n-point Gaussian rule and n orthonormal basis polynomials, the pseudospectral and spectral-collocation approximations are equivalent.The paper states this equivalence through two lemmas relating function evaluations, pseudospectral coefficients, and the resulting approximations.
- Limits of the equivalence: This equivalence breaks down when the number of series terms differs from the number of quadrature points or when the coefficient rule is not Gaussian.The paper identifies these as two important cases where the orthogonal-series representation no longer matches the Lagrange interpolant.
- Multivariate extension and computational challenge: In multiple dimensions, tensor-product Gaussian quadrature and product bases extend the univariate constructions, but an n-point rule in each of d dimensions requires nd function evaluations.Smolyak’s algorithm is introduced as an approach to reduce this dimensionality-driven computational burden while retaining accuracy for certain function classes.
3. Sparse Pseudospectral Approximation Method
SPAM constructs sparse pseudospectral approximations by combining tensor-product pseudospectral expansions according to Smolyak’s sparse-grid weights. It is point-wise equivalent to sparse-grid interpolation, preserves orthonormality for its basis, and yields the sparse-grid quadrature mean.
- Method: SPAM separately computes tensor-product pseudospectral coefficients for each tensor grid and linearly combines coefficients for common basis polynomials.This applies the same linear combination used to construct the sparse-grid quadrature rule.
- Method: The sparse pseudospectral approximation is point-wise equivalent to the sparse-grid interpolation approximation under the theorem’s conditions.This equivalence allows sparse-grid interpolation error analysis to apply directly to SPAM.
- Properties: The mean of SPAM equals the mean obtained by applying the associated sparse-grid quadrature rule directly to f(s).The result follows because the mean is the constant coefficient, and the constant terms combine according to the sparse-grid weights.
- Discrete Orthogonality: Higher-order coefficients are inaccurate under direct sparse-grid integration because higher-order basis functions are not orthonormal under the sparse-grid discrete inner product.SPAM instead produces orthonormal basis polynomials for the relevant set Π.
- Properties: For f(s)=φ(s) with φ(s) in Π, SPAM reproduces the polynomial through its projector property on span(Π).The proof uses exact reproduction on Π and linear independence of its elements.
4. Numerical Experiments
Numerical experiments compare SPAM with direct sparse-grid integration on five bivariate functions and a stochastic diffusion problem. Across these tests, SPAM preserves the expected coefficient behavior, while direct sparse integration becomes inaccurate for higher-order coefficients.
- Experimental setup: The experiments compare SPAM and direct sparse-grid integration using the same basis sets and sparse-grid rules, with tensor-product coefficients treated as truth.The bivariate tests use level 7 sparse grids and tensor-product approximations of order 255 in each variable.
- Five Bivariate functions: Five bivariate test functions include a monomial, an analytic exponential function, a trigonometric function, a rational function, and a nonsmooth absolute-value function.Table 1 defines the test-function set used for the coefficient comparisons.
- Five Bivariate functions: Direct sparse-grid integration produces largely incorrect coefficients for higher-degree polynomials, whereas SPAM more accurately reproduces the expected coefficient structure.For the monomial, direct integration yields nonzero coefficients that orthogonality predicts should vanish; for the analytic function, it produces large high-order coefficients.
- Five Bivariate functions: The coefficient error is attributed to nonorthogonality of the basis under the discrete inner product induced by sparse-grid integration, not to the number of sampled function values.SPAM avoids this issue by separately computing tensor-product coefficients for each tensor grid and combining them through the sparse construction.
- PDE with Random Input Data: In the stochastic diffusion experiment, SPAM coefficients decay with polynomial order as expected, while direct sparse integration begins diverging at higher orders.The difference is less pronounced than in the bivariate tests and is attributed to the alternative growth relationship used for the tensor grids.
5. Conclusions
The sparse pseudospectral approximation combines tensor-product polynomial expansions associated with sparse-grid quadrature rules. Numerical comparisons show that SPAM is more accurate than direct sparse integration, including for higher-degree coefficients and Smolyak variants.
- SPAM linearly combines tensor-product polynomial expansions associated with each tensor-grid quadrature rule.This exploits the equivalence between tensor-product Lagrange interpolation and pseudospectral approximation with an orthogonal polynomial basis.
- Direct sparse integration produces inaccurate higher-degree Fourier coefficients, whereas SPAM coefficients are much more accurate.The comparison concerns approximate Fourier coefficients of a stochastic response for dimension d = 5 and level l = 4.
- The difference between SPAM and direct sparse integration appears in anisotropic and adaptive Smolyak-type approximations as well.The authors report similar studies for these variants, though they are not presented explicitly due to space limitations.