## 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 language | English |
---|---|

Pages (from-to) | 402-447 |

Number of pages | 46 |

Journal | Journal of Complexity |

Volume | 15 |

Issue number | 3 |

DOIs | |

State | Published - 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
- Mathematics (all)
- Control and Optimization
- Applied Mathematics