Back to Search
Start Over
Coin Tossing Algorithms for Integral Equations and Tractability.
- Source :
- Monte Carlo Methods & Applications; 2004, Vol. 10 Issue 3/4, p491-498, 8p
- Publication Year :
- 2004
-
Abstract
- Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d. This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error e that uses roughly ε<superscript>-2</superscript> function values and only d log² ε random bits. The number of arithmetic operations is of the order ε<superscript>-2</superscript> + d log² ε. Hence, the cost of our algorithm increases only mildly with the dimension d, we obtain the upper bound C ⋅ (ε<superscript>-2</superscript> + d log² ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09299629
- Volume :
- 10
- Issue :
- 3/4
- Database :
- Complementary Index
- Journal :
- Monte Carlo Methods & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 18604839
- Full Text :
- https://doi.org/10.1515/mcma.2004.10.3-4.491