Explicit cost bounds of algorithms for multivariate tensor product problems

DOI10.1006/jcom.1995.1001zbMath0819.65082OpenAlexW2013576021MaRDI QIDQ1346592

Henryk Woźniakowski, Grzegorz W. Wasilkowski

Publication date: 5 April 1995

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1312f0bd3da4876eafe20d378e07a09e468db2f9

zbMATH Keywords

average caseworst casecomplexity of algorithmscost boundscosts of algorithmsepsilon approximationmultivariate tensor product problems

Mathematics Subject Classification ID

Combinatorics on words (68R15) Complexity and performance of numerical algorithms (65Y20) Multilinear algebra, tensor calculus (15A69)

Related Items

On tractability of path integration ⋮ Liberating the Dimension for Function Approximation and Integration ⋮ Fast Prediction of Deterministic Functions Using Sparse Grid Experimental Designs ⋮ High-dimensional approximation with kernel-based multilevel methods on sparse grids ⋮ Distributed Control of the Stochastic Burgers Equation with Random Input Data ⋮ Uncertainty Quantification of Derivative Instruments ⋮ A new algorithm and worst case complexity for Feynman-Kac path integration. ⋮ Stochastic Collocation Methods for Nonlinear Parabolic Equations with Random Coefficients ⋮ Sparse interpolatory reduced-order models for simulation of light-induced molecular transformations ⋮ Intractability results for integration and discrepancy ⋮ Efficient Implementations of the Multivariate Decomposition Method for Approximating Infinite-Variate Integrals ⋮ On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation ⋮ A Hyperspherical Adaptive Sparse-Grid Method for High-Dimensional Discontinuity Detection ⋮ Calculation of Discrepancy Measures and Applications ⋮ On the influence of robustness measures on shape optimization with stochastic uncertainties ⋮ Applicability of Smolyak's algorithms to certain Banach spaces of multivariate functions. ⋮ Precomputing strategy for Hamiltonian Monte Carlo method based on regularity in parameter space ⋮ A stochastic collocation method based on sparse grids for a stochastic Stokes-Darcy model ⋮ Worst case complexity of multivariate Feynman--Kac path integration ⋮ A sparse grid stochastic collocation upwind finite volume element method for the constrained optimal control problem governed by random convection diffusion equations ⋮ Higher-order wavelet reconstruction/differentiation filters and Gibbs phenomena ⋮ Numerical Integration in Multiple Dimensions with Designed Quadrature ⋮ An adaptive sparse grid method for elliptic PDEs with stochastic coefficients ⋮ Novel results for the anisotropic sparse grid quadrature ⋮ Tractability of multivariate approximation over a weighted unanchored Sobolev space ⋮ Lattice algorithms for multivariate \(L_{\infty}\) approximation in the worst-case setting ⋮ Complexity of weighted approximation over \(\mathbb{R}^d\) ⋮ The exact exponent of sparse grid quadratures in the weighted case ⋮ Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: Application to random elliptic PDEs ⋮ Hyperspherical Sparse Approximation Techniques for High-Dimensional Discontinuity Detection ⋮ Computing expensive multivariate functions of fuzzy numbers using sparse grids ⋮ A Posteriori Error Estimation for the Stochastic Collocation Finite Element Method ⋮ A Sparse Interpolation Algorithm for Dynamical Simulations in Computational Chemistry ⋮ Optimization of black-box problems using Smolyak grids and polynomial approximations ⋮ General algorithm for the numerical integration of functions of several variables ⋮ Tractability of tensor product linear operators ⋮ On ANOVA expansions and strategies for choosing the anchor point ⋮ Contaminant source identification in aquifers: a critical view ⋮ Approximative capabilities of ``Smolyak type computational aggregates with Dirichlet, Fejér and Vallée-Poussin kernels in the scale of Ul'yanov classes ⋮ Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations ⋮ A sharp upper bound for sampling numbers in \(L_2\) ⋮ Some Results on the Complexity of Numerical Integration ⋮ Polynomial Collocation for Handling an Inaccurately Known Measurement Configuration in Electrical Impedance Tomography ⋮ Scenario generation for stochastic optimization problems via the sparse grid method ⋮ On applicability of the sparse grid method in the worst case setting ⋮ An exact order of discrepancy of the Smolyak grid and some general conclusions in the theory of numerical integration ⋮ The exponent of discrepancy is at most 1.4778... ⋮ Applications of Smolyak quadrature formulas to the numerical integration of Fourier coefficients and in function recovery problems ⋮ \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations ⋮ On tractability of linear tensor product problems for \(\infty \)-variate classes of functions ⋮ Sparse finite element approximation of high-dimensional transport-dominated diffusion problems ⋮ Tractability of approximation of \(\infty\)-variate functions with bounded mixed partial derivatives ⋮ Tractability of infinite-dimensional integration in the worst case and randomized settings ⋮ Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials ⋮ Weighted tensor product algorithms for linear multivariate problems ⋮ A survey of average case complexity for linear multivariate problems ⋮ On an interpolatory method for high dimensional integration ⋮ Efficient algorithms for multivariate and \(\infty\)-variate integration with exponential weight ⋮ Generation of nested quadrature rules for generic weight functions via numerical optimization: application to sparse grids ⋮ On weak tractability of the Clenshaw-Curtis Smolyak algorithm ⋮ Spline interpolation on sparse grids ⋮ A Sparse Grid Stochastic Collocation Discontinuous Galerkin Method for Constrained Optimal Control Problem Governed by Random Convection Dominated Diffusion Equations ⋮ Multivariate \(L_{\infty}\) approximation in the worst case setting over reproducing kernel Hilbert spaces ⋮ Widths between the anisotropic spaces and the spaces of functions with mixed smoothness ⋮ A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives ⋮ Complexity of weighted approximation over \(\mathbb{R}\) ⋮ Cubature formulas for function spaces with moderate smoothness ⋮ Dual interval-and-fuzzy analysis method for temperature prediction with hybrid epistemic uncertainties via polynomial chaos expansion ⋮ A note on tools for prediction under uncertainty and identifiability of SIR-like dynamical systems for epidemiology ⋮ Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity ⋮ High dimensional numerical problems ⋮ Non-intrusive uncertainty quantification using reduced cubature rules ⋮ Sparse approximation of multilinear problems with applications to kernel-based methods in UQ ⋮ Robust PID design by chance-constrained optimization ⋮ Sparse finite element methods for operator equations with stochastic data. ⋮ Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain ⋮ Sampling inequalities for sparse grids ⋮ On weak tractability of the Smolyak algorithm for approximation problems ⋮ Numerical comparison of three stochastic methods for nonlinear PN junction problems ⋮ Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces ⋮ Randomly shifted lattice rules on the unit cube for unbounded integrands in high dimensions ⋮ On the complexity of parabolic initial-value problems with variable drift ⋮ Infinite-dimensional integration and the multivariate decomposition method ⋮ Numerical approach for quantification of epistemic uncertainty ⋮ Liberating the dimension for function approximation: standard information ⋮ Dimension-wise integration of high-dimensional functions with applications to finance ⋮ Stochastic finite element methods for partial differential equations with random input data ⋮ SAMBA: sparse approximation of moment-based arbitrary polynomial chaos ⋮ Lower bounds for the error of quadrature formulas for Hilbert spaces ⋮ Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration ⋮ Uncertain eigenvalue analysis by the sparse grid stochastic collocation method ⋮ An Adaptive Sparse Grid Algorithm for Elliptic PDEs with Lognormal Diffusion Coefficient ⋮ Convergence of adaptive stochastic collocation with finite elements ⋮ When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? ⋮ On the power of standard information for multivariate approximation in the worst case setting ⋮ Efficient deterministic numerical simulation of stochastic asset-liability management models in life insurance ⋮ Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences ⋮ Multi-index stochastic collocation for random PDEs ⋮ Uncertainty quantification of geochemical and mechanical compaction in layered sedimentary basins ⋮ Adaptive reduced-basis generation for reduced-order modeling for the solution of stochastic nondestructive evaluation problems ⋮ A sparse-grid isogeometric solver ⋮ Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting ⋮ Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs ⋮ Analysis and implementation issues for the numerical approximation of parabolic equations with random coefficients ⋮ On the order of discrepancy of the Smolyak grid ⋮ A comparative study of numerical approaches to risk assessment of contaminant transport ⋮ Interpolation of functions from Besov-type spaces on Gauß-Chebyshev grids ⋮ Why does information-based complexity use the real number model? ⋮ Quadrature formulas for the Wiener measure ⋮ Hyperbolic cross designs for approximation of random fields ⋮ A weighted POD method for elliptic PDEs with random inputs ⋮ Smolyak's algorithm for weighted \(L_1\)-approximation of multivariate functions with bounded \(r\)th mixed derivatives over \(\mathbb R^d\) ⋮ An optimal Monte Carlo algorithm for multivariate Feynman–Kac path integrals ⋮ Advances and applications of chance-constrained approaches to systems optimisation under uncertainty