M2P 2023

Generating Problem-Adapted Basis Functions Parallel in Time via Random Sampling

  • Schleuß, Julia (University of Münster)
  • Smetana, Kathrin (Stevens Institute of Technology)
  • ter Maat, Lukas (University of Twente)

Please login to view abstract download link

In this talk, we target time-dependent partial differential equations (PDEs) with heterogeneous coefficients in space and time. To tackle these problems, we construct reduced ansatz functions defined in space that can be combined with time stepping schemes, e.g., within model order reduction methods. As a key new contribution, we propose to construct these ansatz functions in an embarrassingly parallel and local manner in time by selecting important points in time and only performing local computations on the corresponding local time intervals. In detail, we perform several simulations of the PDE for few time steps in parallel, starting at different, randomly drawn start points and prescribing random initial conditions. Applying a singular value decomposition to a subset of the so obtained snapshots yields the reduced basis. This facilitates constructing the reduced basis functions in parallel in time. To select start time points for the temporally local PDE simulations, we suggest using a data-dependent probability distribution. To this end, we represent the time-dependent data functions of the PDE as matrices, where each column of a matrix corresponds to one time point in the grid of the time discretization. Subsequently, we employ column subset selection techniques from randomized numerical linear algebra such as leverage score sampling. Each local in time simulation of the PDE with random initial conditions approximates a local approximation space in one time point that is optimal in the sense of Kolmogorov. These optimal local approximation spaces are spanned by the left singular vectors of a compact transfer operator that maps arbitrary initial conditions to the solution of the PDE in a later point of time. By solving the PDE locally in time with random initial conditions, we construct local ansatz spaces in time that converge provably at a quasi-optimal rate and allow for local error control. Numerical experiments demonstrate that the proposed method can outperform existing methods like the proper orthogonal decomposition even in a sequential setting and is well capable of approximating advection-dominated problems.