Optimal Multilevel Monte Carlo Algorithms for Parametric Integration and Initial Value Problems

  • We intend to find optimal deterministic and randomized algorithms for three related problems: multivariate integration, parametric multivariate integration, and parametric initial value problems. The main interest is concentrated on the question, in how far randomization affects the precision of an approximation. We want to understand when and to which extent randomized algorithms are superior to deterministic ones. All problems are studied for Banach space valued input functions. The analysis of Banach space valued problems is motivated by the investigation of scalar parametric problems; these can be understood as particular cases of Banach space valued problems. The gain achieved by randomization depends on the underlying Banach space. For each problem, we introduce deterministic and randomized algorithms and provide the corresponding convergence analysis. Moreover, we also provide lower bounds for the general Banach space valued settings, and thus, determine the complexity of the problems. It turns out that the obtained algorithms are order optimal in the deterministic setting. In the randomized setting, they are order optimal for certain classes of Banach spaces, which includes the L_p spaces and any finite dimensional Banach space. For general Banach spaces, they are optimal up to an arbitrarily small gap in the order of convergence.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Thomas Daun
URN:urn:nbn:de:hbz:386-kluedo-40441
Advisor:Stefan Heinrich
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2015/04/01
Year of first Publication:2015
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2014/12/05
Date of the Publication (Server):2015/04/07
Page Number:8, 146
Faculties / Organisational entities:Kaiserslautern - Fachbereich Informatik
CCS-Classification (computer science):F. Theory of Computation
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 13.02.2015