Random Batch Methods for Discretized PDEs on Graphs
Martín Hernández †, Enrique Zuazua * † ‡ · 2025
Read Random Batch Methods for Discretized PDEs on Graphs by Martín Hernández †, Enrique Zuazua * † ‡ (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-11809.txt.
Introduction
Martin Hernandez and Enrique Zuazua study a cost-cutting trick for simulating flow on networks in a 2025 paper. Heat and transport on pipelines, traffic grids, and power nets are modeled with partial differential equations, but full simulation gets pricey as networks grow. The random batch method swaps the full operator for a random part on short time steps.
For the one-dimensional heat equation, the authors prove the shortcut converges to the true answer when step sizes are coupled right. They extend the proof to a control problem and test the scheme on graph domains. Accuracy matched full solvers at lower cost. Readers get a randomized splitting idea that extends to other linear equations.
Catalog record
| CREATOR | Martín Hernández †, Enrique Zuazua * † ‡ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-11809
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Random Batch Methods for Discretized PDEs on Graphs Thanks: † Chair for Dynamics, Control, Machine Learning, and Numerics, Alexander von Humboldt-Professorship, Department of Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany. Thanks: * Departamento de Matemáticas, Universidad Autónoma de Madrid, 28049 Madrid, Spain. Thanks: ‡ Chair of Computational Mathematics, University of Deusto. Av. de las Universidades, 24, 48007 Bilbao, Basque Country, Spain. Martín Hernández †, Enrique Zuazua * † ‡ Abstract . Gas transport and other complex real-world challenges often require solving and controlling partial differential equations (PDEs) defined on graph structures, which typically demand substantial memory and computational resources. The Random Batch Method (RBM) offers significant relief from these demands by enabling the simulation of large-scale systems with reduced computational cost. In this paper, we analyze the application of RBM for solving PDEs on one-dimensional graphs, specifically concentrating on the heat equation. Our approach involves a two-step process: initially discretizing the PDE to transform it into a finite-dimensional problem, followed by the application of the RBM. We refer to this integrated approach as discretize+RBM . We establish the convergence of this method in expectation, under the appropriate selection and simultaneous reduction of the switching parameter in RBM and the discretization parameters. Moreover, we extend these findings to include the optimal control of the heat equation on graphs, enhancing the practical utility of our methodology. The efficacy and computational efficiency of our proposed solution are corroborated through numerical experiments that not only demonstrate convergence but also show significant reductions in computational costs. Our algorithm can be viewed as a randomized variant of domain decomposition, specifically adapted for PDEs defined on graph structures. It is sufficiently versatile to be applied to a wide range of linear PDEs – not just the heat equation – while maintaining comparable analytical guarantees and convergence properties. 2020 Mathematics Subject Classification 65C99, 65M55, 65M75, 35R02 1. Introduction 1.1. Motivation The simulation of complex models such as gas transport in extensive pipeline networks is often computationally demanding and resource-intensive [ 28 , 25 ] . Developing efficient algorithms that can deliver faster solutions while reducing resource consumption is crucial. A notable advancement in this field is the Random Batch Method (RBM), which was originally introduced to efficiently simulate large-scale interacting particle systems [ 14 ] . RBM achieves efficiency by randomly grouping particles into small batches and computing their interactions within brief time subintervals. This method of breaking down complex problems into simpler, manageable subproblems is fundamental to RBM’s success and can be applied across various domains. The Mini-Batch Gradient Descent algorithm in machine learning, which strikes a balance between computational efficiency and model performance, employs a similar approach [ 3 , Section 3] . RBM is also adaptable to high-dimensional linear dynamical systems, where it involves decomposing the governing matrix into smaller sub-matrices. The time interval is partitioned into subintervals, during each of which a randomly selected batch of sub-matrices defines a randomized dynamical system. As shown in [ 31 ] , the solution of this random system converges in expectation to the solution of the original system when the subintervals are sufficiently small. This methodology has been proven effective for optimal-control problems as well [ 31 ] . 1.2. Main Contribution In this paper, we extend the RBM to address partial differential equations (PDEs) and their associated optimal control problems. Our approach, which we term discretize+RBM , begins with the spatial discretization of PDEs, converting them into finite-dimensional dynamical systems, followed by the application of RBM. This method necessitates a careful convergence analysis, which depends on the appropriate selection of discretization and randomization parameters. Control theory cautions that the initial discretization of a system prior to the application of control strategies can lead to the generation of high-frequency spurious solutions [ 9 , 10 , 11 ] . This phenomenon is particularly relevant in hyperbolic wave-like systems, where it can lead to divergence and stability issues. Consequently, in the current framework, both the discretization and RBM methodologies must be meticulously calibrated and coordinated to circumvent such instabilities. This necessitates a thorough analysis to ensure that the discretization does not introduce anomalies that could amplify under the RBM’s stochastic dynamics. Our focus in this article is primarily on the one-dimensional heat equation on a graph. We employ the Finite Element Method (FEM) for spatial discretization, followed by the application of RBM. We establish that a careful selection of both the time subinterval size for RBM and the spatial mesh size for FEM ensures the convergence of the combined FEM+RBM methodology. This convergence is then extended to quadratic optimal control problems. We validate our analytical results through numerical experiments that not only confirm convergence but also demonstrate the computational efficiency of our approach. Our method can be viewed as a randomized version of the classical domain or graph decomposition methods applied to matrix decompositions in discrete dynamics. Additionally, partitioning the problem into small batches not only lowers memory requirements by handling subproblems independently but also leverages the inherent structure of the system for parallelization. This parallel execution further accelerates computations, contributing to a significant reduction in total computational time. Although our primary focus is on the heat equation and the FEM discretization scheme, the principles underlying our discretize+RBM methodology are applicable to other linear PDEs, higher-dimensional settings, and various discretization techniques. This versatility highlights the potential of our approach as a broadly applicable tool for efficiently solving and controlling PDEs in complex domains. 1.3. Related Work The RBM was initially proposed for finite-dimensional interacting particle systems, leading to the development of convergence guarantees [ 15 ] and the management of antisymmetric interactions [ 16 ] . The approach has been expanded to linear dynamical systems integrating it with Model Predictive Control (MPC), providing convergence estimates [ 17 , 30 ] . The stochastic process model introduced by [ 21 ] represents another adaptation of the RBM concept, demonstrating convergence as the step size diminishes. The application of RBM to PDEs includes analyses on particle-interacting systems’ mean-field limits [ 13 ] and on the homogeneous Landau and Fokker-Planck equations [ 4 , 24 ] . These studies employ RBM to approximate PDEs through interacting particle systems. Our approach, however, directly utilizes classical PDE discretization methods such as FEM. Other methodologies that combine discretization with randomization include the work of [ 7 ] on parabolic PDEs and [ 5 ] on gradient flows, both offering insights into convergence behaviors under various conditions. 1.4. Outline The remainder of this article is structured as follows: Section 2 introduces our model and outlines the FEM for the one-dimensional heat equation, along with a detailed description of the RBM, as discussed in [ 31 ] . Section 3 is devoted to presenting our main findings on convergence for PDE optimal control. Section 4 presents numerical simulations to validate our results and illustrate the efficacy of the random graph decomposition approach. 2. Preliminaries Let us first consider L,\,T>0 and the following one-dimensional heat equation: (2.1) \displaystyle\begin{cases}\partial_{t}y-\partial_{xx}y=f,\quad&(x,t)\in(0,L)\times(0,T),\\ y(0,t)=y(L,t)=0,&t\in(0,T),\\ y(x,0)=y^{0}(x),&x\in(0,L).\end{cases} Here, y^{0}\in L^{2}(0,L) is the initial condition, and f\in L^{2}(0,T;H^{-1}(0,L)) is a source term. According to [ 8 , Section 7.1.2] , the existence and uniqueness of the solution y\in C((0,T);L^{2}(0,L))\cap L^{2}(0,T;H_{0}^{1}(0,L)) for ( 2.1 ) are guaranteed.