Albert Cohen
email: albert.cohen@sorbonne-universite.fr

Wolfgang Dahmen
email: wolfgang.anton.dahmen@googlemail.com

Matthieu Dolbeault
email: matthieu.dolbeault@sorbonne-universite.fr

Agustin Somacal
email: agustin.somacal@sorbonne-universite.fr

Reduced order modeling for elliptic problems with high contrast diffusion coefficients

We consider a parametric elliptic PDE with a scalar piecewise constant diffusion coefficient taking arbitrary positive values on fixed subdomains. This problem is not uniformly elliptic, as the contrast can be arbitrarily high, contrarily to the Uniform Ellipticity Assumption (UEA) that is commonly made on parametric elliptic PDEs. We construct reduced model spaces that approximate uniformly well all solutions with estimates in relative error that are independent of the contrast level. These estimates are sub-exponential in the reduced model dimension, yet exhibiting the curse of dimensionality as the number of subdomains grows. Similar estimates are obtained for the Galerkin projection, as well as for the state estimation and parameter estimation inverse problems. A key ingredient in our construction and analysis is the study of the convergence towards limit solutions of stiff problems when diffusion tends to infinity in certain domains.

Introduction

1.1 Reduced models for parametrized PDEs Parametric PDE's are commonly used to describe complex physical phenomena. With y = (y 1 , . . . , y d ) denoting a parameter vector ranging in some domain Y ⊂ R d , and u(y) the corresponding solution to the PDE of interest, assumed to be well defined in some Hilbert space V , we denote by

M := {u(y) : y ∈ Y }, (1.1)
the collection of all solutions, called the solution manifold.

There are two main ranges of problems associated to parametric PDEs:

1. Forward modeling: in applications where many queries of the parameter to solution map y → u(y) are required, one needs numerical forward solvers that efficiently compute approximations ũ(y) with a prescribed accuracy.

2. Inverse problems: when the exact value of the parameter y is unknown, one is interested in either recovering an approximation to u(y) (state estimation) or to y (parameter estimation), from a limited number of observations z i = i (u(y)), possibly corrupted by noise.

Reduced order modeling is widely used for tackling both problems. In its most common form, its aim is to construct linear spaces V n of moderate dimension n that approximate all solutions u(y) with best possible certified accuracy. The natural benchmark for measuring the performance of such linear reduced models is provided by the Kolmogorov n-width of the solution manifold

d n (M) V := inf dim(Vn)=n dist(M, V n ) V (1.2)
that describes the performance of an optimal space. Here

dist(M, V n ) V := sup u∈M inf v∈Vn u -v V = sup u∈M u -P Vn u V ,
where P Vn is the V -orthogonal projector onto V n . We refer the reader to [START_REF] Pinkus | N -widths in approximation theory[END_REF] for a general treatment of n-widths.

While an optimal space achieving the above infimum is usually out of reach, there exist two main approaches aiming to construct "sub-optimal yet good" spaces. The first one consists in building expansions of the parameter to solution map, for example by polynomials u n (y) := ν∈Λn u ν y ν , y ν := y ν1 1 . . . y ν d d ,

where Λ n ⊂ N d is a set of cardinality n. The coefficients u ν are elements of V and therefore, for all y ∈ Y the approximation u n (y) is picked from the space

V n := span{u ν : ν ∈ Λ n }.
Notice that u n (y) is not the orthogonal projection P Vn u(y) in this case, but u n (y) is easy to compute for a given query y once the u ν have been constructed (usually through a high fidelity finite element solver). We refer to [START_REF] Babuška | A stochastic collocation method for elliptic partial differential equations with random input data[END_REF][START_REF] Beck | Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison[END_REF][START_REF] Beck | Implementation of optimal Galerkin and collocation approximations of PDEs with random coefficients[END_REF][START_REF] Bachmayr | Sparse polynomial approximation of parametric elliptic pdes. part i: affine coefficients[END_REF][START_REF] Cohen | Approximation of high-dimensional parametric pdes[END_REF][START_REF] Cohen | Analytic regularity and polynomial approximation of parametric and stochastic PDEs[END_REF][START_REF] Tran | Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients[END_REF] for instances of this approach. The second approach is the reduced basis method [START_REF] Haasdonk | Reduced basis methods for parametrized PDEs -a tutorial introduction for stationary and instationary problems[END_REF][START_REF] Rozza | Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations -application to transport and continuum mechanics[END_REF][START_REF] Sen | Reduced-basis approximation and a posteriori error estimation for many-parameter heat conduction problems[END_REF], that consists in taking

V n := span{u 1 , . . . , u n },

where the u j = u(y j ) are particular solution instances corresponding to a selection of parameter vectors y j ∈ Y . A close variant is the proper orthogonal decomposition method [START_REF] Chatterjee | An introduction to the proper orthogonal decomposition[END_REF][START_REF] Volkwein | Proper Orthogonal Decomposition: Theory and reduced order modeling[END_REF][START_REF] Willcox | Balanced model reduction via the proper orthogonal decomposition[END_REF], where the reduced spaces are obtained by principal component analysis applied to large training set of such instances. In the reduced basis method, the parameter vectors y 1 , . . . , y n can be selected by a greedy algorithm, introduced in [START_REF] Veroy | A Posteriori Error Bounds for Reduced-Basis Approximation of Parametrized Noncoercive and Nonlinear Elliptic Partial Differential Equations[END_REF] and originally studied in [START_REF] Buffa | A Priori convergence of the greedy algorithm for the parameterized reduced basis[END_REF]. For such a selection process, it is proved in [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF][START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF] that if d n (M) V has a certain algebraic or exponential rate of decay with n, then a similar rate is achieved by dist(M, V n ) V for the reduced basis spaces. It follows that the reduced basis spaces constructed by the greedy algorithm are close to optimal. This is in contrast to the spaces V n spanned by the polynomial coefficients u ν for which the approximation rate is not guaranteed to be optimal. We refer to [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF] for instances where reduced basis methods can be proved to converge with a strictly higher rate than polynomial approximations. On the other hand, the polynomial constructions (1.3) have certain numerical advantages. Namely, for several relevant classes of parametrized PDEs, it can be shown that the parameter to solution mapping y → u(y) has certain smoothness properties that can be used to obtain a-priori bounds on the u ν V without actually computing these norms. This allows an a priori selection of an appropriate set Λ n and the proof of concrete approximation estimates for the error sup y∈Y u(y) -u n (y) V . These estimates in turn provide an upper bound for d n (M) V , and therefore for reduced basis approximations.

Parametrized elliptic PDEs

One prototypal instance where the convergence analysis described above has been deeply studied is the parametrized second order elliptic equation -div(a(y)∇u(y)) = f in Ω, u |∂Ω = 0 on ∂Ω, (1.4) where Ω ⊂ R m is the spatial domain, f ∈ H -1 (Ω) is a source term, and a(y) has the affine form

a(y) = a + d j=1 y j ψ j , (1.5)
with a and (ψ 1 , . . . , ψ d ) some fixed functions in L ∞ (Ω). The corresponding solution u(y) ∈ H 1 0 (Ω) is defined through the standard variational formulation in H 1 0 (Ω) equipped with its usual norm. Up to renormalization, it is usually assumed that the y j range in [-1, 1], or equivalently Y = [-1, 1] d . To ensure existence and uniqueness of solutions, one typically assumes that the so-called Uniform Ellipticity Assumption (UEA) holds: for some fixed 0

< r R < ∞, r a(x, y) R, x ∈ Ω, y ∈ Y, (1.6)
where a(x, y) := a(y)(x) = a(x)+ d j=1 y j ψ j (x), or in short r a(y) R for all y ∈ Y . Under this assumption, Lax-Milgram theory ensures that the solution map y → u(y) is well defined from Y into H 1 0 (Ω), with the uniform bound

u(y) H 1 0 := ∇u(y) L 2 C f r , y ∈ Y.
Here and throughout this paper

C f := f H -1 . (1.7)
It was proved in [START_REF] Beck | Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison[END_REF][START_REF] Tran | Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients[END_REF] that, under UEA, polynomial approximations (1.3) of given total degree converge sub-exponentially: for Λ n = {|ν| k} with n = k+d d , one has

sup y∈Y u(y) -u n (y) H 1 0 C exp(-cn 1/d ), (1.8)
Such sub-exponential rates show that the spaces V n based on polynomial expansions or reduced bases perform significantly better than standard finite element spaces, at least for a moderate number d of parameters. It is possible to maintain a rate of convergence as d grows, and even when d = ∞, when assuming some anisotropy in the variable y j through the decay of the size of ψ j as j → ∞, see in particular [START_REF] Bachmayr | Sparse polynomial approximation of parametric elliptic pdes. part i: affine coefficients[END_REF][START_REF] Cohen | Approximation of high-dimensional parametric pdes[END_REF][START_REF] Cohen | Analytic regularity and polynomial approximation of parametric and stochastic PDEs[END_REF] for results of this type.

High constrast problems

The Uniform Ellipticity Assumption (1.6) implies that there is a uniform control on the level of contrast in the diffusion function

κ(y) := max x∈Ω a(x, y) min x∈Ω a(x, y) R r , y ∈ Y. (1.9)
This assumption also plays a key role in the derivation of the above approximation results, since it guarantees that the parameter to solution map has a holomorphic extension to a sufficiently large complex neighbourhood of Y . In this case, a good polynomial approximation u n may be defined by simply truncating the power series ν∈N d u ν y ν , leading to the estimate (1.8).

On the other hand, there exist various situations where one would like to avoid such a strong restriction on the level of contrast. Perhaps the most representative setting is when the domain Ω is partitioned into disjoint subdomains {Ω 1 , . . . , Ω d }, each of them admitting a constant diffusivity level that could vary strongly between subdomains. This is typically the case when modeling diffusion in materials having multiple layers or inclusions that could have very different nature, for example air or liquid versus solid. This situation can be encountered in groundwater flow applications, where certain subdomains correspond to cavities, for which the diffusion function becomes nearly infinite, as opposed to subdomains containing sediments or other porous rocks.

In such a case, we do not want to limit the contrast level. To represent this setting, we let a(y [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF] or equivalently a(y) = d j=1 y j χ Ωj , which corresponds to the affine form (1.5) with a = 0 and ψ j = χ Ωj , now with

) |Ωj = y j , y j ∈]0, ∞[ (1.
Y :=]0, ∞[ d .
(1.11)

We take (1.11) as the definition of the parameter domain Y for the remainder of this paper. The solution u(y) satisfies the variational formulation

d j=1 y j ˆΩj ∇u(y) • ∇v dx = f, v H -1 ,H 1 0 , v ∈ H 1 0 (Ω), (1.12)
or equivalently -y j ∆u(y) = f as elements of H -1 (Ω j ) on each Ω j , with the standard jump conditions [a(y)∂ n u(y)] = 0 across the boundaries between subdomains.

Let us observe that in this setting, it is hopeless to find spaces V n that approximate all solutions u(y) uniformly well. Indeed, the following homogeneity property obviously holds: for any y ∈ Y and t > 0, one has u(ty) = t -1 u(y).

(1.13)

This property implies in particular that u(y) H 1 0 tends to infinity as y → 0, and so does u(y) -P Vn u(y) H 1 0 in general. In fact, this also shows that the solution manifold M is not relatively compact and does not have finite n-widths.

In addition to this principal difficulty, let us remind that when using the spaces V n in forward modeling, we typically use the Galerkin method, that delivers the orthogonal projection onto V n however for the energy norm

v 2 y := d j=1 y j ˆΩj |∇v| 2 dx. (1.14)
This approximation is thus optimal in H 1 0 (Ω), however up to the constant κ(y) 1/2 , which deteriorates with high contrast.

The main contribution of this paper is to treat these issues, and derive approximation estimates that are robust to high contrast, in the sense that they are independent of y ∈ Y .

Due to the main objection coming from the homogeneity property (1.13), it is natural to look for uniform approximation estimates in relative error, that is, estimates of the form

u(y) -P Vn u(y) H 1 0 ε n u(y) H 1 0 , y ∈ Y, (1.15)
with lim n→∞ ε n = 0, and similarly for P y Vn u(y). Our main results, Theorems 3.7 and 4.2, exhibit spaces V n ensuring the validity of such uniform estimates with ε n having sub-exponential decay with n, similar to the known results under UEA.

Remark 1.1. High contrast problems have been the object of intense investigation, in particular with the objective of developing techniques for multilevel or domain decomposition preconditioning [START_REF] Aksoyly | Robust multigrid preconditioners for cell-centered finite volume discretization of the high-contrast diffusion equation[END_REF][START_REF] Aksoylu | Towards a rigorously justified algebraic preconditioner for high-contrast diffusion problems[END_REF][START_REF] Galvis | Domain decomposition preconditioners for multiscale flows in high contrast media: reduced dimension coarse spaces[END_REF] and a-posteriori error estimation [START_REF] Ainsworth | Robust a posteriori error estimation for nonconforming finite element approximation[END_REF][START_REF] Bernardi | Adaptive finite element methods for elliptic equations with non-smooth coefficients[END_REF], that are provably robust with respect to the level of contrast. To our knowledge, the present work is the first in which this robustness is established for reduced modeling methods.

Outline

Throughout this paper, we consider the parametrized elliptic PDE (1.4) with a(y) having piecewise constant form (1.10) over a fixed partition. In view of the homogeneity property (1.13), we are led to consider the subset

Y := [1, ∞[ d (1.16)
of parameters corresponding to the coercive regime. Any result on relative approximation error that is established for Y extends automatically to all of Y because of the homogeneity property. Accordingly, we let

B := {u(y) : y ∈ Y }.
(1.17)

In §2, we start by proving that B is a precompact set of H 1 0 (Ω). One crucial ingredient for this analysis are the limit solutions of the so-called stiff problem, obtained as y j → ∞ for certain j ∈ {1, . . . , d}.

In §3, we construct specific reduced model spaces for which the approximation estimate (1.15) holds with ε n decaying sub-exponentially. Our construction is based on partitioning the parametric domain Y into rectangular regions and using a different polynomial approximations on each region. This results in global reduced model space V n for which the accuracy bound remains subexponential, however in exp(-cn 1 2d-2 ). A key ingredient for establishing these sub-exponential rates is the derivation of quantitative estimates on the convergence of u(y) towards limit solutions defined in §2 as some y j tend to infinity. These estimates are established under an additional geometrical assumption on the partition, similar results for a general partition of Ω being an open problem.

In §4, we discuss the use of these reduced model spaces in forward modeling and inverse problems. Our main result relative to forward modeling is that the estimate (1.15) also holds for the Galerkin projection with the same exponential decay ε n . We show that such a result is only possible if V n includes functions that have constant values over some subdomains. For the state estimation problem, we follow the Parametrized Background Data Weak (PBDW) method [START_REF] Binev | Data assimilation in reduced modeling[END_REF][START_REF] Maday | A parametrizedbackground data-weak approach to variational data assimilation: Formulation, analysis, and application to acoustics[END_REF], and obtain recovery bounds that are uniform over y ∈ Y in relative error. For the parameter estimation problem, we introduce an ad-hoc strategy that specifically exploits the piecewise constant structure of the diffusion coefficient and obtain similar recovery bounds for the inverse diffusivity.

We conclude in §5 by presenting some numerical illustrations revealing the effectiveness of the reduced model spaces even in the high-contrast regime, as expressed by the approximation results.

Uniform approximation in relative error

In this section we work under no particular geometric assumption on the partition {Ω 1 , . . . , Ω d } of Ω, and consider the solution manifold M defined by (1.1), where u(y) ∈ H 1 0 (Ω) is solution to the elliptic boundary value problem with variational formulation (1.12). Our objective is to show the existence of spaces V n that uniformly approximate M in the relative error sense expressed by (1.15).

Limit solutions and the extended solution manifold

Our first observation is that this collection can be continuously extended when y j = ∞ for some values of j, through limit solutions of stiff inclusions problems. Such limit solutions have for example been considered in the context homogeneization, see e.g. p.98 of [START_REF] Jikov | Homogeneization of differential operators and integral functionals[END_REF].

For this purpose, to any S ⊂ {1, . . . , d}, we associate the space

V S := {v ∈ H 1 0 (Ω) : ∇v |Ωj = 0, j ∈ S}. (2.18)
In other words, V S consists of the functions from H 1 0 (Ω) that have constant values on the subdomains Ω j for j ∈ S (or on each of their connected components if these subdomains are not connected). It is a closed subspace of H 1 0 (Ω). We decompose the parameter vector y according to y = (y S , y S c ), y S := (y j ) j∈S and y S c := (y j ) j∈S c .

(

For any finite and positive vector y S c , similar to the • y norm (1.14), we may define v 2 y S c :=

j∈S c y j ˆΩj |∇v| 2 dx, (2.20)
which is a semi-norm on H 1 0 (Ω), and a full norm equivalent to the H 1 0 -norm on V S . Also note that when y = (y S , y S c ) is finite, one then has v y S c = v y for any v ∈ V S .

For any finite and positive vector y S c , we define the function u S (y S c ) ∈ V S solution to the following stiff inclusions problem:

j∈S c y j ˆΩj ∇u S (y S c ) • ∇v dx = f, v H -1 ,H 1 0 , v ∈ V S . (2.21)
The following result shows that this solution is well defined and is the limit of u(y), when y S c is fixed and y j → ∞ for j ∈ S. Note that the weak convergence is established in [START_REF] Jikov | Homogeneization of differential operators and integral functionals[END_REF] (p. 98) and so we concentrate the proof on the strong convergence.

Lemma 2.1. There exists a unique u S (y S c ) ∈ V S solution to (2.21), which is the limit in H 1 0 (Ω) of the solution u(y S , y S c ) as y j → ∞ for all j ∈ S.

Proof. Using the bilinear form (u, v) → j∈S c y j ´Ωj ∇u • ∇v dx in the space V S , Lax-Milgram theory implies the existence of a unique solution u S (y

S c ) ∈ V S to (2.21). Consider now a sequence (y n ) n 1 ∈ Y N , with y n S c = y S c and y n j → ∞ for all j ∈ S. Denoting u n = u(y n ), it is readily seen that (u n ) n 1 is uniformly bounded in H 1 0 norm by C = C f c -1
, where c := min n 1 min 1 j d y n j > 0, and that any weak limit of a sequence extraction is solution to the variational equation (2.21). Therefore the whole sequence (u n ) n 1 weakly converges to ū = u S (y S c ).

We finally prove strong convergence by writing

c u n -ū 2 H 1 0 ˆΩ a(y n )|∇(u n -ū)| 2 dx = f, u n H -1 ,H 1 0 -2 ū, u n y S c + ū 2 y S c -→ n→∞ f, ū H -1 ,H 1 0 -ū 2 y S c = 0.
The above lemma allows us to readily extend the solution manifold by introducing

Y :=]0, ∞] d , and
M := {u(y) : y ∈ Y },
where we have formally set u(y) := u S (y S c ), when y j = ∞ for j ∈ S and y j < ∞ for j ∈ S c . Note that when S = {1, . . . , d} the space V S is trivial and one has u(∞, . . . , ∞) = 0.

Remark 2.2. Although we do not make explicit use of it, it can be checked that despite the fact that y j = 0 is excluded in the definition of M, it indeed coincides with the closure of M in H 1 0 (Ω) due to the fact that u(y)

H 1 0 → ∞ as y → 0.
Remark 2.3. More precisely, when some y j tend to zero, u(y) converges to the solution of the so-called soft inclusions problem (see [START_REF] Jikov | Homogeneization of differential operators and integral functionals[END_REF], chapter 3), outside the corresponding subdomains Ω j . Here, due to the fact that the approximation estimates that we prove further are in relative error, these other limit solutions are of no use in our analysis.

A compactness result

As already observed in the introduction, the manifold M is not bounded in H 1 0 (Ω) due to the homogeneity property (1.13) and therefore not compact.

In order to treat this defect, we consider

Y := [1, ∞] d ,
and the submanifold

B := {u(y) : y ∈ Y },
which is now bounded in H 1 0 (Ω), from the standard a-priori estimate

u(y) H 1 0 C f min y j C f ,
that is obtained by taking v = u(y) in the variational formulation (1.12), with [START_REF] Beck | Implementation of optimal Galerkin and collocation approximations of PDEs with random coefficients[END_REF]. This estimate trivially extends to u S (y S c ) when the y j have infinite value for j ∈ S. In addition we have the following result.

C f = f H -1 as in (1.
Theorem 2.4.

The set B is compact in H 1 0 (Ω).
Proof. Consider any sequence of vectors y n = (y n 1 , . . . , y n d ) ∈ Y for n 1. We need to prove that the corresponding sequence of solutions (u(y n )) n 1 admits a converging subsequence. For this purpose, we observe that there exists a subset S ∈ {1, . . . , d} such that, up to subsequence extraction,

lim n→∞ y n j = ∞, j ∈ S,
and lim

n→∞ y n j = y j < ∞, j ∈ S c .
Note that S could be empty, for instance in the case where the y n j are uniformly bounded for all j.

Let ε > 0. Using the strong convergence result in Lemma 2.1, for all n 1 there exists an auxiliary vector ȳn such that ȳn j = y n j when y n j < ∞, ȳn j < ∞ when y n j = ∞, such that by having picked ȳn j large enough in the second case

u(y n ) -u(ȳ n ) H 1 0 ε/3.
In addition we may assume that ȳn j → ∞ for j ∈ S. Next we introduce the vector ỹn such that ỹn j = ȳn j when j ∈ S and ỹn j = y j when j ∈ S c . Applying again Lemma 2.1, we find that with y S c = (y j ) j∈S c , one has

u(ỹ n ) -u S (y S c ) H 1 0 ε/3,
for n sufficiently large. Finally we argue that

u(ỹ n ) -u(ȳ n ) H 1 0 ε/3,
for n large enough. This is a consequence of the following variant of Strang first lemma (which proof is similar and left as an exercise to the reader) that says that for two diffusion functions ā and ã, the corresponding solution ū and ũ with the same data f satisfy

ū -ũ H 1 0 C f ā -ã L ∞ min{ā min , ãmin } 2 .
We then apply this to a := a n = a(y n ) and ã := ãn = a(ỹ n ), observing that from their definition, ā -ã

L ∞ = max j∈S c |ȳ n j -y j | → 0 as n → ∞. Therefore u(y n ) -u S (y S c ) H 1 0
ε for n sufficiently large, which concludes the proof.

We next observe that any y ∈ Y can be rewritten as y = tỹ, with ỹ ∈ Y and normalization min ỹj = 1, for some t > 0, and from (1.13) one has u(y) = t -1 u(ỹ). This motivates the study of the further reduced manifold

N := {u(y) : y ∈ Y , min y j = 1}, (2.22)
which is a subset of B.

One important observation is that the solutions contained in N are also uniformly bounded from below, under mild assumptions on the data f . Lemma 2.5. The set N is compact in H 1 0 (Ω). Moreover, one has the framing min

1 j d f H -1 (Ωj ) u(y) H 1 0 C f , (2.23)
for all u(y) ∈ N .

Proof. The compactness of N follows from that of B, since N is a closed subset of B. For the framing, as a(y) 1 on Ω,

u 2 H 1 0 j∈S c y j ˆΩj |∇u(y)| 2 dx = f, u(y) H -1 ,H 1 0 C f u(y) H 1 0 , so u(y) H 1 0 C f . Now take j ∈ {1, . . . , d} such that y j = 1, and consider φ ∈ H 1 0 (Ω j ). Then f, φ H -1 ,H 1 0 = ˆΩj ∇u(y) • ∇φ dx u(y) H 1 0 (Ω) φ H 1 0 (Ωj ) ,
which gives the result.

In the sequel of this paper, we always work under the condition that the lower bound in (2.23) is strictly positive

c f := min 1 j d f H -1 (Ωj ) > 0.
(2.24)

Let us observe that when f is a function in L 2 (Ω), this is ensured as soon as f is not identically zero on one of the Ω j . We thus have

0 < c f u(y) H 1 0 C f , (2.25)
for all u(y) ∈ N .

Remark 2.6. The condition c f > 0 is in general necessary for controlling u(y) H 1 0 from below. Indeed assume f H -1 (Ωj ) = 0 for some j such that Ω \ Ω j is connected. Then taking y k = ∞ for k = j and y j = 1, we find that u(y) ∈ V S with S = {j} c , which is equivalent to u(y) ∈ H 1 0 (Ω j ) since it vanishes on the other sub-domains. As f H -1 (Ωj ) = 0, we obtain u(y) = 0.

Remark 2.7. One also has the uniform framing in the • y norm since

0 < c f u(y) H 1 0 u(y) y = f, u H -1 ,H 1 0 C f , (2.26)
for all u(y) ∈ N when all y j are finite.

The framing (2.25) has an implication on the existence of reduced model spaces that approximate uniformly well all solutions u(y) ∈ M in relative error.

Theorem 2.8. There exists a sequence of linear spaces

(V n ) n 1 such that dim(V n ) = n, and a sequence (ε n ) n 1 that converges to zero such that u(y) -P Vn u(y) H 1 0 ε n u(y) H 1 0 (2.27)
for all y ∈ Y , where P Vn is the H 1 0 (Ω)-orthogonal projector onto V n . Proof. Since N is compact, there exists a sequence of spaces (V n ) n 1 with dim(V n ) = n and a sequence (σ n ) n 1 that tends to 0, such that

v -P Vn v H 1 0 σ n , v ∈ N .
Now let y ∈ Y differing from (∞, . . . , ∞), for which there is nothing to prove since u(∞, . . . , ∞) = 0, and let t -1 = min 1 j d y j < ∞. By homogeneity, t -1 u(y) = u(ty) ∈ N , and therefore

u(y) -P Vn u(y) H 1 0 = t u(ty) -P Vn u(ty) H 1 0 (Ω)
tσ n .

On the other hand, u(y)

H 1 0 (Ω) = t u(ty) H 1 0 (Ω)
tc f by framing (2.23), which proves Theorem 2.8 with ε n = σ n /c f . The above theorem tells us that we can achieve contrast-independent approximation in relative error. It is however still unsatisfactory from two perspectives:

1. It does not describe the rate of decay of ε n as the reduced dimension n grows. In practice, one would like to construct reduced spaces V n such that this decay is fast, similar to the exponential decay obtained under UEA. 2. The approximation property is expressed in terms of the orthogonal projection P Vn . In applications to forward modeling, we approximate the solution u(y) in the space V n by the Galerkin projection P y Vn u(y). We thus wish for uniform estimates also for such approximations.

z 1 z 2 0 1 1 1 2 1 2 1 2 L 1 2 L R -1 11 R -1 12 R -1 21 R -1 22 . . . R -1 1L ... . . . . . . . . .
These two problems are treated in §3 and §4 respectively.

Approximation rates

Our construction of efficient reduced model spaces is based on a certain partitioning of the parameter domain Y associated to the manifold B. To any = ( 1 , . . . , d ) ∈ N d 0 we associate the dyadic rectangle

R = [2 1 , 2 1+1 ] × • • • × [2 d , 2 d +1 ], (3.28)
For a positive integer L to be fixed further, we modify the definition of R by replacing the interval [2 j , 2 j +1 ] by [2 j , ∞] when j = L for some j. This leads to the partition

Y = ∈{0,...,L} d R . (3.29)
This partition is best visualized in the inverse parameter domain by setting

z = (z 1 , . . . , z d ) := (y -1 1 , . . . , y -1 d ) ∈ [0, 1] d . (3.30)
Then, the inverse rectangles R -1 split the unit cube, as shown on Figure 1.

In particular, the rectangles touching the axes correspond to rectangles R of infinite size.

We build reduced model spaces through a piecewise polynomial approximation over this partition. In other words, for each ∈ {0, . . . , L} d , we use different polynomials

u ,k (y) = |ν| k u ,ν y ν ,
of total degree k for approximating u(y) when y ∈ R , leading to a family of local reduced model spaces

V ,k = span{u ,ν : |ν| k}, (3.31)
that can be either used individually when approximating u(y) if the rectangle R containing y is known, or summed up in order to obtain a global reduced model space.

In this section we show that this construction yields exponential convergence rates in (1.15), similar to those obtained under a Uniform Ellipticity Assumption. This requires a proper tuning between the total polynomial degree k and the integer L that determines the size of the partition. In the study of local polynomial approximation, we treat separately the inner rectangles for which ∈ {0, • • • , L -1} d and the infinite rectangles for which one or several j are equal to L. The estimates obtained in the latter case rely on the additional assumption that the partition has a geometry of disjoint inclusions.

Polynomial approximation on inner rectangles

Inner rectangles R are particular cases of rectangles of the form

R = [a 1 , 2a 1 ] × • • • × [a d , 2a d ], (3.32)
for some a j 1. The following lemma, adapted from [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF], shows that one can approximate the parameter to solution map in the • y and • H 1 0 norms on such rectangles, with a rate that decreases exponentially in the total polynomial degree.

Lemma 3.1. Let R be any rectangle of the form (3.32). Then, for each k 0, there exists functions

u ν ∈ H 1 0 (Ω) such that u(y) - |ν| k u ν y ν y C3 -k , y ∈ R, (3.33)
where

C := 1 √ 3 C f , and
u(y) - |ν| k u ν y ν H 1 0 C3 -k , y ∈ R, (3.34)
where

C := 1 √ 6 C f .
Proof. The exponential rate is established in [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF] for a single parameter domain with uniform ellipticity assumption. Here the difficulty lies in the fact that we want the same estimate for all parametric rectangles R and thus without control on the uniform ellipticity. Still the technique of proof, based on power series, is similar.

The elliptic equation -div(a(y)u(y)) = f may be written in operator form

A y u(y) = f,
where the invertible operator A y :

H 1 0 (Ω) → H -1 (Ω) is defined by A y v, w H -1 ,H 1 0 := ˆa(y)∇v • ∇w dx = v, w y .
We introduce

y := 3 2 (a 1 , . . . , a d ),
the center of the rectangle, and write any y ∈ R as

y = y + ỹ,
where the components ỹj of ỹ vary in [-a j /2, a j /2]. We may write A y = A y + d j=1 ỹj A j , where the operators A j : H 1 0 (Ω) → H -1 (Ω) are defined by

A j v, w H -1 ,H 1 0 := ˆΩj ∇v • ∇w dx.
This allows us to rewrite the equation as

(I + B(ỹ))u(y) = g, where g := A -1 y f ∈ H 1 0 (Ω) and B(ỹ) = d j=1 ỹj A -1 y A j acts in H 1 0 (Ω).
We then observe that

B(ỹ)v, w y = A y B(ỹ)v, w H -1 ,H 1 0 = d j=1 ỹj A j v, w H -1 ,H 1 0 = d j=1 ỹj ˆΩj ∇v•∇w dx,
and therefore, since

|ỹ j | 1 3 y j , | B(ỹ)v, w y | 1 3 d j=1 y j ˆΩj ∇v • ∇w dx 1 3 v y w y ,
which shows that B(ỹ) y→y 1 3 . We may thus approximate (I + B(ỹ)) -1 by the partial Neumann series

k l=0 (-1) l B(ỹ) l ,
which is a polynomial in ỹ of total degree k. The corresponding polynomial approximation to u(y) is given by

N k u(y) = k l=0 (-1) l B(ỹ) l g = k l=0 (-1) l   d j=1 ỹj A -1 y A j   l g = |ν| k v ν ỹν ,
and coincides with the truncated power series of ũ(ỹ) := u(y + ỹ) at ỹ = 0, that is,

v ν := 1 ν! ∂ ν u(y), ν! := ν j !.
It can be rewritten in the form

N k u(y) = |ν| k u ν y ν .
One has

u(y) -N k u(y) y l>k B(ỹ) l g y l>k 3 -l A -1 y f y = 3 -k 2 A -1 y f y , and
A -1 y f 2 y = A y A -1 y f, A -1 y f H -1 ,H 1 0 = f, u(y) H -1 ,H 1 0 C f u(y) H 1 0 C 2 f ,
where the last inequality follows from Lax-Milgram estimate since a(y) 1. This proves the estimate

u(y) - |ν| k u ν y ν y C3 -k , y ∈ R, (3.35)
with C := 1 2 C f . Using the inequalities

v 2 y 4 3 v 2 y , v ∈ H 1 0 (Ω), y ∈ R, and v 2 H 1 0 2 3 v 2 y , v ∈ H 1 0 (Ω),
we obtain the estimate (3.33) and (3.34) with the modified multiplicative constants.

Remark 3.2. The above lemma shows that the set M R := {u(y) : y ∈ R} can be approximated with accuracy C3 -k by the space

V R := span{u ν : |ν| k}. (3.36)
The dimension of V R is at most k+d d , however, as noticed in [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF], it can in fact be seen that

dim(V R ) k + d -1 d -1 . ( 3

.37)

This stems from the fact that the operators defined in the above proof satisfy the dependency relation

A y = d j=1 y j A j ,
and therefore, one can rewrite A y as

A y := (1 + ỹd /y d )A y + d-1 j=1 (ỹ j -ỹd y j /y d )A j .
Using this form, the partial Neumann sum N k u(y) has at most k+d-1 d-1

independent terms.

We shall also make use of the following adaptation of the above lemma to the approximation of the limit solution map y S c → u S (y S c ), defined by (2.21). Its proof is an immediate adaptation of the previous one and is therefore omitted. Lemma 3.3. Let S ⊂ {1, . . . , d}, and for some a j 1, let R be a rectangle of the form

R = j∈S c [a j , 2a j ]. (3.38)
Then, there exists functions u ν ∈ V S such that u S (y S c ) -

|ν| k u ν y ν S c y S c C3 -k , y S c ∈ R, (3.39)
where C := 1 √ 3 C f , and

u S (y S c ) - |ν| k u ν y S c H 1 0 C3 -k , y S c ∈ R, (3.40)
where

C := 1 √ 6 C f .

Polynomial approximation on infinite rectangles

We now consider the infinite rectangles R , corresponding to the such that some of the j equal L. We define

S := {j : j = L}, (3.41)
the set of such indices. When y ∈ R , we thus have

y j 2 L , j ∈ S,
and so u(y) should be close to u S (y S c ) as L is large. On the other hand y S c belongs to a rectangle of the form

R S c = j∈S c [2 j , 2 j +1 ].
Therefore, by Lemma 3.3, we can approximate u S (y S c ) by a polynomial of total degree k in these restricted variables.

In order to conclude that this polynomial is a good approximation to u(y) on R , we need a quantitative estimate on the convergence of u(y) towards u S (y S c ). Let us observe that since

d j=1 y j ˆΩj ∇u(y)•∇v dx = f, v H -1 ,H 1 0 = j∈S c y j ˆΩj ∇u S (y S c )•∇v dx, v ∈ V S ,
the function u S (y S c ) coincides with the orthogonal projection of u(y) onto V S for the y-norm, as well as for the y S c -norm:

u S (y S c ) = P y V S u(y) = P y S c
V S u(y).

(3.42)

In addition, with

Ω S := j∈S Ω j , (3.43)
we have

2 L ∇u(y) 2 L 2 (Ω S ) j∈S y j ˆΩj |∇u(y)| 2 dx f, u(y) H -1 ,H 1 0 C 2 f , since u(y) H 1 0
C f , and therefore, since ∇u S (y S c ) = 0 on Ω S , we find that ∇u(y) -∇u S (y

S c ) L 2 (Ω S ) C f 2 -L/2 . (3.44)
Our objective is to obtain a similar error bound on the remaining domains Ω j for j ∈ S c . This turns out to be feasible, with an even better rate 2 -L , when making certain geometric assumptions on the partition of the domain Ω.

Definition 3.4. We say that {Ω 1 , . . . , Ω d } is a Lipschitz partition if and only if for any subset T ⊂ {1, . . . , d}, the domain Ω T = j∈T Ω j has Lipschitz boundaries. Note that such a property is stronger than just saying that each domain is Lipschitz, see Figure 2 (right) for a counter-example. In a Lipschitz partition, all subdomains Ω j are Lipschitz, and the common boundary between two subdomains is either empty or a (n-1)-dimensional surface, as illustrated on Figure 2 (left). In particular, it is easily checked that partitions consisting of a background domain and well separated subdomains that have Lipschitz boundaries fall in this category. Similar to the Ω T , the individual Ω j could have several connected components, that should then be well separated. Here by "well separated", we mean that δ-neighbourhoods of the subdomains remain disjoints for some δ > 0.

Ω 1 Ω 4 Ω 2 Ω 3 Ω 1 Ω 2 Ω 3 Ω 4
For the inner domains Ω T such that ∂Ω T ∩ ∂Ω = ∅, the classical Stein's extension theorem [START_REF] Stein | Singular integrals and differentiability properties of functions[END_REF] guarantees the existence of continuous extension operators

E T : H 1 (Ω T ) → H 1 (Ω), that satisfy (E T v) |Ω T = v for all v ∈ H 1 (Ω T )
. We refer to chapter 5 of [START_REF] Adam | Sobolev spaces[END_REF] for a relatively simple construction of the extension operator E j by local reflection after using a partitioning of unity along the boundary of Ω T and local transformations mapping the boundary to the hyperplane R n-1 .

For the domains Ω T touching the boundary ∂Ω, these operators are modified in order to take into account the homogeneous boundary condition, and we refer to [START_REF] Zenisek | extensions from the Sobolev spaces H 1 satisfying prescribed Dirichlet boundary conditions[END_REF] for such adaptations. Here, the relevant space is

H1 (Ω T ) := R T (H 1 0 (Ω)), (3.45)
where R T is the restriction to Ω T , over which v → ∇v L 2 (Ω T ) is equivalent to the H 1 norm by Poincaré inequality. Then, there exists a continuous extension operator E T : H1 (Ω T ) → H 1 0 (Ω). Note that the norm of all these operators depends on the geometry of the partition. These operators are instrumental in proving the following convergence estimate. Lemma 3.5. Assume that {Ω 1 , . . . , Ω d } is a Lipschitz partition of Ω. Then there exists a constant C 0 that only depends on the geometry of the partition such that for any S ⊂ {1, . . . , d} and y = (y S , y S c ) ∈ Y , one has

u(y) -u S (y S c ) H 1 0 C 0 C f max j∈S y -1 j . (3.46)
In particular, for the infinite rectangle R ,

u(y) -u S (y S c ) H 1 0 C 0 C f 2 -L , y ∈ R , (3.47)
with S defined by (3.41).

Proof. We first note that it suffices to prove (3.46) in the particular case where the largest y j are those for which j ∈ S. Indeed, if this is not the case, we use the decomposition

u(y) -u S (y S c ) = (u(y) -u S (y S c )) -(u(y ) -u S (y S c )) + (u(y ) -u S (y S c )),
with S = {i : y i min j∈S y j } and y defined by y j = max i=1,...,d y i if j ∈ S, y j = y j otherwise, so that each term falls in this particular case and will be bounded in H 1 0 norm by C 0 C f max j∈S y -1 j . This leads to the same estimate (3.46) up to a factor 3 in constant C 0 . In addition, up to reordering the subdomains Ω j , we may assume y 1 . . . y d and therefore S = {1, . . . , |S|}.

Fix j |S|, and denote u = u(y) and u S = u S (y S c ) for simplicity. We define the Lipschitz domain

Ω j = Ω 1 ∪ • • • ∪ Ω j , remarking that Ω S = j∈S Ω j = Ω |S| .
Poincaré's inequality ensures that there exists a function c on Ω j , constant on any connected component of Ω j , and null on ∂Ω ∩ Ω j , such that

u -u S -c H 1 (Ω j ) C P ∇(u -u S ) L 2 (Ω j ) ,
with C P the maximal Poincaré constant of all unions of subdomains from the partition. Moreover, there is an extension

v ∈ H 1 0 (Ω) of u -u S -c ∈ H1 (Ω j ) such that v H 1 0 (Ω) C E u -u S -c H 1 (Ω j ) C E C P ∇(u -u S ) L 2 (Ω j ) ,
with C E the maximal norm of all extension operators E T , T ⊂ {1, . . . , d}.

As u -u S -v = c on Ω S ⊂ Ω j , the function u -u S -v is in V S , and therefore orthogonal to u -u S = u -P y V S u for the • y norm:

0 = u -u S , u -u S -v y = d i=1 y i ˆΩi |∇(u -u S )| 2 - d i=1 y i ˆΩi ∇(u -u S ) • ∇v = i>j y i ˆΩi |∇(u -u S )| 2 - i>j y i ˆΩi ∇(u -u S ) • ∇v since ∇v = ∇(u -u S ) on Ω j .
In particular, we obtain

y j+1 ∇(u -u S ) 2 L 2 (Ωj+1) i>j y i ˆΩi |∇(u -u S )| 2 y j+1 ˆΩ\Ω j |∇(u -u S ) • ∇v| y j+1 u -u S H 1 0 (Ω) v H 1 0 (Ω) y j+1 u -u S H 1 0 (Ω) C P C E ∇(u -u S ) L 2 (Ω j )
, and therefore

∇(u -u S ) 2 L 2 (Ω j+1 ) (1 + C P C E ) ∇(u -u S ) L 2 (Ω) ∇(u -u S ) L 2 (Ω j ) .
Applying this inequality inductively for j = d -1, . . . , d -k, we get

∇(u -u S ) L 2 (Ω) (1 + C P C E ) 2 k -1 ∇(u -u S ) L 2 (Ω d-k ) ,
for any k = 1, . . . , d -|S|. For k = d -|S|, this results in the bound

∇(u -u S ) 2 L 2 (Ω) C 0 ∇(u -u S ) 2 L 2 (Ω S ) = C 0 ∇u 2 L 2 (Ω S ) , (3.48)
for any non-empty S, with

C 0 = (1 + C P C E ) 2 d-1 .
We now write (min

i∈S y i ) ∇(u -u S ) 2 L 2 (Ω S ) u -u S 2 y = u, u -2u S y + u S , u S y S c = f, u -u S H -1 ,H 1 0 C f ∇(u -u S ) L 2 (Ω) ,
which, combined to the previous estimate, gives

u -u S H 1 0 = ∇(u -u S ) L 2 (Ω) C 0 C f max i∈S y -1 i ,
therefore proving (3.46). For (3.47), we simply notice that max j∈S y -1 j 2 -L for y ∈ Y ∩ R , and use a continuity argument when y takes infinite values.

Combining the estimate (3.47) from the above lemma with (3.40) from Lemma 3.3, we obtain the following estimate for polynomial approximation on an infinite rectangle R :

u(y) - |ν| k u ν y ν S c H 1 0 C f √ 6 3 -k + C 0 C f 2 -L , y ∈ R , (3.49)
where C 0 is the constant in (3.47). This estimate hints how the level L in the partition should be tuned to the total polynomial degree k, so that the two contributions in the above estimate are of the same order.

Remark 3.6. Note that the constant C 0 = (1 + C P C E ) 2 d-1 becomes prohibitive even for moderate values of d. However, under more restrictive geometric assumptions, for instance if the subdomains Ω 2 , . . . , Ω d are disjoint inclusions in a background Ω 1 , better bounds can be obtained, with a constant C 0 that does not suffer a similar curse of dimensionality, by replacing the induction in the proof by a two-step procedure, consisting of extensions first from the high-diffusivity inclusions to the background, and then to the whole domain Ω.

Approximation rates and n-widths

We are now in position to establish an approximation result for the reduced model spaces. For this purpose, we fix the smallest level L = L k 1 such that

C 0 C f 2 -L C f √ 3 3 -k . 20
In particular L scales linearly with k, with the bound αk + β L k αk + γ, where

α := ln 3 ln 2 , β := ln( √ 3C 0 ) ln 2 , γ := ln(2 √ 3C 0 ) ln 2 . (3.50)
Then, the polynomial approximation estimates (3.34) and (3.49) show that for each

∈ {0, • • • , L k } d , there exist functions u ,ν ∈ H 1 0 (Ω) such that u(y) - |ν| k u ,ν y ν H 1 0 C f √ 6 + C f √ 3 3 -k C f 3 -k , y ∈ R .
Note that in the case of an infinite rectangle R , the u ,ν are non trivial only for monomials of the form y ν S c and they belong to V S , where S := {j : j = L k }. Thus the solutions u(y) for y ∈ R are approximated with accuracy

C f 3 -k in the space V ,k := span{u ,ν : |ν| k},
which in view of Remark 3.2 has dimension at most k+d-1 d-1 . Note also that approximating the reduced manifold N defined in (2.22) requires a smaller subset of rectangles, since

{y ∈ Y : min y j = 1} ⊂ ∈E k R , E k := {0, • • • , L k } d \ {1, • • • , L k } d .
We thus introduce the reduced model space

V n := ∈E k V ,k , n = dim(V n ) #(E k ) k + d -1 d -1 , (3.51)
and find that u(y) -P Vn u(y)

H 1 0 C f 3 -k , (3.52)
for all y ∈ Y such that min y j = 1. In view of (3.50), there exists a constant C that depends on d and C 0 , such that

n ((L k + 1) d -L d k ) k + d -1 d -1 C(k + 1) 2d-2 . (3.53)
This leads to the following approximation theorem.

Theorem 3.7. Assume that the partition has the geometry of disjoint inclusions. The reduced basis space V n defined in (3.51) then satisfies

u(y) -P Vn u(y) H 1 0 C exp -cn 1 2d-2 , (3.54)
for all y ∈ Y = [1, ∞] d such that min y j = 1. The Kolmogorov n-width (1.2) of the reduced manifold N satisfies

d n (N ) H 1 0 C exp -cn 1 2d-2 .
(3.55)

Over the full manifold M, one has the estimate in relative error

u(y) -P Vn u(y) H 1 0 C exp -cn 1 2d-2 u(y) H 1 0 , (3.56)
for all y ∈ Y =]0, ∞] d . The positive constants c and C only depend on d, C f , and on the geometry of the partition through the constant C 0 .

Proof. The estimate (3.54) follows directly by combining (3.52) and (3.53), and (3.55) is an immediate consequence. We then derive (3.56) by using the homogeneity property (1.13) and the lower inequality in (2.25), similar to the proof of (2.27) in Theorem 2.8.

Remark 3.8. In the above construction of V n , the dimension n only takes the values

n k := #(E k ) k+d-1 d-1
for k 0. However it is easily seen that if we set V n = V n k for n k n < n k+1 , then all the estimates in the above theorem remain valid up to a change in the constants (c, C). Remark 3.9. Note that the union of the V ,k for ∈ E k would suffice to approximate N with uniform accuracy C f 3 -k , their sum V n is an overkill. When y is known, for example in forward modeling, it is therefore possible to first identify the proper space V ,k associated to the rectangle R that contains y, and build the approximation to u(y) from this space. This nonlinear reduced modeling strategy has been studied in [START_REF] Bonito | Nonlinear methods for model reduction[END_REF] with similar local polynomial approximation under UEA, and in [START_REF] Patera | An "hp" certified reduced basis method for parametrized elliptic partial differential equations[END_REF][START_REF] Maday | Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces[END_REF][START_REF] Kouri | An adaptive local reduced basis method for solving pdes with uncertain inputs and evaluating risk[END_REF] with local reduced basis. The natural benchmark is given by the notion of library width introduced in [START_REF] Temlyakov | Nonlinear Kolmogorov widths[END_REF], that is defined for any compact set K in a Banach space V as where the first infimum is taken over all libraries L n of n-dimensional spaces with cardinality at most N . Our results thus show that

d n,N (N ) H 1 0 C f 3 -k ∼ C exp(-cn 1 d ), n := k + d -1 d -1 , N = (L k +1) d -L d k .
Note that the above sub-exponential rate can be misleading due to fact that the constant c has a hidden dependence in d. As an example, up to the constant C f , we find that taking k = 4, 7, 9 leads to error bounds 3 -k of order 10 -2 , 10 -3 , 10 Remark 3.10. In view of the results from [START_REF] Binev | Convergence rates for greedy algorithms in reduced basis methods[END_REF] and [START_REF] Devore | Greedy algorithms for reduced bases in Banach spaces[END_REF], we are ensured that a proper selection of reduced basis elements in the manifold N should generate spaces V n that perform at least with the same exponential rates as those achieved by the spaces V n in Theorem 3.7. As explained in the introduction, reduced basis spaces may perform significantly better than reduced model spaces based on polynomial or piecewise polynomial approximation. This occurs in particular when the polynomial coefficients have certain linear dependency, as established in [START_REF] Bachmayr | Kolmogorov widths and low-rank approximations of parametric elliptic PDEs[END_REF] for the elliptic problem with piecewise constant coefficients in the low contrast regime, and recalled in Remark 3.2. There, it is shown that the rate O(exp(-cn

1 d
)) is at least improved to O(exp(-cn

1 d-1
)) and that further improvements in the rate may result from certain symmetry properties of the domain partition, however not circumventing the curse of dimensionality. While we do not pursue this analysis in the present high contrast setting, we expect similar results to hold.

Forward modeling and inverse problems 4.1 Galerkin projection

In the context of forward modeling, the reduced model space V n is used to approximate the parameter to solution map, by a map

y → u n (y) ∈ V n , computed through the Galerkin method: u n (y) ∈ V n is such that d j=1 y j ˆΩj ∇u n (y) • ∇v dx = f, v H -1 ,H 1 0 , v ∈ V n .
Therefore u n (y), v y = u(y), v y , that is u n (y) = P y Vn u(y),

where P y Vn is the projection onto V n with respect to norm • y . Hence, one would like to derive estimates on u(y) -P y Vn u(y) H 1 0 in place of the estimates on u(y)-P Vn u(y) H 1 0 that we have obtained so far, since P Vn u(y) is not practically accessible. As explained in the introduction, we cannot be satisfied with combining the latter estimates with the bound u(y) -P y Vn u(y) H 1 0 κ(y) 1/2 u(y) -P Vn u(y) H 1 0 derived from Cea's lemma, since the multiplicative constant κ(y) from (1.9) is not uniformly bounded over the manifolds M, B or N . Here, we shall employ another approach to derive the same rates of convergence for u(y) -P y Vn u(y) H 1 0 . One first observation is that in order for Galerkin projection P y Vn onto a reduced model space V n to satisfy a convergence bound in relative error, it is critical that this space contains some functions from the limit spaces V S . This is expressed by the following result. Proof. Since V n ∩ V S = {0}, the quantity ∇v L 2 (Ω S ) is a norm on V n and one can define

α = min v∈Vn ∇v L 2 (Ω S ) v H 1 0 > 0.
For any ε > 0, take y j = ε -2 for j ∈ S and y j = 1 for j ∈ S c . Then, for v = P y Vn u(y),

α ε v H 1 0 1 ε ∇v L 2 (Ω S ) v y u(y) y C f C f c f u(y) H 1 0 ,
where we have used the framings (2.25) and (2.26). Therefore, taking ε =

c f C f α(1 -C) implies v H 1 0
(1 -C) u(y) H 1 0 , and (4.58) follows. However, in the construction of V n in §3, each space V ,k is a subset of V S for S = {j : j = L k }. This prevents the phenomenon described in the previous proposition from occurring. Instead, we obtain similar convergence bounds as those obtained for P Vn , as expressed in the following result. Theorem 4.2. Assume that the partition of Ω has the geometry of disjoint inclusions. On the rectangles R for ∈ {0, . . . , L} d , the following uniform convergence estimates hold:

u(y) -P y V ,k u(y) H 1 0 C f √ 3 3 -k , y ∈ R , (4.59)
if ∞ < L, and for all y ∈ Y such that min y j = 1, and

u(y) -P y V ,k u(y) H 1 0 C f √ 3 3 -k + C 0 C f 2 -L , y ∈ R , ( 4
u(y) -P y V ,k u(y) H 1 0 C exp -cn 1/(2d-2) u(y) H 1 0 , (4.62)
for all y ∈ Y , with constants c and C that only depend on d, C f , and on the geometry of the partition through the constant C 0 .

Proof. For bounded rectangles R with ∞ < L, we know from Lemma 3.1, and more precisely from (3.33), that u(y) -P y V ,k u(y) y = min

v∈V ,k u(y) -v y u(y) - |ν| k u ν y ν y C f √ 3 3 -k
This is a quadratic problem when a(y) has an affine dependence in y, that can be solved by standard quadratic optimization methods. The rationale for this approach is the fact that

R(y) = A y u * -A y u(y) H -1 ∼ u * -u(y) H 1 0
, and therefore we should be close to finding the parameter y that best explains the approximation u * . Unfortunately, this approach is not much viable in the high-contrast regime since the equivalence A y v H -1 ∼ v H 1 0 has constants that are not uniform in y and deteriorate with the level of contrast.

Instead, we propose a more specific approach that exploits the piecewise constant structure of a(y), assuming that V n is a reduced space of the form

V n = span(u 1 , . . . , u n ), u i = u(y i ),
for some properly selected parameter vectors

y i = (y i 1 , . . . , y i d ), i = 1, . . . , n.
As mentioned, see Remark (3.10), these spaces satisfy the same exponential convergence bounds as the spaces constructed in §3.

The PBDW estimator v * = v * (w) ∈ V n thus has the form

v * = n i=1 c i u i ∈ V n
and satisfies a similar bound (4.67) as in the above proposition. Then, on the particular domain Ω j , one has

f y j = -∆u |Ωj ≈ - n i=1 c i ∆u i = n i=1 c i f y i j ,
and therefore, a natural candidate for the parameter estimate is y * = (y * 1 , . . . , y * d ) with

y * j := n i=1 c i y i j -1 . ( 4

.68)

The following result gives a recovery bound in relative error for the inverse diffusivity.

Proposition 4.5. With the notation 1/y = (1/y 1 , . . . , 1/y d ), the estimator y * defined by (4.68) satisfies the bound

1 y * - 1 y ∞ C f c f Cµ n exp -cn 1 2d-2 1 y ∞ , (4.69)
where C f and c f are as in (2.25), and the other constants as in (4.67). 3.5. Therefore we consider sub-partitions that comply to the assumptions, such as illustrated on Figure 3, which amounts to equate the parameters y j of squares belonging to the same sub-domain. This way we can consider that y = (y A , y B , y C , y D ) consists of four parameters, one per each subdomain.

Ω D Ω C Ω B Ω A Figure 3: Lipschitz partition of Ω. Ω A Ω A Ω A Ω A Ω B Ω B Ω B Ω B Ω C Ω C Ω C Ω C Ω D Ω D Ω D Ω D
The numerical results that we next present aim to illustrate the robustness to high-contrast of the reduced basis method, and discuss in addition the effect of parameter selection, higher parametric dimensions, and inclusions that are not satisfying the geometric assumption as exemplified on Figure 4.

We construct different reduced bases {u 1 , . . . , u n } of moderate dimension 1 n 15, where u k = u(y k ), for certain parameter selections y 1 , . . . , y n . Each reduced basis element u k is numerically computed by the Galerkin method in a background finite element space V h of dimension 6241.

The reduced basis spaces are thus subspaces of V h , thus strictly speaking spaces V n,h depending on n and on the meshsize h. In our numerical computation, we always assess the error

P y V h u(y) -P y V n,h u(y).
We noticed that for the considered values of n = 1, . . . , 15 the error curves do not vary much when further reducing the mesh size h. In fact they are already essentially the same when the dimension of V h is four times smaller. Therefore, for simplicity of the presentation, we still write u(y) -P y Vn u(y), bearing in mind that the additional finite element error u(y) -P y V h u(y) depends on h (with algebraic decay in the finite element dimension).

All the tests were done using Python 3.8. For more information and experiments not presented here we invite the reader to look into the github repository https://github.com/agussomacal/ROMHighContrast.

• Greedy H 1 0 : The y k are picked incrementally, y k+1 maximizing the relative H 1 0 projection error u(y) -P V k u(y) H 1 0 / u(y) H 1 0 . • Greedy Galerkin: The y k are picked incrementally, y k+1 maximizing the relative H 1 0 error of the Galerkin projection u(y)-P y V k u(y) H 1 0 / u(y) H 1 0 . Figure 5 for the same parameter selection strategies. Here, we notice that the inclusion of the limit solution u ∞ is not anymore critical for reaching good accuracy. Nevertheless, these errors still decay faster for the greedy strategies.

Remark 5.1. As the diffusion coefficient is piecewise constant on the partition Ω A ∪Ω c A , the parameter space dimension is d = 2 in this numerical example. The theoretical results thus provide a bound on the error of order exp(-c √ n). However, this bound is obtained with local reduced spaces V ,k on dyadic intervals, which does not perform as well as V n = ∈E k V ,k , for which one might expect a rate closer to exp(-cn). In Figure 5 for n 11, that is, until numerical precision issues arise, we even observe a faster than exponential convergence, that could be due to the superiority of reduced bases over polynomial approximations. Remark 5.2. It is well known that the reduced basis can be very ill-conditioned, since u n becomes extremely close to V n-1 = span{u 1 , . . . , u n-1 } as n gets moderately large. In order to avoid numerical instabilities, prior to the computation of the Galerkin or H 1 0 projection onto V n , we need to perform a change of basis, typically by some orthonormalization process. In our numerical test, we perform this orthonormalization with respect to the discrete 2 inner product for the nodal values in the background finite element representation, using the QR decomposition, and obtain a satisfactory stable numerical behavior. However, this process is not invariant under permutations, and we observe that it behaves better in terms of numerical stability when sorting the reduced basis elements from higher contrast to lower contrast.

In this one parameter scenario, both greedy strategies behaved equally well. However, as we increase the dimensionality of the problem d > 1, Greedy Galerkin appears to be the best selection procedure, as could be expected since it optimizes the error based on the approximation which is effectively computed in forward modeling. Figure 6 shows this effect when d = 2, where y A and y B are allowed to vary independently while y C and y D are taken as background always equal to 1.

Influence of dimensionality and geometry

In order to study the impact of dimensionality on the approximation rates, we compare the behavior of the Greedy Galerkin selection method, as we increase the number of freely varying parameters. As before, we will have for y = (y A , 1, 1, 1) when d = 1, then y = (y A , y B , 1, 1) when d = 2, until having all four subdomains freely varying between 1 and +∞.

In Figure 7 the degradation with respect to dimension is clearly observed as the approximation capabilities strongly decrease. Even thought the exponential decay rate is still conserved, the decay parameter shrinks from almost 3 down to 0.22 when d = 4.

Secondly, we study the case where the geometrical assumptions are not satisfied. We follow the same incremental subdomains unfreezing as in the previous case but using the geometry stated in Figure 4. We observe that the reduced basis approach still achieves exponential approximation rates, actually higher than in the previous example. This hints that the geometric assumptions which are needed in our proofs could be artificial, and leaves open the question of achieving such results without relying on these assumptions.

Figure 1 :

 1 Figure 1: Partition of [0, 1] d by the inverse rectangles R -1 in the case d = 2.

Figure 2 :

 2 Figure 2: A Lipschitz partition of Ω (left) and a counter-example (right) since Ω 1 ∪ Ω 4 is not Lipschitz.

- 4 ,

 4 with n = 15, 36, 55 for d = 3, and n = 35, 120, 220 for d = 4, which is far better than the value of exp(-n 1 d ).

Proposition 4 . 1 .

 41 Assume that there exists S {1, . . . , d} such that V n ∩ V S = {0}. Then for any C ∈]0, 1[, there exists y ∈ Y such that u(y) -P y Vn u(y) H 1 0 C u(y) H 1 0 . (4.58)

  .60) if ∞ = L. As a consequence, with L = L k and V n defined as in §3.3, one has the estimates u(y) -P y Vn u(y)

Figure 4 :

 4 Figure 4: Non-lipschitz partition of Ω.

1 0u(y) H 1 0 ,

 10 displays on the left the evolution of the maximal relative error of the Galerkin projection supy A ∈[1,∞] u(y) -P y Vn u(y) Has a function of n = dim(V n ) for these various selection strategies. It reveals the superiority of the greedy selection that reaches machine precision after picking n = 11 reduced basis elements, and the gain in including the limit solution in the case of a random selection. As a comparison, we display on the right the decay of the relative H 1 0 -orthogonal projection error supy A ∈[1,∞]u(y) -P Vn u(y)

Figure 6 :

 6 Figure 6: Galerkin and H 1 0 projection error (both measured in H 1 0 relative error maximized over the parameter domain) for different reduced bases, case d = 2.

Figure 7 :

 7 Figure 7: The Galerkin projection of Greedy Galerkin method for increasing dimensionality in geometries satisfying (left) or not (right) the assumptions.

Acknowledgements: We thank the anonymous reviewers for their constructive comments. We also thank François Murat for useful discussions in the understanding of the convergence process towards limit solutions, Hamza Maimoune for leading us to this work through his remarks during his master project, and Jules Pertinand for useful discussions.

for any y ∈ R . Since all the y j are greater or equal to 1, one has v H 1 0 v y for all v and therefore (4.59) follows.

For infinite rectangles R such that ∞ = L, we again introduce S = {j : j = L}. Then, using (3.47),

Similarly to the previous case, we apply (3.39) from Lemma 3.3:

and we thus obtain (4.60).

After taking L = L k and defining V n as the sum of the V ,k for ∈ E k , the derivation of (4.61) and (4.62) is exactly the same as for (3.54) and (3.56).

Remark 4.3. As in Remark 3.10, it is expected that the same rate of convergence is attained if V n is a reduced basis space generated by solutions u(y i ), i = 1, . . . , n, as long as there are O k+d-1 d-1 samples y i in each rectangle, however with samples forced to be of the form u S (y i S c ) ∈ V S in the case of infinite rectangles.

State and parameter estimation

The state estimation problem consists in retrieving the solution u = u(y) when the parameter y is unknown, and one observes m linear measurements

where the i are continuous linear functional on the Hilbert space V that contains the solution manifold. These linear functionals may thus be written in terms of Riesz representers

The Parametrized Background Data Weak (PBDW) method, introduced in [START_REF] Maday | A parametrizedbackground data-weak approach to variational data assimilation: Formulation, analysis, and application to acoustics[END_REF] and further studied in [START_REF] Binev | Data assimilation in reduced modeling[END_REF], exploits the fact that all potential solutions are well approximated by reduced model spaces V n . It is based on a simple recovery algorithm that consists in solving the problem

where, for w = (w 1 , . . . , w m ) ∈ R m ,

is the affine space of functions that agree with the measurements. The analysis of this problem is governed by the quantity

where

Then, there exists a unique minimizing pair

to (4.63), which satisfies the estimates

The computation of (u * , v * ) amounts to solving finite linear systems, and both solutions depend linearly on w.

Turning to our specific elliptic problem, and assuming that the i belong to H -1 (Ω) = V for V = H 1 0 (Ω), we may apply the above PBDW method using the reduced basis spaces V n introduced in §3. As an immediate consequence of Theorem (3.7), we obtain a recovery estimate in relative error.

The positive constants c and C only depend on d, C f , and on the geometry of the partition through the constant C 0 .

Proof. It follows readily by combining (3.56) applied to y = y with the recovery estimates (4.65) and (4.66).

We next turn to the problem of parameter estimation, namely recovering an approximation y * to y from the measurements w. In contrast to state estimation, this is a nonlinear inverse problem since the first mapping in y → u → w is typically nonlinear. One way of relaxing this problem into a linear one is by first using a recovery u * of the state u, for example obtained by the PBDW method. One then defines y * as the minimizer over Y of the residual R(y) := div(a(y)∇u * ) + f H -1 .

Proof. For 1 j d, take φ ∈ H 1 0 (Ω j ), then

which combined with (4.67) gives

Using the Lax-Milgram estimate

we reach (4.69).

Remark 4.6. The bound (4.69) is not entirely satisfactory since the approximation error on y j remains high when y ∈ N with y j 1. We do not know if a bound of the form

Numerical illustration

The base model that will be used all along the numerical illustrations is the diffusion equation (1.4) with data f = 1 set on the two-dimensional square Ω = [-1, 1] 2 with homogeneous Dirichlet boundary conditions. We consider a piece-wise constant diffusion coefficient a |Ωj = y j , 1 j d, on a partition of Ω into 16 squares of quarter side-length.

As such this partition does not satisfy the geometrical assumption of "Lipschitz partition" that was critical in our analysis for the application of Lemma

Parameter selection

We first study the case of a one parameter family : the diffusion coefficient y A of Ω A in Figure 3 varies from 1 to ∞, while the other subdomains are considered as background with all coefficents equal to 1. Thus the y k are of the form y k = (y k A , 1, 1, 1). In reduced basis constructions, two approaches for parameter selection are usually considered : random or greedy. Random selection usually performs well enough in many situations, however we shall see that it fails in the high contrast regime. This is in particular due to the fact that it does not capture the limit solutions, while we have observed in §4 that robust convergence of the Galerkin method in the high-contrast regime critically requires to include limit solutions in the space V n . Here, there is only one limit solution u ∞ = u(y ∞ ) where y ∞ = (∞, 1, 1, 1), and this element is picked by the greedy method if initialized at any other point.

More precisely, we compare four strategies for selecting the y k A ∈ [1, ∞]:

• Random: the y k A are drawn independently according to the uniform law for 1 y A ∈ [0, 1]. • Random-∞: First the limit solution corresponding to y A = ∞ is put in the basis. The rest of the elements are randomly picked as in the previous case.