{'fraction_non_alphanumeric': 0.055595102505694764, 'fraction_numerical': 0.014877562642369021, 'mean_word_length': 3.967821782178218, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exponential decay of the resonance error in numerical homogenization via parabolic and elliptic cell problems

This paper presents two new approaches for finding the homogenized coefficients of multiscale elliptic PDEs. Standard approaches for computing the homogenized coefficients suffer from the so-called resonance error, originating from a mismatch between the true and the computational boundary conditions. Our new methods, based on solutions of parabolic and elliptic cell-problems, result in an exponential decay of the resonance error.


Introduction
We consider the numerical homogenization of multiscale elliptic partial differential equations (PDEs) of the form −∇ · (a ε (x)∇u ε ) = f in Ω ⊂ R d where a ε ∈ [L ∞ (Ω)] d×d is symmetric, uniformly elliptic and bounded, and ε ≪ |Ω| 1/d = O(1) is the wave-length of the small scale variations in the medium. A direct numerical approximation of u ε by standard finite element/difference methods is prohibitively expensive as the ε-scale variations need to be resolved on the whole computational domain Ω. Homogenization theory aims at finding an effective coefficient a 0 (or solution u 0 ) such that −∇ · a 0 (x)∇u 0 = f describes the coarse-scale behaviour of (1). The coefficient a 0 (and hence the solution) is no more oscillatory, and a standard solver may be directly applied to the homogenized system once a 0 is determined. Explicit representations for a 0 are available only in a few cases, such as periodic microstructures or stationary ergodic random materials. For example, when the medium is such that a ε (x) = a(x/ε), and a is a K := [−1/2, 1/2] d -periodic function, then a 0 is given by |K| K e i + ∇χ i (y) · a(y) e j + ∇χ j (y) dy, where χ i is a K-periodic solution of the so-called corrector problem, see [6,9,13]: − ∇ · a(y) ∇χ i + e i = 0 in K.
In several situations of interest, e.g. when the period of a is not known or when a is quasi-periodic or stochastic, equations (2) and (3) have to be posed over the whole R d . In this case, we write a 0 = lim R→+∞ a 0,R , where In practice, the value of a 0,R can be computed only for finite values of R, and an error occurs due to the mismatch on the boundary ∂K R between the values of ψ i R and χ i . This error will then propagate into the domain K R and deteriorate the accuracy of the approximation a 0,R . It is well-known that if a is K-periodic and R is not integer, then a 0,R − a 0 F ≤ CR −1 , see [4,10]. A similar result exists also for stationary ergodic random coefficients, both in continuous [8] and discrete [12] settings. This first order resonance error dominates all other discretization errors in modern multiscale methods and, therefore, better approximation techniques with reduced resonance errors are needed.
In order to reduce the resonance error, previous approaches improved the prefactor (but not the convergence rate) [15], or gave second order rates in 1/R [7], or fourth order in the asymptotic limit for large values of R [11]. Another strategy results in arbitrary orders in 1/R, but at the cost of solving a computationally expensive wave equation [5]. This paper, inspired by [14], presents two strategies based on parabolic and elliptic corrector problems which have exponentially decaying boundary errors at a cost comparable to the one of solving the classical elliptic model.

New algorithms for computing the homogenized tensor
It can be seen that the computation of homogenized coefficients is linked to the average of oscillatory functions, as formula (4) shows. A naive averaging of a K-periodic function f over K R converges to the mean value 1 |K| K f (y) dy with a first order accuracy in 1/R. To improve this accuracy to arbitrarily high rates, a set of smooth averaging filters can be used, see [11]. Definition 1. We say that a function µ : [−1/2, 1/2] → R + belongs to the space F q , q ≥ 1, if: For q = 0, we define µ ∈ F 0 as µ(y) = 1 [−1/2,1/2] , where 1 I is the characteristic function on the interval I.
We say that a function µ L : where µ ∈ F q and y i is the coordinate along the i-th direction.

A parabolic approach
In this section we introduce a numerical homogenization scheme based on the solution of parabolic differential equations, as proposed in the discrete setting [14], since the parabolic Green's function decays exponentially in space. This yields to a reduced influence of mismatching boundary values on the corrector functions. The new cell problems are defined by Then, the homogenized coefficient is approximated by As it will be shown in Section 3, the T parameter is crucial to obtain an exponential convergence of the resonance error.

A modified elliptic approach
The second approach that we propose can be viewed as adding a correction term to the elliptic cell problem (5) to reduce the boundary effect in the interior region K L . The new elliptic cell problems are given by where and {λ k , ϕ k } N k=1 are the first N dominant eigenvalues and eigenfunctions of the operator A := −∇ · (a(·)∇), equipped with Dirichlet boundary conditions. Moreover, g i (y) := ∇ · a(y)e i , and g i k := g i , ϕ k L 2 (KR) . The homogenized coefficient can then be approximated by It is worth mentioning that the correction term [e −AN T g i ](y) is an approximation to [e −AT g i ](y), which corresponds to the solution of the parabolic PDE (6) at time T . However, due to the exponential decay of the semigroup e −AT with respect to the eigenvalues of the operator A, one can approximate this correction term with exponential accuracy by computing a few dominant eigenmodes of A, instead of solving the full parabolic PDE (6).

Equivalence between the standard elliptic and the parabolic formulations
In this section, we give a proof of the equivalence between elliptic and parabolic equations, thus legitimating the use of (7) and (9), in place of (4), as upscaling model. In the statement of the results, we will refer to the space M(α, β, Ω), which consists of symmetric matrices a ∈ [L ∞ (Ω)] d×d such that α|ζ| 2 ≤ ζ · a(y)ζ ≤ β|ζ| 2 , ∀ζ ∈ R d , a.e. y ∈ Ω ⊂ R d . We will also use the notation Proof. We reformulate problem (6) as the abstract Cauchy problem in is defined as Au := −∇ · (a∇u). Then, u k R (t) = e −tA g k . We know that σ(A), the spectrum of A, is contained in an open sectorial domain α + S ω , where α ∈ R, α > 0 and S ω = z ∈ C : |arg z| < ω, 0 < ω < π 2 .
Then, the Dunford integral representation The first equality is given by the Dunford integral formula. The second equality is obtained by Fubini's theorem. The third equality is true because the double integral is bounded, lim t→+∞ e −tz = 0 since Re(z) > 0 on Γ. The last equality follows from the fact that the function f (z) = 1/z is holomorphic in the interior of α + S ω . Since A is an isomorphism and ψ k R is the weak solution of Aψ k R = g k , we have that A −1 g k = ψ k R and (10) is proved. To prove (11), we write the weak formulation of (5) and choose ψ j R = +∞ 0 u j R dt as test function: dt.
Using the semigroup property of e −tA and the self-adjointness of A we obtain KR ∇ψ k R (y) · a(y)∇ψ j R (y) dy = +∞ 0 u k R (·, t/2), u j R (·, t/2) and conclude the proof by the change of variable t/2 → t.
By the symmetry of a and the weak form of (5), we can rewrite (4) as: Theorem 1 provides an equivalent expression, based on the solutions u i R of the parabolic cell problems (6) over infinite time domain, for the second integral in the above expression. This result is summarized as a corollary below. Corollary 1. Let a satisfy the assumptions of Theorem 1, a 0,R be defined by (4) and a 0,R,R,+∞ be defined by (7) with µ R ∈ F 0 (K R ) (note that L = R). Then a 0,R,R,+∞ = a 0,R .
Hence, using the classical result stated in Section 1, there exist a constant C > 0 independent of R such that a 0,R,R,+∞ − a 0 F ≤ C R .
From this analysis, we can immediately see that, when T = +∞, the parabolic approach does not result in any gain in comparison to the standard cell-problem (5), as the two strategies are equivalent and have first order convergence rates in 1/R. (7) The following Theorem 2 shows that an exponential convergence rate for the boundary error can be attained when the parameter T is sufficiently small and an appropriate filter is used, as fully proved in [2]. If the coefficients a ij (y) are K-periodic and (6) is solved with periodic boundary conditions and integer R, then Theorem 1 still holds true by substituing functions ψ i R in (10) and (11) with χ j defined in (3). Thus, it is possible to find an equivalent formula for the exact homogenized coefficients, which is based on a parabolic model with periodic boundary conditions. The proof of Theorem 2 is based on such an equivalence result and on a decomposition of the resonance error in several terms, respectively accounting for the averaging error of periodic functions, the boundary mismatch between the two problems and the truncation in time.

Exponential convergence of the parabolic approach
Theorem 2. Let a ∈ M(α, β, K R ) be K-periodic, ∇·(ae i ) ∈ L 2 (K R ) for any i = 1, . . . , d, µ L ∈ F q (K L ), for 0 < L < ⌊R⌋, R > 1 and T > 0. Then where C > 0 is a constant independent of R, L, T and c = 1/4β. Moreover, the choices L = (1 − k o )R and T = k T R, with 0 < k o < 1 and k T = ko π √ 4βα result in the following convergence rate in terms of R: with ζ = πk o 2 β/α and γ(R) = 1 + The term L −(q+1) is the averaging error induced by using a filter function µ L ∈ F q (K L ), and it can be made arbitrarily small by taking higher values for q. The term e −απ 2 T originates from using a finite T for the parabolic cell problem (6). The remaining terms are the errors due to the boundary conditions, which decay exponentially provided T < |R − L| 2 . Moreover, the quasi-optimal scaling of L and T in terms of R are found by equating the exponents of the truncation and boundary errors. Note that bound (12) is similar to the one obtained in [11], except for the term T −2 that accounts for the effect of using a biased model equation. (9) The boundary error associated with formula (9) relies on how the parameter T is tuned, similarly to the parabolic case. If T = +∞, then the term e −AN T g j vanishes, and the standard Dirichlet cell problem (5) is recovered. Hence, no improvement over the first order convergence rate will be observed. In the following theorem, we specify the precise exponential upper bound for the modified elliptic approach. The proof is based on the equality lim

Exponential convergence of the modified elliptic approach
Theorem 3. Let a ∈ M(α, β, K R ) be K-periodic, ∇·(ae i ) ∈ L 2 (K R ) for any i = 1, . . . , d, µ L ∈ F q (K L ), for 0 < L < ⌊R⌋, R > 1 and T > 0. Then where C > 0 is a constant independent of R, L and T but may depend on a and µ, c = 1/4β and c d > 0 is a constant (independent of R, T, L) that may depend on the dimension d, α and β. Moreover, the 2βα result in the following convergence rate in terms of R: The upper bounds in Theorem 3 have a similar character to those in Theorem 2, except the error which comes from the spectral truncation. In particular, Theorem 3 shows that an exponential convergence (for the spectral error) will be achieved if the number of modes scales as N = O(R d ) and T = O(R). In practice, small values of R, e.g. R = 10, are preferred for simulations. This makes the elliptic approach very favourable both from a computation and accuracy point of view.

Numerical validation
Here, we show the results of numerical tests performed using a two-dimensional periodic tensor for validating the convergence rates of Theorems 2 and 3 (note that both theorems assume periodicity of the coefficient). In particular, we consider the following 2 × 2 tensor We compute a numerical approximation of a 0,R,L,T and b 0,R,L,T,N for many values of R and with the optimal values for L and T (as expressed in Theorems 2 and 3). The error between the numerical approximations and the exact value a 0 is then plotted against R, see Figure 1. The reference value for a 0 is computed by solving the standard elliptic corrector problems (3) with R = 1, periodic boundary conditions and by using formula (2). Numerical approximations for the parabolic formulation (6) are computed by a P1-Finite Elements discretization with meshsize h = 1/100 in space, while a Rosenbrock formula of order 2 with tolerance tol = 10 −5 and adaptive stepping scheme is used in time. For the modified elliptic approach we used a meshsize h = 1/160 and N = 60 eigenmodes for approximating the right-hand side e −AN T g j , in disregard of the size R.
The decay of the overall upscaling error is pictured in Figure 1. In particular, for relatively low to moderate values of R, e.g., 1 < R ≤ 10, the exponentially decaying boundary error is negligible in comparison to the averaging error when q = 1 and q = 3.
Besides the improved convergence rate, it is desirable that the computational cost of the proposed methods is comparable to the one of the classical model, that equals the cost of solving d linear systems. Those can be solved by different numerical schemes, from LU decomposition, more suitable for smaller and two dimensional problems, to iterative methods like GMRES or CG, that are more indicated for large systems coming from three dimensional models. The first of the two proposed approaches, the parabolic model, can be efficiently solved by stabilized explicit ODE solver (such as RKC2 [16] or ROCK4 [1]), whose algorithms perform cheap matrix-vector multiplications iteratively. The number of iterations depends on the number of time steps and stages, but not on the dimension of the system. Lastly, the modified elliptic method has the same cost as the classical model, with the additional expense of accurately reconstructing the modified right-hand side by eigenfunction decomposition of the operator A. The eigenmodes computation can be done, for instance, by Krylov-Schur decomposition. A full analysis of the computational cost for the two methods will be addressed in future studies.