Source-linked AI summary
Optimal Local Approximation Spaces for Generalized Finite Element Methods with Application to Multiscale Problems
Ivo Babuska, Robert Lipton
TL;DR
The paper addresses accurate approximation of elliptic problems in heterogeneous media with rough coefficients and potentially non-separated length scales. It uses GFEM with Kolmogorov n-width-based local spaces, combined through a Galerkin method, and shows nearly exponential global energy-norm convergence; homogenization provides exponentially convergent pre-asymptotic spaces for sufficiently fine microstructures.
Problem
The paper seeks accurate numerical approximations for second-order elliptic problems in heterogeneous media with rough L∞ coefficients, including microstructured media and multiple non-separated length scales.
Method
The method partitions Ω into local subdomains, uses Kolmogorov n-width spectral problems to construct local spaces, and combines them in GFEM for Galerkin approximation.
Results
The Galerkin error decays almost exponentially, or super-algebraically, with total degrees of freedom N; homogenized coefficients also produce exponentially decreasing pre-asymptotic error for sufficiently fine microstructures.
Takeaways & Limitations
Optimal local spaces enable accurate GFEM approximation, while homogenization can construct nearly optimal spaces when subdomains are large relative to the heterogeneity scale.
Takeaways & Limitations
The paper does not address the best local-domain sizes for maximum computational efficiency in parallel implementation.
Abstract
from arXiv · showhide
The paper addresses a numerical method for solving second order elliptic partial differential equations that describe fields inside heterogeneous media. The scope is general and treats the case of rough coefficients, i.e. coefficients with values in $L^\infty(Ω)$. This class of coefficients includes as examples media with micro-structure as well as media with multiple non-separated length scales. The approach taken here is based on the the generalized finite element method (GFEM) introduced in \cite{107}, and elaborated in \cite{102}, \cite{103} and \cite{104}. The GFEM is constructed by partitioning the computational domain $Ω$ into to a collection of preselected subsets $ω_{i},i=1,2,..m$ and constructing finite dimensional approximation spaces $Ψ_{i}$ over each subset using local information. The notion of the Kolmogorov $n$-width is used to identify the optimal local approximation spaces. These spaces deliver local approximations with errors that decay almost exponentially with the degrees of freedom $N_{i}$ in the energy norm over $ω_i$. The local spaces $% Ψ_{i}$ are used within the GFEM scheme to produce a finite dimensional subspace $S^N$ of $H^{1}(Ω)$ which is then employed in the Galerkin method. It is shown that the error in the Galerkin approximation decays in the energy norm almost exponentially (i.e., super-algebraicly) with respect to the degrees of freedom $N$. When length scales "`separate" and the microstructure is sufficiently fine with respect to the length scale of the domain $ω_i$ it is shown that homogenization theory can be used to construct local approximation spaces with exponentially decreasing error in the pre-asymtotic regime.
1 Introduction
The paper develops a GFEM strategy for heterogeneous elliptic problems with rough coefficients, targeting accurate, parallelizable simulation through optimal local approximation spaces. It combines Kolmogorov n-width analysis with GFEM and homogenization to obtain nearly exponential convergence.
- Motivation: GFEM partitions the domain into local subsets and combines independent local computations, reducing computational work for large heterogeneous structures.The method is designed for parallel computers and uses a partition of unity.
- Contribution: The paper identifies optimal local spaces through the Kolmogorov n-width and an associated spectral problem.These spaces apply to subdomains both inside the domain and intersecting its boundary.
- Contribution: Local approximation errors decay almost exponentially with the local degrees of freedom Ni in the energy norm.The result concerns the newly identified finite-dimensional local spaces.
- Global convergence: The resulting GFEM Galerkin error decays almost exponentially, or super-algebraically, with the total degrees of freedom N.The local spaces are combined into a finite-dimensional GFEM subspace of H^1(Ω).
- Homogenization: Homogenized coefficients yield nearly optimal local spaces when each subdomain is large relative to the heterogeneity length scale.For uniformly fine microstructures, examples show exponentially decreasing error in the pre-asymptotic regime.
- Homogenization: The implementation guideline chooses subdomains large relative to local heterogeneity but small enough for statistical uniformity.The paper presents this as a rule of thumb motivated by homogenization theory.
2 The generalized finite element method (GFEM)
GFEM constructs global trial spaces from local approximation spaces attached to a partition of unity. The Galerkin error is controlled by local approximation accuracy, motivating the selection of nearly optimal local spaces.
- Galerkin approximation: The Galerkin approximation solves the variational problem within the GFEM space, and its energy-norm error follows the available approximation error.If a GFEM function approximates the exact solution within ε, the Galerkin solution also has energy error at most ε.
- GFEM construction: GFEM begins with an open cover of Ω and a subordinate partition of unity whose functions are supported on local subdomains ωi.Each point belongs to at most κ subdomains, and the partition functions satisfy boundedness and support conditions.
- GFEM construction: Each local space Ψi is a finite-dimensional subspace of H^1(ωi) with dimension Ni.The global GFEM space is assembled from these local spaces.
- GFEM construction: The resulting global space has dimension N equal to the sum of the local dimensions Ni.The partition-of-unity construction ensures the global space lies in H^1(Ω).
- Accuracy: Theorem 2.1 shows that selecting suitable local spaces is essential for optimal GFEM accuracy.The theorem applies to the Neumann problem and also holds for Dirichlet conditions with boundary modifications.
- Accuracy: Including constants in the local spaces can allow the first term in the theorem’s error bound to be omitted.This simplification holds for an appropriate choice of constant when every local space contains constant functions.
3 Optimal local approximation spaces and nearly exponential upper bounds on their accuracy
The paper identifies optimal local GFEM spaces through Kolmogorov n-widths and shows nearly exponential approximation convergence for interior and boundary subdomains, including the resulting global GFEM space.
- Local approximation framework: The GFEM local-space problem is posed for A-harmonic fields on nested subdomains, with the outer domain supplying local heterogeneous information.The restriction operator from the outer A-harmonic space to the inner space is compact, after quotienting out constants.
- Optimal local spaces: Kolmogorov n-widths formulate optimality, and the optimal space is spanned by restrictions of the first n eigenfunctions of the compact self-adjoint operator P*P.The same characterization is stated through the eigenfunctions and eigenvalues associated with the local restriction operator.
- Interior convergence: Nearly exponential convergence holds for optimal interior local spaces for general coercive, bounded L∞(Ω) coefficients once n exceeds an ε-dependent threshold.The theorem provides an upper bound of the form I(ω,ω*) C^n for the local energy-norm error.
- Boundary convergence: Boundary-touching subdomains admit analogous optimal spaces and nearly exponential convergence under the stated C1 boundary-coordinate assumption.The boundary construction uses a truncated cube and a boundary projection, with the local fields defined on Ω∩ω*.
- Global GFEM convergence: Combining local spaces with constants in the GFEM yields a global Galerkin approximation whose energy-norm error converges nearly exponentially with total degrees of freedom N.The construction distinguishes interior spaces from boundary spaces augmented by the relevant affine component.
4 Implementation of the multiscale GFEM method
The implementation constructs local optimal bases from A-harmonic functions and combines them through a partition of unity into a sparse global GFEM system. The paper outlines parallel assembly, computational costs, and an example exhibiting exponential error decay, while leaving some implementation questions for future work.
- Local basis construction: Local bases are computed from eigenfunctions of problems (3.6) and (3.30), using a subspace method based on boundary-generated A-harmonic functions.The method starts with M>N boundary functions, solves corresponding Neumann problems, and uses the resulting subspace to approximate the first N eigenfunctions.
- Global assembly: The partition of unity combines local bases into a global basis, preserving sparsity and enabling local parallel assembly of the global stiffness matrix.The implementation also separates multiple parallel local-basis computations from the single global solve.
- Implementation accuracy: For sufficiently smooth boundary functions, the authors conjecture an energy error of order C h^γ M^δ ||u||_E(ω*) and plan to analyze it in future work.For the fiber-material mesh, they expect γ=2 and a negligible effect of M.
- Computational cost: The choice of local-domain sizes ω and ω* is identified as important for computational efficiency but is not addressed.The global solve and local-basis costs are estimated, but the best domain-size choice for parallel computation remains open.
- Numerical example: In the shaft example, harmonic-polynomial boundary functions produce a relative energy-norm error decaying at rate e^-0.48n, compared with the estimate e^-0.33n, where n=2k+1.The local spaces are finite-element approximations computed on sufficiently fine meshes, and the reported error decay is exponential.
- Numerical example: The simulations report slower convergence as the distance between ω and ω* decreases, with exponential convergence vanishing when the two domains coincide.This identifies separation between the local approximation domain and its oversampling domain as a practical condition for the observed rate.
5 Homogenization of the n-width and exponential decay of approximation error in the pre-asymptotic regime
The paper identifies homogenization limits for the Kolmogorov n-width and optimal local approximation bases under H-convergence. These results yield exponentially decreasing approximation errors in a pre-asymptotic regime for sufficiently fine heterogeneities.
- The construction applies to general H-convergence and G-convergence settings, including heterogeneous media with uniformly fine microstructure relative to the local domains.
- The limiting eigenfunctions and eigenvalues are obtained through the compact restriction operator and its self-adjoint spectral problem.
- The homogenization limit of the n-width and optimal approximation space is identified for coefficient sequences H-converging to a limit coefficient.
- Theorem 5.1 establishes subsequential convergence of heterogeneous optimal basis functions to the corresponding optimal basis for the homogenized coefficient.
- For sufficiently small characteristic heterogeneity scales, the homogenized optimal basis gives exponential approximation-error decay in the pre-asymptotic regime.
6 Implementation in the pre-asymptotic regime and more examples of exponential convergence
The implementation replaces costly optimal eigenfunction computations with approximation spaces derived from homogenized coefficients. Under sufficiently fine heterogeneity, these spaces achieve exponential pre-asymptotic convergence.
- The implementation constructs local spaces from homogenized optimal bases and applies them to coefficient sequences H-converging to a homogenized matrix.
- When the homogenized coefficient is constant and the subdomains are concentric ellipsoids, explicit functions provide cheaper-to-compute approximation spaces than the optimal eigenvalue problem.
- For fiber composites, the local domain must be sufficiently large relative to the fiber cross-section length scale.
- For sufficiently small heterogeneity scales, the constructed spaces approximate heterogeneous solutions with an error bounded by e^{-|ln(r/r*)|(n+1)} + τ in the energy norm.
- The examples demonstrate exponential convergence in the pre-asymptotic regime when the size and separation of inclusions are sufficiently small.
- The fiber volume fraction varies from 45% to 65% across the sample, indicating statistical inhomogeneity correlated with effective elastic-property variation.
A Appendix
The appendix proves a Caccioppoli inequality and uses it with compactness arguments to establish compactness of restriction operators between spaces of A-harmonic functions, including a domain-intersection variant.
- A Appendix: A cutoff function is introduced to prove the Caccioppoli inequality in Lemma 3.1.The function satisfies 0 ≤ η ≤ 1, equals 1 inside O, and has gradient bounded by 1/δ on ω∗.
- A Appendix: The restriction operator from H_A(ω∗)/R to H_A(ω)/R is defined by restricting each A-harmonic function to the smaller cube.The appendix considers two concentric cubes ω ⊂ ω∗.
- A Appendix: A sequence bounded in the energy norm over ω∗ has a subsequence converging in H1(ω) to an element of H_A(ω)/R.Poincare, Rellich compactness, and the Caccioppoli inequality yield convergence, while the weak formulation shows the limit is A-harmonic.
- A Appendix: For a C1 domain, the same compactness conclusion holds for restriction from H_A,0(ω∗∩Ω)/R to H_A,0(ω)/R.The construction uses concentric cubes with side lengths σ and σ∗ = (1 + ρ)σ and assumes both domain intersections have nonzero volume.
- A Appendix: The compactness proof proceeds after establishing the relevant estimate and then follows the earlier compactness argument.The appendix explicitly refers back to the proof of Lemma A.1 after obtaining (A.6).