PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Smolyak Pseudospectral Approximations

Patrick R. Conrad, Youssef M. Marzouk

arXiv:1209.1406v2math.NA

TL;DR

The paper addresses efficient polynomial approximation of computationally intensive black-box models and the aliasing problems of sparse direct quadrature. It develops adaptive Smolyak pseudospectral approximation, establishes its exactness and aliasing properties, and reports improved accuracy and efficiency, including multiple-order-of-magnitude gains on a chemical kinetics problem.

  • Problem

    Sparse quadrature can require unclear truncation choices and incur significant aliasing, motivating a more reliable sparse-grid construction for polynomial approximations.

  • Method

    The paper combines pseudospectral approximation with Smolyak’s algorithm and uses a single tolerance to adaptively refine polynomial spaces and model-evaluation points.

  • Results

    Smolyak pseudospectral approximation avoids internal aliasing, while the adaptive method shows multiple-order-of-magnitude accuracy gains over a non-adaptive approach on a realistic chemical kinetics problem.

  • Takeaways & Limitations

    The approach provides customizable sparse pseudospectral approximations that use function evaluations effectively while controlling truncation and external-aliasing errors.

  • Takeaways & Limitations

    The global error indicator is heuristic and can be poor for some functions, so the authors recommend combining it with wall-clock time and additional error estimates.

Abstract

from arXiv · show

Polynomial approximations of computationally intensive models are central to uncertainty quantification. This paper describes an adaptive method for non-intrusive pseudospectral approximation, based on Smolyak's algorithm with generalized sparse grids. We rigorously analyze and extend the non-adaptive method proposed in [6], and compare it to a common alternative approach for using sparse grids to construct polynomial approximations, direct quadrature. Analysis of direct quadrature shows that O(1) errors are an intrinsic property of some configurations of the method, as a consequence of internal aliasing. We provide precise conditions, based on the chosen polynomial basis and quadrature rules, under which this aliasing error occurs. We then establish theoretical results on the accuracy of Smolyak pseudospectral approximation, and show that the Smolyak approximation avoids internal aliasing and makes far more effective use of sparse function evaluations. These results are applicable to broad choices of quadrature rule and generalized sparse grids. Exploiting this flexibility, we introduce a greedy heuristic for adaptive refinement of the pseudospectral approximation. We numerically demonstrate convergence of the algorithm on the Genz test functions, and illustrate the accuracy and efficiency of the adaptive approach on a realistic chemical kinetics problem.

1. Introduction.

The paper develops adaptive Smolyak pseudospectral approximation for efficient polynomial approximation of computationally intensive black-box models. It analyzes aliasing in sparse-grid approaches and introduces adaptive refinement of both polynomial spaces and model evaluations.

  • Pseudospectral methods construct polynomial approximations from point evaluations, while Smolyak’s algorithm reduces computational effort by weakening coupling between input dimensions.
  • Sparse quadrature approaches can require independently specified truncation and may produce significant aliasing errors unless quadrature order is excessively high.
  • The paper analyzes exactness conditions for tensorized quadrature and pseudospectral operators using polynomial exactness rather than particular interpolation properties.
  • A fully adaptive algorithm uses one tolerance parameter to refine both the polynomial approximation space and its corresponding model-evaluation points.

2. Full tensor approximations.

The full-tensor framework defines exactness for one-dimensional and tensor-product operators, constructs polynomial projections and quadrature rules, and separates truncation from aliasing errors. Suitable one-dimensional operators yield tensor approximations with inherited convergence and zero internal aliasing.

  • Tensor operators are formed by combining convergent one-dimensional approximations whose levels may be selected independently across dimensions.The resulting tensor approximation typically converges as all multi-index components increase.
  • Exact sets contain inputs on which an approximation equals the true operator, while half exact sets connect quadrature exactness to pseudospectral operators.
  • Admissible multi-index sets require every included index to have its backward neighbors included, supporting structured total-order and full-tensor constructions.
  • Quadrature rules approximate integrals through weighted point evaluations and are exact for polynomial spaces whose degree is bounded by the rule’s accuracy.Increasing polynomial accuracy supports convergence for functions in L2.
  • Pseudospectral error separates into truncation and external aliasing, while suitable tensor-product operators inherit zero internal aliasing.Truncation error decreases as the polynomial level increases, and external aliasing vanishes for functions in L2.

3. Smolyak algorithms.

Smolyak algorithms combine lower-order tensor approximations through telescoping sums over admissible multi-index sets. The resulting quadrature and pseudospectral constructions inherit convergence while controlling exactness and avoiding internal aliasing.

  • 3.1. General Smolyak algorithms.: Smolyak algorithms reduce full-tensor cost by blending lower-order tensor approximations through a telescoping sum.For example, separate polynomial terms can require smaller grids than a fully coupled tensor grid.
  • 3.1. General Smolyak algorithms.: Admissible multi-index sets make telescoping valid and allow arbitrary customization beyond the commonly studied total-order set.The weighted-sum form combines tensor operators using coefficients determined by the index-set structure.
  • 3.2. Exactness of Smolyak algorithms.: The exact set of a Smolyak algorithm contains the union of the exact sets of its constituent full-tensor approximations.This theorem applies to arbitrary admissible Smolyak multi-index sets with nested constituent exact sets.
  • 3.3. Smolyak quadrature.: Smolyak quadrature inherits convergence from its one-dimensional operators when the constituent exact sets satisfy the theorem’s conditions.Quadrature rules with polynomial accuracy have nested exact sets.
  • 3.4. Smolyak pseudospectral approximation.: Smolyak pseudospectral approximation has no internal aliasing and limits external aliasing through basis orthogonality.Its selected coefficients can therefore be computed with controlled truncation and external-aliasing errors.

4. Comparing direct quadrature to Smolyak pseudospectral approximation.

Direct quadrature independently selects the polynomial index set and quadrature rule, but this flexibility can produce internal and external aliasing. Smolyak pseudospectral approximation avoids internal aliasing under the stated construction and generally uses sparse evaluations more effectively.

  • Direct quadrature: Independent choices of J and Q(d) make direct quadrature flexible but complicate truncation and can cause aliasing.The polynomial expansion and quadrature grid need not be aligned.
  • Internal aliasing: Direct quadrature has no internal aliasing only when every pair of selected basis terms is mutually non-aliased.A sufficiently powerful quadrature rule can satisfy this condition, but it may be impractical.
  • Internal aliasing: For basis terms (0, 4) and (8, 0), the product term (8, 4) lies outside the sparse rule’s exact set, causing (0, 4) to alias onto (8, 0).The example attributes the error to limited accuracy in mixed dimensions.
  • Internal aliasing: Using the same information and basis, Smolyak pseudospectral approximation has no internal aliasing, whereas direct quadrature corrupts several coefficients.In Example 4.3, direct quadrature aliases onto (8, 0), (10, 0), (12, 0), and (14, 0).
  • External aliasing: Direct quadrature generally has at least as much external aliasing as Smolyak pseudospectral approximation, while Smolyak can eliminate additional external aliases for separable functions.Example 4.4 reports fewer corrupted terms for the Smolyak approach.
  • Overall comparison: Direct quadrature is therefore inefficient for most sparse quadrature rules, while Smolyak pseudospectral approximation is guaranteed to avoid internal aliasing under simple one-dimensional construction guidelines.The paper recommends against using direct quadrature.

5. Adaptive polynomial approximations.

The adaptive Smolyak approach combines local multi-index refinement with a global stopping estimate to improve polynomial approximations. Its indicator choices are useful but heuristic, and work-aware variants introduce tuning challenges and inconclusive benefits.

  • Adaptive strategy: The adaptive strategy separates local improvements to the Smolyak multi-index set from a global stopping criterion.Local refinement adds admissible forward neighbors, while termination uses a global error indicator or threshold.
  • Local refinement: Dimension adaptivity selects a multi-index with a large error indicator and refines its admissible forward neighbors.The indicator is based on the change produced by adding the multi-index and need only be computed once as the set evolves.
  • Error indicators: The L2(X, w) norm is used for the local indicator because it corresponds to pseudospectral convergence, but this choice is heuristic.Aliasing of missing polynomial terms onto included lower-order coefficients can indicate directions for refinement and reduce reliance on smooth coefficient patterns.
  • Work-aware refinement: Work-aware indicators trade error reduction against refinement cost, but selecting their tuning parameter is difficult in practice.The parameterized formulation ranges from prioritizing the standard error indicator to prioritizing cost; ratio-based indicators seek efficient refinements instead.
  • Work-aware refinement: Work-considering refinements showed no significant improvement in the reported experiments, and poor tuning can make the algorithm effectively non-adaptive.The authors describe these results as inconclusive and leave coefficient patterns that may benefit from such approaches as an open problem.
  • Stopping and evaluation: The global error indicator is excellent for most smooth functions but can be poor in other cases, so termination combines it with time and ad hoc sampling.The numerical experiments focus on quadrature rules within Smolyak pseudospectral approximation and on the adaptive strategy, not further direct-quadrature evaluation.

6. Numerical experiments.

The experiments evaluate quadrature choices, non-adaptive and adaptive Smolyak pseudospectral approximations, and a global error indicator on Genz functions and chemical kinetics. Adaptive refinement converges effectively, especially for the 14-dimensional chemical kinetics problem, while the indicator is reliable mainly for smooth functions.

  • Quadrature strategies: The experiments compare linear-growth and exponential-growth Gauss-Legendre, Clenshaw-Curtis, and Gauss-Patterson quadrature strategies for Smolyak pseudospectral approximation.The comparison tracks quadrature points, polynomial exactness, and cumulative cost.
  • Genz functions: All tested non-adaptive methods show fast convergence on smooth Genz functions, indicating that internal aliasing issues are resolved.The authors do not recommend isotropic, function-independent truncation for adaptive use.
  • Genz functions: Adaptive Smolyak approximation converges as expected and performs comparably to or better than non-adaptive approximation on anisotropic Genz functions.The non-adaptive strategy remains suitable when the functions retain substantial coupling, such as the product peak function.
  • Chemical kinetics: More than two orders of magnitude reduction in error is achieved by adaptive Gauss-Patterson versus the non-adaptive method at the same number of model evaluations.Gauss-Patterson is most efficient; exponential-growth Gauss-Legendre and Clenshaw-Curtis are nearly equivalent, while linear-growth Gauss-Legendre performs worse at higher order.
  • Chemical kinetics: Adaptive refinement lowers error by skipping near-zero coefficients and locating higher-order mixed terms that capture variable coupling.The final adaptive Gauss-Patterson expansion has about 32,000 terms versus around 37,000 for the non-adaptive expansion, and includes terms through 30th order.
  • Global error indicator: The global error indicator is largely within an order of magnitude of true L2 error for smooth functions but is less directly related for non-smooth Genz functions.Both the indicator and errors decrease on non-smooth functions, but their relationship is less reliable.

7. Conclusions.

The conclusions emphasize that Smolyak pseudospectral approximation avoids internal aliasing and that adaptive refinement can substantially improve accuracy, while the simple adaptive strategy remains open to extension.

  • Smolyak pseudospectral approximation avoids internal aliasing by assembling tensor-product pseudospectral approximations coherently.
  • Adaptive refinement does not improve approximation performance for every function, although the authors report little evidence that it is harmful.
  • The adaptive strategy is deliberately simple, and possible extensions include computational-cost measures and gradient-based refinement of multi-index directions.
Loading 1209.1406v2…