Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems

Grzegor Z.W. Wasilkowski, Henryk Wozniakowski

Research output: Contribution to journalArticlepeer-review

266 Scopus citations

Abstract

We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β12 + β3(ln 1/ϵ)/(d - 1))β4(d - 1)(1/ϵ)β5. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and βi′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) − 7.26ϵ-2.454, ∀d, ϵ ≤ 1.

Original languageEnglish
Pages (from-to)1-56
Number of pages56
JournalJournal of Complexity
Volume11
Issue number1
DOIs
StatePublished - Mar 1995

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems'. Together they form a unique fingerprint.

Cite this