Efficient optimization-based quadrature for variational discretization of nonlocal problems

Marco Pasetto, Zhaoxiang Shen, Marta D'Elia, Xiaochuan Tian, Nathaniel Trask, David KamenskyarXiv 2022 · DOI · OpenReview

TL;DR

This paper introduces a novel way to solve nonlocal models (like peridynamics) using Finite Element Methods without the "geometric nightmare" of calculating intersections between mesh elements and interaction balls. By using Generalized Moving Least Squares (GMLS) to compute integration weights, the authors achieve a scheme that is easier to implement, passes the patch test, and is "asymptotically compatible" with classical local models.

What Problem Does This Paper Address?

Nonlocal models are powerful tools for simulating phenomena where small-scale effects influence global behavior, such as fracture mechanics, turbulence, and image processing. Unlike standard partial differential equations (PDEs) that look only at a point's immediate neighbors, nonlocal models use integral operators to sum up interactions within a "horizon" (a ball of radius $\delta$).

When you try to solve these using the Finite Element Method (FEM), you run into a massive computational bottleneck: the double integral. To assemble the stiffness matrix, you must compute an inner integral over the intersection of a mesh element and the interaction ball. Identifying and parameterizing these overlapping shapes is a complex computational geometry problem that is both slow to run and difficult to code, especially in 3D or with irregular meshes.

Methods

The authors propose a "change of perspective." Instead of trying to integrate element-by-element, they perform the inner integration over the entire ball $\mathcal{H}(\mathbf{x}, \delta)$.

The secret sauce is Generalized Moving Least Squares (GMLS). Here’s how it works:

  1. Point Distribution: They distribute a set of quadrature points over the full ball, regardless of how the ball intersects the underlying mesh elements.
  2. Optimization: They solve an equality-constrained optimization problem to find the quadrature weights. The goal is to find weights that integrate a specific set of basis functions (polynomials) exactly over the ball.
  3. Boundary Treatment: A key innovation is the "special treatment" of the boundary. Near the edges of the domain, the interaction ball is "truncated." The authors found that naively calculating weights for these partial balls leads to high errors. By extending the interaction domain during the weight calculation, they restore high-order accuracy.

This approach effectively "outsources" the geometric complexity to a one-time optimization step, allowing the use of standard, global quadrature rules.

Datasets

As a theoretical and numerical analysis paper, the authors do not use external "big data" sets. Instead, they use manufactured solutions to benchmark the algorithm:

  • 1D Cases: Sinusoidal and linear functions on a unit interval.
  • 2D Cases: A tensor-product sinusoidal function on a unit square.
  • Grids: They tested both uniform grids and non-uniform grids (created by randomly perturbing the nodes of a uniform mesh by a factor $\epsilon$).

Key Insights and Ideas

  • Circumventing Geometry: The most significant "aha moment" is that you don't actually need to calculate the intersection of a ball and a triangle (or hex). If your quadrature weights are optimized to integrate the FE basis functions correctly over the ball, the mesh layout becomes secondary.
  • Asymptotic Compatibility: The paper proves the method is "asymptotically compatible." This means that as the mesh size ($h$) and the horizon ($\delta$) both shrink to zero, the nonlocal solution correctly converges to the solution of the corresponding local PDE.
  • The Importance of the Boundary: The authors show that error concentrates at the boundaries if the quadrature weights don't account for the "missing" parts of the interaction ball. Their domain extension technique ($t_e$) is the fix that enables second-order convergence.

Key Results

  • Accuracy: On uniform grids, the method achieves second-order convergence in the $L^2$ norm and first-order in the $H^1$ norm.
  • The Patch Test: For uniform discretizations, the method passes the "patch test," meaning it can reproduce linear solutions with machine-level precision (errors around $10^{-14}$).
  • Robustness: Even on non-uniform (distorted) grids, the method maintains at least first-order convergence and often shows second-order behavior in "pre-asymptotic" regimes (the mesh sizes typically used in engineering).
  • Implementation: Because it avoids complex geometric intersections, the GMLS subroutine can be easily embedded into existing FE codes.

Limitations and Future Work

  • Non-uniform Grid Degradation: While the method performs well on non-uniform grids, the authors acknowledge that the convergence rate theoretically drops to first-order (or even zeroth-order in extreme cases) as the mesh is refined infinitely.
  • Computational Cost of GMLS: While it avoids geometric calculations, you still have to solve a small optimization problem for different "types" of balls. On a uniform mesh, this is cheap (you do it once and reuse it), but on highly irregular meshes, it might add overhead.
  • Theoretical Scope: The rigorous proof of convergence provided in the paper is currently limited to the 1D uniform case. Extending this proof to 2D/3D and non-uniform meshes is a clear next step.
  • L2 Error Estimates: The authors suggest that future work should focus on obtaining "sharp" $L^2$ error estimates to better explain why the method often performs better than the $H^1$ theory predicts.

Summary updated

Abstract

Casting nonlocal problems in variational form and discretizing them with the finite element (FE) method facilitates the use of nonlocal vector calculus to prove well-posedeness, convergence, and stability of such schemes. Employing an FE method also facilitates meshing of complicated domain geometries and coupling with FE methods for local problems. However, nonlocal weak problems involve the computation of a double-integral, which is computationally expensive and presents several challenges. In particular, the inner integral of the variational form associated with the stiffness matrix is defined over the intersections of FE mesh elements with a ball of radius $\delta$, where $\delta$ is the range of nonlocal interaction. Identifying and parameterizing these intersections is a nontrivial computational geometry problem. In this work, we propose a quadrature technique where the inner integration is performed using quadrature points distributed over the full ball, without regard for how it intersects elements, and weights are computed based on the generalized moving least squares method. Thus, as opposed to all previously employed methods, our technique does not require element-by-element integration and fully circumvents the computation of element-ball intersections. This paper considers one- and two-dimensional implementations of piecewise linear continuous FE approximations, focusing on the case where the element size h and the nonlocal radius $\delta$ are proportional, as is typical of practical computations. When boundary conditions are treated carefully and the outer integral of the variational form is computed accurately, the proposed method is asymptotically compatible in the limit of $h \sim \delta \to 0$, featuring at least first-order convergence in L^2 for all dimensions, using both uniform and nonuniform grids.
BibTeX
@misc{pasetto2022efficient,
  author = {Marco Pasetto and Zhaoxiang Shen and Marta D'Elia and Xiaochuan Tian and Nathaniel Trask and David Kamensky},
  title = {{Efficient optimization-based quadrature for variational discretization of nonlocal problems}},
  year = {2022},
  eprint = {2201.12391},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2201.12391},
}
Figure