Analysis and preconditioning of a probabilistic domain decomposition algorithm for elliptic boundary value problems

2023/12/06 by Bernal, Francisco, Morón-Vidal, Jorge
#65C05 #65D05 #65F08 #65F50 #65N75 #65Y05 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2312.03930

Abstract

PDDSparse is a new hybrid parallelisation scheme for solving large-scale elliptic boundary value problems on supercomputers, which can be described as a Feynman-Kac formula for domain decomposition. At its core lies a stochastic linear, sparse system for the solutions on the interfaces, whose entries are generated via Monte Carlo simulations. Assuming small statistical errors, we show that the random system matrix G(ω) is near a nonsingular M-matrix G, i.e. G(ω)+E=G where ||E||/||G|| is small. Using nonstandard arguments, we bound ||G^-1|| and the condition number of G, showing that both of them grow moderately with the degrees of freedom of the discretisation. Moreover, the truncated Neumann series of G^-1 -- which is straightforward to calculate -- is the basis for an excellent preconditioner for G(ω). These findings are supported by numerical evidence.

Related

• Domain Decomposition of Stochastic PDEs: Development of Probabilistic Wirebasket-based Two-level Preconditioners
• An explicit substructuring method for overlapping domain decomposition based on stochastic calculus
• Hybrid PDE solver for data-driven problems and modern branching
• Combining sparse grids, multilevel MC and QMC for elliptic PDEs with\n random coefficients
• Parallel stochastic methods for PDE based grid generation