What Monte Carlo models can do and cannot do efficiently?

被引:24
作者
Atanassov, Emanouil [2 ]
Dimov, Ivan T. [1 ]
机构
[1] Univ Reading, ACET, Reading RG6 6AH, Berks, England
[2] Bulgarian Acad Sci, Dept Parallel Algorithms, Inst Parallel Proc, BU-1113 Sofia, Bulgaria
关键词
Monte Carlo algorithms; deterministic algorithms; multidimensional integration; integral equations; unimprovable rate of convergence;
D O I
10.1016/j.apm.2007.04.010
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
The question "what Monte Carlo models can do and cannot do efficiently" is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Holder type conditions, as well as Korobov-like spaces. Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms - deterministic and randomized for both problems - numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码:1477 / 1500
页数:24
相关论文
共 75 条
[1]  
[Anonymous], J COMPUTATIONAL APPL
[2]  
[Anonymous], 1979, Monte Carlo Methods, DOI DOI 10.1007/978-94-009-5819-7
[3]  
[Anonymous], 1991, COMPUTATIONAL COMPLE
[4]  
ATANASSOV EI, 1999, MONTE CARLO METH, V5, P149
[5]  
Bakhvalov N. S., 1987, Numerical Methods
[6]  
BAKHVALOV NS, 1961, USSR COMP MATH MATH, V1, P64
[7]  
BAKHVALOV NS, 1964, NUMERICAL METHODS SO
[8]  
BAKHVALOV NS, 1959, VESTNIK MOSK MMAFH, V4
[9]  
BECKERS M, 1992, NATO ADV SCI I C-MAT, V357, P329
[10]   RANDOMIZATION OF NUMBER THEORETIC METHODS FOR MULTIPLE INTEGRATION [J].
CRANLEY, R ;
PATTERSON, TNL .
SIAM JOURNAL ON NUMERICAL ANALYSIS, 1976, 13 (06) :904-914