## Abstract

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q* variables. Here, q* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A_{1,ε} that use O(ε^{-p}) function or linear functional evaluations to achieve an error ε in the worst case setting. Based on these algorithms A_{1,ε}, we provide a construction of polynomial-time algorithms A_{d,ε} for the general d-variate problem with the number of evaluations bounded roughly by ε^{-p}d^{q}* to achieve an error ε in the worst case setting.

Original language | English |
---|---|

Pages (from-to) | 451-494 |

Number of pages | 44 |

Journal | Foundations of Computational Mathematics |

Volume | 5 |

Issue number | 4 |

DOIs | |

State | Published - Nov 2005 |

## Keywords

- 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