Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information
type: Item
instance of: scholarly article
title: Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information
zbMATH Open document ID: 1118.65001
author: Michael Gnewuch
author: H. Woźniakowski
published in: Journal of Complexity
publication date: 2007-06-04T00:00:00Z
review text: The main subject of the present paper is studying generalized tractability for multivariate problems defined as a linear tensor product of problems. The tractability is the study of the difficulty of approximating operators defined on spaces of \(d\)-variate functions with the emphasis on the large dimension \(d.\) Here \(n(\varepsilon, d)\) denotes the minimal number of information evaluations needed to reduce the initial error by a factor of \(\varepsilon \in (0,1].\) The essence of the tractability study is to find necessary and sufficient conditions on spaces of functions and operators for which \(n(\varepsilon, d)\) does not depend exponentially on \(\varepsilon^{-1}\) and on \(d.\) In the introduction a broad survey of papers concerning tractability is given. The notion a tractability function is defined. In section 2 some preliminary notions and statements are given. The concept of the multivariate problem is given. An algorithm \(A_{n,d}\) that uses finitely many information evaluations is proposed. The notion of the worst-case error of the algorithm \(A_{n,d}\) is defined. The notions generalized tractability, \((T, \Omega)\)-tractability, strong \((T, \Omega)\)-tractability and the corresponding parameters exponent \(t^{\text{tra}}\) and \(t^{\text{str}}\) are defined. Different cases of the tractability functions are considered. In section 3 the elements of the multivariate linear tensor product problems are given. The main topic here is the choice of the eigenvalues. Eigenvalues with exponential, polynomial and logarithmic rates of convergence are considered. In section 4 necessary and sufficient conditions for restricted tractability are provided. In Theorem 4.1 where \(d^{*} = 0\) and Theorem 4.2 where \(d^{*} \geq 1,\) necessary and sufficient conditions for multivariate problems \(S\) to be \((T, \Omega^{\text{res}})\)-tractable and strongly \((T, \Omega^{\text{res}})\)-tractable in the class of linear information are presented. The values of the exp…
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 5161134
zbMATH Keywords: Multivariate problem
zbMATH Keywords: Information-based complexity
zbMATH Keywords: Worst-case error
zbMATH Keywords: Eigenvalues
reviewed by: Vassil Grozdanov
MaRDI profile type: Publication
full work available at URL: j.jco.2006.06.006
OpenAlex ID: W1980001337
cites work: Quasi-Monte Carlo methods can be efficient for integration over products of spheres
cites work: Worst case complexity of multivariate Feynman--Kac path integration
cites work: When are integration and discrepancy tractable?
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Q3993279
cites work: Q4226567
cites work: Finite-order weights imply tractability of linear multivariate problems
cites work: Tractability and strong tractability of linear multivariate problems
DOI: 10.1016/J.JCO.2006.06.006
description: scientific article; zbMATH DE number 5161134