Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients

Eric T. Chung, Yalchin Efendiev, Wing Tat Leung, Zhiwen Zhang

TL;DR

This paper introduces a novel "Cluster-based Generalized Multiscale Finite Element Method" (GMsFEM) to efficiently solve complex partial differential equations (PDEs) with random coefficients. By intelligently grouping similar random scenarios (clustering) and then building specialized basis functions, their method significantly reduces computational cost while maintaining accuracy, particularly for problems without clear scale separation.

What Problem Does This Paper Address?

Many real-world physical systems, like those in porous media, are governed by PDEs where material properties (like permeability) are not precisely known and vary randomly. This uncertainty is often described by a large number of possible "realizations" of these properties. Simulating these systems requires solving the PDE for many such realizations, which becomes computationally prohibitive, especially when the underlying physics also involves multiple spatial scales that are tightly coupled with the uncertainties. Existing methods often struggle to efficiently handle this combination of spatial and uncertainty-driven complexity, particularly when there's no clear separation between the scales involved. This paper aims to bridge this gap by developing a method that simultaneously coarsens both the spatial domain and the space of random realizations.

Methods

The core of the proposed method lies in a two-stage approach:

  • Offline Stage: This is where the heavy lifting of pre-computation happens.
  • Spatial Coarsening: They employ the Generalized Multiscale Finite Element Method (GMsFEM) framework. This involves constructing a small set of "multiscale basis functions" within each coarse spatial grid block. These functions are designed to capture the essential behavior of the solution within that block, effectively reducing the dimensionality of the spatial problem.
  • Uncertainty Coarsening (Clustering): This is the novel contribution. Instead of treating each random realization independently, they group similar realizations together using a clustering algorithm. To define "similarity," they introduce a distance metric based on the solutions of local problems with randomized boundary conditions. This allows them to identify groups of realizations that behave similarly. They then use Karhunen-Loève (KL) expansion to capture the dominant modes of variation within these clusters.
  • Basis Function Construction: For each cluster and coarse spatial block, they construct a set of "snapshot functions" by solving local problems with specific boundary conditions. These snapshots are then used to build the reduced basis functions for the offline space.
  • Online Stage: Once the offline computations are done, solving for new random realizations becomes much faster.
  • Efficient Solution: The pre-computed multiscale basis functions are used to approximate the solution on the coarse grid.
  • Adaptive Refinement (Online Basis Functions): For improved accuracy, they introduce an online stage where additional basis functions can be adaptively constructed based on the residual of the current solution. This allows for targeted refinement where needed, further accelerating convergence.

Datasets

Not discussed in the paper. The paper focuses on a general methodology and demonstrates its performance on synthetic examples designed to mimic challenging multiscale and stochastic scenarios.

Key Insights and Ideas

  • Joint Coarsening is Key: The most significant insight is the effectiveness of simultaneously coarsening both the spatial domain and the uncertainty space. This "joint coarsening" is crucial for problems where spatial scales and uncertainties are tightly coupled.
  • Clustering as a Dimensionality Reduction Tool for Uncertainty: Using clustering to group similar random realizations is a powerful way to reduce the dimensionality of the uncertainty space, making computations tractable.
  • Randomized Boundary Conditions for Local Problems: Employing randomized boundary conditions to generate local solutions for distance computation is an efficient way to capture the essential modes of local behavior without solving full problems for all realizations.
  • Adaptive Online Basis Functions for Faster Convergence: The online stage, which adaptively adds basis functions based on the residual, provides a mechanism to achieve high accuracy with fewer degrees of freedom, significantly accelerating convergence.
  • Exploiting Heterogeneities: The cluster-based approach naturally helps in exploring the heterogeneities of the solution space, even for problems without scale separation.

Key Results

The paper demonstrates significant computational savings and good accuracy through numerical experiments.

  • Error Reduction: They show substantial error reduction by increasing the number of basis functions per cluster and by increasing the number of clusters. For instance, in Case 1, using 5 basis functions and 5 clusters reduced errors to around 8.35% for the L² norm over realizations.
  • Efficiency: The method offers considerable savings compared to traditional stochastic methods. The online stage further accelerates convergence, with errors dropping significantly after just a few online iterations. For example, in Table 4, errors dropped from over 11% to under 1.4% with just 3 online iterations.
  • Handling Non-Affinity: The method is shown to be effective even for problems with highly nonlinear parameter dependence (non-affine), which are particularly challenging for many existing methods.

Limitations and Future Work

  • Accuracy Analysis: The paper acknowledges that a rigorous mathematical analysis of the accuracy is not provided. The accuracy is expected to depend on the realization-based multiscale approximations and the cluster sizes.
  • Clustering Adaptivity: While adaptivity in spatial space and uncertainty space is a strength, adaptivity for clustering itself (changing cluster sizes and elements) can be computationally expensive and is a direction for future work.
  • General Clustering Algorithms: The paper uses k-means clustering and suggests that other clustering algorithms and more accurate distance approximations could be explored for improved convergence.
  • Online Stage Cost: While the online stage accelerates convergence, it involves reformulating the coarse-grid problem, which can still be computationally intensive. The accuracy of the online method is noted to depend on the quality of the offline spaces.

Summary updated

Abstract

We propose a generalized multiscale finite element method (GMsFEM) based on clustering algorithm to study the elliptic PDEs with random coefficients in the multi-query setting. Our method consists of offline and online stages. In the offline stage, we construct a small number of reduced basis functions within each coarse grid block, which can then be used to approximate the multiscale finite element basis functions. In addition, we coarsen the corresponding random space through a clustering algorithm. In the online stage, we can obtain the multiscale finite element basis very efficiently on a coarse grid by using the pre-computed multiscale basis. The new GMsFEM can be applied to multiscale SPDE starting with a relatively coarse grid, without requiring the coarsest grid to resolve the smallest-scale of the solution. The new method offers considerable savings in solving multiscale SPDEs. Numerical results are presented to demonstrate the accuracy and efficiency of the proposed method for several multiscale stochastic problems without scale separation.
BibTeX
@article{chung2018cluster,
  author = {Eric T. Chung and Yalchin Efendiev and Wing Tat Leung and Zhiwen Zhang},
  title = {{Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients}},
  journal = {Journal of Computational Physics},
  year = {2018},
  doi = {10.1016/j.jcp.2018.05.041},
}
Figure