Random Batch Methods for Discretized PDEs on Graphs

Abstract

Diffusion and transport processes on networks arise in applications such as pipeline systems, traffic and information flow, and energy and thermal networks. In these settings the dynamics are often modeled by partial differential equations (PDEs) on graph domains, and their simulation becomes increasingly expensive as the network size grows. The Random Batch Method (RBM) offers a way to reduce this cost, while preserving the large-scale behavior in expectation. In this paper, we study a discretize+RBM strategy for the heat equation. After a finite element discretization in space, we combine it with RBM by decomposing the resulting discrete operator into a finite sum of submatrices and, on short time intervals, replacing the full discrete operator by a randomly chosen partial sum. This defines a computationally cheaper, unbiased RBM approximation of the semi-discrete dynamics. For the one-dimensional heat equation, we prove mean-square convergence of this RBM approximation to the exact PDE solution under a suitable coupling between the short-interval length and the spatial discretization step, and we extend this analysis to a linear-quadratic optimal control problem. The same framework is then applied to the heat equation on metric graphs, and we validate it numerically, showing that the discretize+RBM scheme attains accuracy comparable to a full-graph solver while reducing computational resources. The method can be interpreted as a randomized domain-decomposition strategy on graphs. We emphasize that, beyond the heat equation, the underlying discretize+RBM construction can in principle be applied to a wider class of linear PDEs.