Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting

G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We study multivariate linear problems in the average case setting with respect to a zero-mean Gaussian measure whose covariance kernel has a finite-order weights structure. This means that the measure is concentrated on a Banach space of d-variate functions that are sums of functions of at most q * variables and the influence of each such term depends on a given weight. Here q * is fixed whereas d varies and can be arbitrarily large. For arbitrary finite-order weights, based on Smolyak's algorithm, we construct polynomial-time algorithms that use standard information. That is, algorithms that solve the d-variate problem to within ε using of order -pd q function values modulo a power of ln∈ε -1. Here p is the exponent which measures the difficulty of the univariate (d=1) problem, and the power of ln∈ε -1 is independent of d. We also present a necessary and sufficient condition on finite-order weights for which we obtain strongly polynomial-time algorithms, i.e., when the number of function values is independent of d and polynomial in ε -1. The exponent of ε -1 may be, however, larger than p. We illustrate the results by two multivariate problems: integration and function approximation. For the univariate case we assume the r-folded Wiener measure. Then p=1/(r+1) for integration and p=1/(r+ 1 2) for approximation.

Original languageEnglish
Pages (from-to)105-132
Number of pages28
JournalFoundations of Computational Mathematics
Issue number1
StatePublished - Feb 2009


  • Average case setting
  • Finite-order weights
  • Multivariate linear problems
  • Polynomial-time algorithms
  • Small effective dimension
  • Tractability

ASJC Scopus subject areas

  • Analysis
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting'. Together they form a unique fingerprint.

Cite this