A multigrid-like algorithm for probabilistic domain decomposition

DOI10.1016/J.CAMWA.2016.07.030MaRDI QIDQ521522zbMATH OpenOpenAlexFDO

Authors Francisco Bernal, Juan A. Acebrón

Publication date 11 April 2017

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02818

zbMATH Keywords

variance reductionstabilityalgorithmscalabilityFeynman-Kac formulanumerical exampleparallel computationhigh-performance supercomputingMonte Carlo errorprobabilistic domain decomposition

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Error bounds for boundary value problems involving PDEs (65N15)

Abstract: We present an iterative scheme, reminiscent of the Multigrid method, to solve large boundary value problems with Probabilistic Domain Decomposition (PDD). In it, increasingly accurate approximations to the solution are used as control variates in order to reduce the Monte Carlo error of the following iterates--resulting in an overall acceleration of PDD for a given error tolerance. The key ingredient of the proposed algorithm is the ability to approximately predict the speedup with little computational overhead and in parallel. Besides, the theoretical framework allows to explore other aspects of PDD, such as stability. One numerical example is worked out, yielding an improvement of between one and two orders of magnitude over the previous version of PDD.

Recommendations

• Probabilistically induced domain decomposition methods for elliptic boundary-value problems
• The PDD method for solving linear, nonlinear, and fractional PDEs problems
• Efficient parallel solution of nonlinear parabolic partial differential equations by a probabilistic domain decomposition
• scientific article; zbMATH DE number 4213376
• Domain Decomposition Solution of Elliptic Boundary-Value Problems via Monte Carlo and Quasi-Monte Carlo Methods

Cites work

• scientific article; zbMATH DE number 193842 (Why is no real title available?)
• scientific article; zbMATH DE number 1999206 (Why is no real title available?)
• scientific article; zbMATH DE number 949303 (Why is no real title available?)
• scientific article; zbMATH DE number 3204552 (Why is no real title available?)
• A Monte Carlo method for solving the one-dimensional telegraph equations with boundary conditions
• A comparison of higher-order weak numerical schemes for stopped stochastic differential equations
• A stochastic algorithm based on fast marching for automatic capacitance extraction in non-Manhattan geometries
• An efficient algorithm for accelerating Monte Carlo approximations of the solution to boundary value problems
• Domain Decomposition Solution of Elliptic Boundary-Value Problems via Monte Carlo and Quasi-Monte Carlo Methods
• Domain decomposition solution of nonlinear two-dimensional parabolic problems by random trees
• Evaluation of conditional Wiener integrals by numerical integration of stochastic differential equations
• Functional Integration and Partial Differential Equations. (AM-109)
• Highly efficient numerical algorithm based on random trees for accelerating parallel Vlasov-Poisson simulations
• Meshfree approximation methods with Matlab. With CD-ROM.
• Multilevel estimation of expected exit times and other functionals of stopped diffusions
• Optimization of mesh hierarchies in multilevel Monte Carlo samplers
• Stopped diffusion processes: boundary corrections and overshoot

Cited in

(5)

• A hybrid probabilistic domain decomposition algorithm suited for very large-scale elliptic PDEs
• The PDD method for solving linear, nonlinear, and fractional PDEs problems
• Iterative schemes for probabilistic domain decomposition
• Hybrid PDE solver for data-driven problems and modern branching
• An implementation of Milstein's method for general bounded diffusions

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: A multigrid-like algorithm for probabilistic domain decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521522)