A Budgeted Multi-Level Monte Carlo Method for Full Field Estimates of Multi-PDE Problems
Niklas Baumgarten, Robert Kutri, Robert Scheichl · 2025
Read A Budgeted Multi-Level Monte Carlo Method for Full Field Estimates of Multi-PDE Problems by Niklas Baumgarten, Robert Kutri, Robert Scheichl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01644.txt.
Introduction
Niklas Baumgarten, Robert Kutri, and Robert Scheichl present a 2025 method for estimating whole solution fields of random physics problems. Many engineering models pair several partial differential equations with input data that carry random error. Monte Carlo methods handle the randomness by running many samples, but cost explodes when the full field is wanted.
Their budgeted multi-level Monte Carlo method is built to run at top speed within set memory and time caps. It needs no advance knowledge of how smooth the problem is or how much memory the run will take. A sparse multi-index update works on a data structure assembled in parallel as the run proceeds. The authors prove the full field can be had for the same time cost as a single value. Memory stays close to what the plain deterministic problem would need.
Catalog record
| CREATOR | Niklas Baumgarten, Robert Kutri, Robert Scheichl |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Budgeted Multi-Level Monte Carlo Method for Full Field Estimates of Multi-PDE Problems Niklas Baumgarten, Robert Kutri, Robert Scheichl Abstract . We present a high-performance budgeted multi-level Monte Carlo method for estimates on the entire spatial domain of multi-PDE problems with random input data. The method is designed to operate optimally within memory and CPU-time constraints and eliminates the need for a priori knowledge of the problem’s regularity and the algorithm’s potential memory demand. To achieve this, we build on the budgeted multi-level Monte Carlo framework [Baumgarten et al., SIAM/ASA J. Uncertain. , 12 , 2024] and enhance it with a sparse multi-index update algorithm operating on a dynamically assembled parallel data structure to enable estimates of the full field solution. We demonstrate numerically and provide mathematical proof that this update algorithm allows computing the full spatial domain estimates at the same CPU-time cost as a single quantity of interest, and that the maximum memory usage is similar to the memory demands of the deterministic formulation of the problem despite solving the stochastic formulation in parallel. We apply the method to a sequence of interlinked PDE problems, ranging from a stochastic partial differential equation for sampling random fields that serve as the diffusion coefficient in an elliptic subsurface flow problem, to a hyperbolic PDE describing mass transport in the resulting flux field. † † footnotetext: [email protected] 1 Introduction The acquisition and management of comprehensive data is a significant challenge for complex computational systems, often imposed by the limited amount of available memory to hold and the lack of computing power to process this data. Hence, the given computational resources act as a constraint on the computational result. This certainly is the case in Uncertainty Quantification (UQ), particularly when applied to challenging models such as high-dimensional Partial Differential Equations (PDEs) with an uncertain input due to measurement noise or parameter fluctuations. Here, the sheer volume of data already introduces the difficulty. A common approach to UQ for PDEs is to employ model order reduction and surrogate modeling. Additionally, the focus has been on the isolation, prioritization and estimation of quantities of interest (QoIs) associated with the system’s solution, rather than spatially fully resolved estimates. This paper intentionally moves away from model order reduction and from computing QoIs, seeking to demonstrate that, through careful algorithmic design, estimating statistical moments of a random field (RF) solution on the complete spatial domain of the system is no additional burden in terms of memory footprint or computing time. We explain how this is shown mathematically but also introduce the implementation achieving this in practice. While the theory on estimating the solution on the entire spatial domain is known, we have not found a computational method that can reach this goal in a memory-efficient and fully parallelized manner. Our approach uses Multi-Level Monte Carlo (MLMC) methods, introduced in [ 1 , 2 ] and further developed for elliptic [ 3 , 4 , 5 , 6 ] and hyperbolic PDEs [ 7 , 8 ] . We build upon the theoretical work in [ 9 , 10 ] and combine it with the Budgeted Multi-Level Monte Carlo (BMLMC) method [ 11 ] . One notable advantage of the MLMC method lies in its non-intrusive implementation. This means that existing software, e.g. finite element (FE) implementations, can be leveraged without requiring substantial modifications to the code base. In contrast to other works, in particular [ 11 ] , this paper sacrifices the non-intrusive nature inherent in MLMC by combining it with a parallel update protocol. In doing so, we achieve precise control over the algorithm’s memory consumption, and thereby gain the capability to compute estimates of the solution across the entire spatial domain on the fly without postprocessing and without performance degradation. The underpinning methodology, i.e. the BMLMC method, incorporates various concepts from continuation MLMC [ 12 ] and adaptive MLMC [ 13 ] . The central idea is to impose the available computational resources as a budget while minimizing the estimated error. This transforms the search for the optimal sample sequence of the MLMC method into an NP-hard knapsack problem. A similar point of view is also taken in [ 14 ] and the multi-fidelity method [ 15 ] . However, a crucial distinction between the BMLMC method and the multi-fidelity method is that there is no initial cost associated with the construction of the low-fidelity models. Furthermore, the method is designed to use preassigned computational resources on a parallel computing cluster optimally through distributed dynamic programming (DDP) techniques. Importantly, the budget of the BMLMC method, which in [ 11 ] is constrained only by CPU-time \left|\mathcal{P}\right|\cdot{\mathrm{T}}_{\mathrm{B}} with \left|\mathcal{P}\right| being the total number of available CPUs and \mathrm{T}_{\mathrm{B}} the computational time budget, is extended by incorporating an additional memory constraint \mathrm{Mem}_{\mathrm{B}} . As a result, this extension eliminates the need for prior knowledge about the problem and the discretization, ensuring successful execution of the method. The theoretical framework for estimating statistical moments of RF solutions on the entire spatial domain via MLMC is well-established [ 3 , 9 , 10 ] . However, implementation for large-scale applications on distributed memory introduces new challenges. Careless algorithmic design may lead to a dramatic increase in memory consumption, degradation of the computational performance, or require storage of huge amounts of data on a hard-drive. In particular, a novel communication protocol with appropriate distribution rules is necessary to sustain data integrity throughout the simulation. Thus, our novel contributions – significantly extending [ 11 ] – are summarized as follows: Memory Constraint and Sparse Multi-Index Update Algorithm Our work offers a mathematical proof asserting that, through the use of a sparse multi-index update algorithm, the memory usage remains comparable to that of solving the deterministic problem with the same spatial resolution. This justifies imposing a memory constraint on the MLMC method, which is a significant improvement on [ 11 ] in robustness and usability in computationally challenging settings. We achieve this even for full, spatially distributed domain estimates without compromising computing performance due to excessive communication overheads. By extending the techniques to stably update statistical moments, first published in [ 16 , 17 ] and further developed in [ 18 ] , the RF estimates can be computed in a single pass through the samples. To support our claims, we provide empirical evidence in our numerical experiments. A crucial element of the update algorithm is the introduction of a communication split index, denoted by s . When combined with the discretization level, represented by the index \ell , this leads to the method essentially being a variant of a sparse multi-index method. Although our algorithm shares similarities with existing multi-index methods [ 19 , 20 , 21 ] , and sparse grids [ 22 ] , the construction of the multi-index set differs. We build upon the sparsity inherent in the multi-sample parallelization scheme of [ 11 ] . Multi-PDE Problems and Parallel Sampling of RFs The proposed method can be applied to forward UQ problems comprising several intricate PDE models with high-dimensional random input data. The numerical study consists of a series of computations, starting with the generation of Gaussian RFs by solving Stochastic Partial Differential Equations (SPDEs). This is