Weighted tensor product algorithms for linear multivariate problems

G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

71 Scopus citations

Abstract

We study the ε-approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces of functions f of d variables. A class of weighted tensor product (WTP) algorithms is defined which depends on a number of parameters. Two classes of permissible information are studied. Λall consists of all linear functionals while Λstd consists of evaluations of f or its derivatives. We show that these multivariate problems are sometimes tractable even with a worst-case assurance. We study problem tractability by investigating when a WTP algorithm is a polynomial-time algorithm, that is, when the minimal number of information evaluations is a polynomial in 1/ε and d. For Λall we construct an optimal WTP algorithm and provide a necessary and sufficient condition for tractability in terms of the sequence of weights and the sequence of singular values for d=1. ForΛstd we obtain a weaker result by constructing a WTP algorithm which is optimal only for some weight sequences.

Original languageEnglish
Pages (from-to)402-447
Number of pages46
JournalJournal of Complexity
Volume15
Issue number3
DOIs
StatePublished - Sep 1999

Bibliographical note

Funding Information:
We study the =-approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces of functions f of d variables. A class of weighted tensor product (WTP) algorithms is defined which depends on a number of parameters. Two classes of permissible information are studied. 4all consists of all linear functionals while 4std consists of evaluations of f or its derivatives. We show that these multivariate problems are sometimes tractable even with a worst-case assurance. We study problem tractability by investigating when a WTP algorithm is a polynomial-time algorithm, that is, when the minimal number of information evaluations is a polynomial in 1 = and d. For 4all we construct an optimal WTP algorithm and provide a necessary and sufficient condition for tractability in terms of the sequence of weights and the sequence of singular values for d=1. For 4std we obtain a weaker result by constructing a WTP algorithm which is optimal only for some weight sequences. ν 1999 Academic Press 1The authors were partially supported by the National Science Foundation under Grants CCR-9729971 and CCR-9731858, respectively.

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 'Weighted tensor product algorithms for linear multivariate problems'. Together they form a unique fingerprint.

Cite this