LEADER 03457nam 22004455a 450 001 9910151934203321 005 20091109150325.0 010 $a3-03719-526-6 024 70$a10.4171/026 035 $a(CKB)3710000000953833 035 $a(CH-001817-3)85-091109 035 $a(PPN)178155497 035 $a(EXLCZ)993710000000953833 100 $a20091109j20080902 fy 0 101 0 $aeng 135 $aurnn|mmmmamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aTractability of Multivariate Problems$b[electronic resource] $eVolume I: Linear Information /$fErich Novak, Henryk Woz?niakowski 210 3 $aZuerich, Switzerland $cEuropean Mathematical Society Publishing House$d2008 215 $a1 online resource (395 pages) 225 0 $aEMS Tracts in Mathematics (ETM)$v6 330 $aMultivariate 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 ?, i.e., the cost increases polynomially in ??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 ??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 ??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... 606 $aNumerical analysis$2bicssc 606 $aMathematical theory of computation$2bicssc 606 $aNumerical analysis$2msc 606 $aComputer science$2msc 615 07$aNumerical analysis 615 07$aMathematical theory of computation 615 07$aNumerical analysis 615 07$aComputer science 686 $a65-xx$a68-xx$2msc 700 $aNovak$b Erich$056070 702 $aWoz?niakowski$b Henryk 801 0$bch0018173 906 $aBOOK 912 $a9910151934203321 996 $aTractability of Multivariate Problems$92565018 997 $aUNINA