Temporal splitting algorithms for non-stationary multiscale problems

Yalchin Efendiev, Sai-Mang Pun, Petr N. Vabishchevich

TL;DR

This paper introduces a novel temporal splitting algorithm for solving complex non-stationary multiscale problems. By decomposing the solution into components that capture different spatial scales and then applying temporal splitting, the method significantly reduces computational cost while maintaining accuracy, offering a more efficient way to simulate phenomena with vastly different time and space scales.

What Problem Does This Paper Address?

Many real-world phenomena, such as those in porous media, material science, and biology, exhibit multiscale behavior. This means they involve processes happening at vastly different spatial and temporal scales. Simulating these phenomena directly on a fine grid is computationally prohibitive due to the enormous number of degrees of freedom required. Existing multiscale algorithms aim to reduce this computational burden by representing fine-scale details on a coarser grid. However, when these problems are time-dependent (non-stationary), efficiently handling both spatial and temporal scales simultaneously remains a significant challenge. This paper addresses this by developing a temporal splitting algorithm that leverages multiscale spatial decompositions to break down complex time-dependent problems into smaller, more manageable sub-problems.

Methods

The core of the proposed method lies in combining two key ideas: Generalized Multiscale Finite Element Methods (GMsFEM) for spatial decomposition and temporal splitting algorithms.

  1. GMsFEM for Spatial Decomposition: GMsFEM constructs a set of "multiscale basis functions" on a coarse grid. These functions are designed to capture the essential features of the solution at different scales within each coarse grid element. This effectively reduces the spatial dimension of the problem. The paper utilizes a recent theoretical framework for solution decomposition based on these multiscale basis functions.
  2. Temporal Splitting: The paper then applies a temporal splitting scheme to the resulting system of ordinary differential equations (ODEs) obtained from the GMsFEM discretization. The key innovation is to decompose the solution vector itself into components, each associated with a subset of the multiscale basis functions. This decomposition allows for the system matrices (mass and stiffness matrices) to be split into block-diagonal and off-diagonal parts. The temporal splitting algorithm then operates on these blocks, effectively solving smaller, decoupled systems at each time step. The algorithm is presented as a three-level scheme, offering flexibility in how the temporal splitting is performed.

Datasets

Not discussed in the paper. The paper focuses on developing and testing a numerical method for a general class of PDEs, using synthetic examples with defined permeability fields, source terms, and initial conditions.

Key Insights and Ideas

  • Synergy of Spatial and Temporal Decomposition: The paper demonstrates that effectively combining spatial multiscale decomposition (via GMsFEM) with temporal splitting can lead to significant computational savings. The spatial decomposition provides a natural way to partition the problem for temporal splitting.
  • Reduced System Size: By splitting the solution into components corresponding to different sets of multiscale basis functions, the algorithm effectively reduces the size of the linear systems that need to be inverted at each time step. This is a major driver of computational efficiency.
  • Handling of Fast and Slow Dynamics: The proposed splitting approach offers the potential to treat fast and slow temporal dynamics separately, which can be crucial for stiff problems or when explicit-implicit schemes are desired.
  • Unconditional Stability: The paper provides theoretical results showing that the proposed splitting scheme can be unconditionally stable under appropriate conditions on user-defined parameters, which is a desirable property for numerical methods.

Key Results

The paper presents numerical results from three examples with varying degrees of heterogeneity and source function complexity.

  • Example 5.1 (Periodic Permeability): The proposed splitting algorithm achieved errors on the order of $10^{-4}$ in both L2 and energy norms at the terminal time, demonstrating good accuracy.
  • Example 5.2 (High-Contrast Permeability): This more challenging example showed that the splitting algorithm's performance is sensitive to the choice of splitting parameters ($\mu, \sigma$). The 1+9 splitting option was found to be superior, achieving errors in the range of $10^{-3}$ to $10^{-2}$. The paper also noted that the algorithm fails to converge if $\mu < 1.0$ and $\sigma < 1.0$ in this case.
  • Example 5.3 (Time-Dependent Source): For a time-dependent source, the 1+9 splitting again outperformed other options, achieving very low errors (on the order of $10^{-6}$ to $10^{-4}$). The paper also highlighted that using a splitting with $l^{(1)} < l^{(2)}$ (e.g., 1+9) can speed up computation.

In general, the numerical results consistently show that the splitting algorithm achieves high accuracy and, in many cases, outperforms the standard backward Euler scheme in terms of error reduction over time, especially when considering the computational cost.

Limitations and Future Work

  • Parameter Selection: The performance and stability of the splitting algorithm depend on the choice of parameters ($\mu, \sigma$). While theoretical conditions for stability are provided, finding optimal parameters for specific problems might require further investigation.
  • Orthogonalization: The paper mentions that orthogonalizing multiscale basis functions can reduce the effect of off-diagonal matrices and improve stability. This aspect could be further explored.
  • Future Directions: The authors suggest exploring the application of this decomposition method to more complex scenarios, such as unsteady parameter-dependent evolutionary problems. They also plan to investigate adaptive time-marching schemes and adaptive splitting strategies to further enhance efficiency. The potential for parallelization due to the decoupled sub-problems is also a promising avenue.

Summary updated

Abstract

In this paper, we study temporal splitting algorithms for multiscale problems. The exact fine-grid spatial problems typically require some reduction in degrees of freedom. Multiscale algorithms are designed to represent the fine-scale details on a coarse grid and, thus, reduce the problems' size. When solving time-dependent problems, one can take advantage of the multiscale decomposition of the solution and perform temporal splitting by solving smaller-dimensional problems, which is studied in the paper. In the proposed approach, we consider the temporal splitting based on various low dimensional spatial approximations. Because a multiscale spatial splitting gives a "good" decomposition of the solution space, one can achieve an efficient implicit-explicit temporal discretization. We present a recently developed theoretical result in our earlier work and adopt it in this paper for multiscale problems. Numerical results are presented to demonstrate the efficiency of the proposed splitting algorithm.
BibTeX
@article{efendiev2021temporal,
  author = {Yalchin Efendiev and Sai-Mang Pun and Petr N. Vabishchevich},
  title = {{Temporal splitting algorithms for non-stationary multiscale problems}},
  journal = {Journal of Computational Physics},
  year = {2021},
  doi = {10.1016/j.jcp.2021.110375},
}
Figure