Tractability Of Multivariate Problems Linear Information
Download Tractability Of Multivariate Problems Linear Information PDF/ePub or read online books in Mobi eBooks. Click Download or Read Online button to get Tractability Of Multivariate Problems Linear Information book now. This website allows unlimited access to, at the time of writing, more than 1.5 million titles, including hundreds of thousands of titles in various foreign languages.
Tractability of Multivariate Problems: Linear information
Author: Erich Novak
language: en
Publisher: European Mathematical Society
Release Date: 2008
Multivariate problems occur in many applications. These problems are defined on spaces of $d$-variate functions and $d$ can be huge--in the hundreds or even in the thousands. Some high-dimensional problems can be solved efficiently to within $\varepsilon$, i.e., the cost increases polynomially in $\varepsilon^{-1}$ and $d$. However, there are many multivariate problems for which even the minimal cost increases exponentially in $d$. This exponential dependence on $d$ is called intractability or the curse of dimensionality. This is the first volume of a three-volume set comprising a comprehensive study of the tractability of multivariate problems. It is devoted to tractability in the case of algorithms using linear information and develops the theory for multivariate problems in various settings: worst case, average case, randomized and probabilistic. A problem is tractable if its minimal cost is not exponential in $\varepsilon^{-1}$ and $d$. There are various notions of tractability, depending on how we measure the lack of exponential dependence. For example, a problem is polynomially tractable if its minimal cost is polynomial in $\varepsilon^{-1}$ and $d$. The study of tractability was initiated about 15 years ago. This is the first and only research monograph on this subject. Many multivariate problems suffer from the curse of dimensionality when they are defined over classical (unweighted) spaces. In this case, all variables and groups of variables play the same role, which causes the minimal cost to be exponential in $d$. But many practically important problems are solved today for huge $d$ in a reasonable time. One of the most intriguing challenges of the theory is to understand why this is possible. Multivariate problems may become weakly tractable, polynomially tractable or even strongly polynomially tractable if they are defined over weighted spaces with properly decaying weights. One of the main purposes of this book is to study weighted spaces and obtain necessary and sufficient conditions on weights for various notions of tractability. The book is of interest for researchers working in computational mathematics, especially in approximation of high-dimensional problems. It may be also suitable for graduate courses and seminars. The text concludes with a list of thirty open problems that can be good candidates for future tractability research.
Tractability of Multivariate Problems
Multivariate problems occur in many applications. These problems are defined on spaces of d-variate functions and d can be huge - in the hundreds or even in the thousands. Some high-dimensional problems can be solved efficiently to within [epsilon], i.e., the cost increases polynomially in [epsilon]-1 and d. However, there are many multivariate problems for which even the minimal cost increases exponentially in d. This exponential dependence on d is called intractability or the curse of dimensionality. This is the first of a three-volume set comprising a comprehensive study of the tractability of multivariate problems. It is devoted to algorithms using linear information consisting of arbitrary linear functionals. The theory for multivariate problems is developed in various settings: worst case, average case, randomized and probabilistic. A problem is tractable if its minimal cost is not exponential in [epsilon]-1 and d. There are various notions of tractability, depending on how we measure the lack of exponential dependence. For example, a problem is polynomially tractable if its minimal cost is polynomial in [epsilon]-1 and d. The study of tractability was initiated about 15 years ago. This is the first research monograph on this subject. Many multivariate problems suffer from the curse of dimensionality when they are defined over classical (unweighted) spaces. But many practically important problems are solved today for huge d in a reasonable time. One of the most intriguing challenges of theory is to understand why this is possible. Multivariate problems may become tractable if they are defined over weighted spaces with properly decaying weights. In this case, all variables and groups of variables are moderated by weights. The main purpose of this book is to study weighted spaces and to obtain conditions on the weights that are necessary and sufficient to achieve various notions of tractability. The book is of interes...
Tractability of Multivariate Problems: Standard information for functionals
Author: Erich Novak
language: en
Publisher: European Mathematical Society
Release Date: 2008
This is the second volume of a three-volume set comprising a comprehensive study of the tractability of multivariate problems. The second volume deals with algorithms using standard information consisting of function values for the approximation of linear and selected nonlinear functionals. An important example is numerical multivariate integration. The proof techniques used in volumes I and II are quite different. It is especially hard to establish meaningful lower error bounds for the approximation of functionals by using finitely many function values. Here, the concept of decomposable reproducing kernels is helpful, allowing it to find matching lower and upper error bounds for some linear functionals. It is then possible to conclude tractability results from such error bounds. Tractability results, even for linear functionals, are very rich in variety. There are infinite-dimensional Hilbert spaces for which the approximation with an arbitrarily small error of all linear functionals requires only one function value. There are Hilbert spaces for which all nontrivial linear functionals suffer from the curse of dimensionality. This holds for unweighted spaces, where the role of all variables and groups of variables is the same. For weighted spaces one can monitor the role of all variables and groups of variables. Necessary and sufficient conditions on the decay of the weights are given to obtain various notions of tractability. The text contains extensive chapters on discrepancy and integration, decomposable kernels and lower bounds, the Smolyak/sparse grid algorithms, lattice rules and the CBC (component-by-component) algorithms. This is done in various settings. Path integration and quantum computation are also discussed. This volume is of interest to researchers working in computational mathematics, especially in approximation of high-dimensional problems. It is also well suited for graduate courses and seminars. There are 61 open problems listed to stimulate future research in tractability.