Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Implementation and Analysis of an Adaptive Multilevel Monte Carlo Algorithm
KTH, School of Computer Science and Communication (CSC), Numerical Analysis, NA (closed 2012-06-30).
King Abdullah University of Science and Technology.
KTH, School of Computer Science and Communication (CSC), Numerical Analysis, NA (closed 2012-06-30).
King Abdullah University of Science and Technology.
2012 (English)Report (Other academic)
Abstract [en]

This work generalizes a multilevel Monte Carlo (MLMC) method in-troduced in [7] for the approximation of expected values of functions depending on the solution to an Ito stochastic differential equation. The work [7] proposed and analyzed a forward Euler MLMC method based on a hierarchy of uniform time discretizations and control variates to reduce the computational effort required by a standard, single level, forward Euler Monte Carlo method from O( TOL^(−3) ) to O( TOL^(−2) log( TOL^(−1))^2 ) for a meansquare error of size 2 . This work uses instead a hierarchy of adaptivelyrefined, non uniform, time discretizations, generated by an adaptive algo-rithm introduced in [20, 19, 5]. Given a prescribed accuracy TOL in theweak error, this adaptive algorithm generates time discretizations basedon a posteriori expansions of the weak error first developed in [24]. Atheoretical analysis gives results on the stopping, the accuracy, and thecomplexity of the resulting adaptive MLMC algorithm. In particular, it isshown that: the adaptive refinements stop after a finite number of steps;the probability of the error being smaller than TOL is under certain as-sumptions controlled by a given confidence parameter, asymptotically asTOL → 0; the complexity is essentially the expected for MLMC methods,but with better control of the constant factors. We also show that themultilevel estimator is asymptotically normal using the Lindeberg-FellerCentral Limit Theorem. These theoretical results are based on previouslydeveloped single level estimates, and results on Monte Carlo stoppingfrom [3]. Our numerical tests include cases, one with singular drift andone with stopped diffusion, where the complexity of uniform single levelmethod is O TOL−4 . In both these cases the results confirm the theoryby exhibiting savings in the computational cost to achieve an accuracy of O(TOL), from O( TOL^(−3) )for the adaptive single level algorithm toessentially O( TOL^(−2) log(TOL−1)^2 ) for the adaptive MLMC.

Place, publisher, year, edition, pages
2012. , 57 p.
Series
TRITA-NA, ISSN 0348-2952 ; 2012:6
Keyword [en]
computational finance; Monte Carlo; multi-level; adaptivity; weak approximation
National Category
Probability Theory and Statistics Computer Engineering
Identifiers
URN: urn:nbn:se:kth:diva-94108OAI: oai:DiVA.org:kth-94108DiVA: diva2:525328
Note

QC 20120508

Available from: 2012-05-08 Created: 2012-05-07 Last updated: 2016-12-22Bibliographically approved
In thesis
1. Complexity and Error Analysis of Numerical Methods for Wireless Channels, SDE, Random Variables and Quantum Mechanics
Open this publication in new window or tab >>Complexity and Error Analysis of Numerical Methods for Wireless Channels, SDE, Random Variables and Quantum Mechanics
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of the four papers which consider different aspects of stochastic process modeling, error analysis, and minimization of computational cost.

     In Paper I, we construct a Multipath Fading Channel (MFC) model for wireless channels with noise introduced through scatterers flipping on and off. By coarse graining the MFC model a Gaussian process channel model is developed. Complexity and accuracy comparisons of the models are conducted.

     In Paper II, we generalize a multilevel Forward Euler Monte Carlo method introduced by Mike Giles for the approximation of expected values depending on solutions of Ito stochastic differential equations. Giles' work proposed and analyzed a Forward Euler Multilevel Monte Carlo (MLMC) method based on realizations on a hierarchy of uniform time discretizations and a coarse graining based control variates idea to reduce the computational cost required by a standard single level Forward Euler Monte Carlo method. This work is an extension of Giles' MLMC method from uniform to adaptive time grids. It has the same improvement in computational cost and is applicable to a larger set of problems.

     In paper III, we consider the problem to estimate the mean of a random variable by a sequential stopping rule Monte Carlo method. The performance of a typical second moment based sequential stopping rule is shown to be unreliable both by numerical examples and by analytical arguments. Based on analysis and approximation of error bounds we construct a higher moment based stopping rule which performs more reliably.

     In paper IV, Born-Oppenheimer dynamics is shown to provide an accurate approximation of time-independent Schrödinger observables for a molecular system with an electron spectral gap, in the limit of large ratio of nuclei and electron masses, without assuming that the nuclei are localized to vanishing domains. The derivation, based on a Hamiltonian system interpretation of the Schrödinger equation and stability of the corresponding hitting time Hamilton-Jacobi equation for non ergodic dynamics, bypasses the usual separation of nuclei and electron wave functions, includes caustic states and gives a different perspective on the Born-Oppenheimer approximation, Schrödinger Hamiltonian systems and numerical simulation in molecular dynamics modeling at constant energy.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2012. vii, 65 p.
Series
Trita-CSC-A, ISSN 1653-5723 ; 2012:06
Keyword
Wireless Channels; SDE; Monte Carlo Methods, Molecular Dynamics, Quantum Mechanics
National Category
Computational Mathematics Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-94150 (URN)978-91-7501-350-3 (ISBN)
Public defence
2012-05-30, F3, Lindstedtsvägen 26, Kungliga Tekniska högskolan, Stockholm, 10:15 (English)
Opponent
Supervisors
Funder
Swedish e‐Science Research Center
Note

QC 20120508

Available from: 2012-05-08 Created: 2012-05-08 Last updated: 2013-04-09Bibliographically approved

Open Access in DiVA

fulltext(692 kB)260 downloads
File information
File name FULLTEXT01.pdfFile size 692 kBChecksum SHA-512
0fad128c17f5d4dbc161015faab5c24bb40f09fef141fcb69d12b68252e9e3098f2ec797875d55aa78b50d299c8c0833ef7891d70c0b5f08e1a0fb0986f75ba4
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Hoel, HåkonSzepessy, Anders
By organisation
Numerical Analysis, NA (closed 2012-06-30)
Probability Theory and StatisticsComputer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 260 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 93 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf