首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Average Case Setting
Authors:G W Wasilkowski  H Wo?niakowski
Institution:(1) Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA;(2) Department of Computer Science, Columbia University, New York, NY 10027, USA;(3) Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Abstract:We study multivariate linear problems in the average case setting with respect to a zero-mean Gaussian measure whose covariance kernel has a finite-order weights structure. This means that the measure is concentrated on a Banach space of d-variate functions that are sums of functions of at most q * variables and the influence of each such term depends on a given weight. Here q * is fixed whereas d varies and can be arbitrarily large. For arbitrary finite-order weights, based on Smolyak’s algorithm, we construct polynomial-time algorithms that use standard information. That is, algorithms that solve the d-variate problem to within ε using of order $\varepsilon^{-p}d^{q^{*}}$ function values modulo a power of ln ε −1. Here p is the exponent which measures the difficulty of the univariate (d=1) problem, and the power of ln ε −1 is independent of d. We also present a necessary and sufficient condition on finite-order weights for which we obtain strongly polynomial-time algorithms, i.e., when the number of function values is independent of d and polynomial in ε −1. The exponent of ε −1 may be, however, larger than p. We illustrate the results by two multivariate problems: integration and function approximation. For the univariate case we assume the r-folded Wiener measure. Then p=1/(r+1) for integration and $p=1/(r+\frac{1}{2})$ for approximation.
Keywords:Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000)  65D15  H1A46  H1A63  H1A65
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号