Boris Andreianov

Mohamed Maliki

A note on uniqueness of entropy solutions to degenerate parabolic equations in R N

Keywords: Mathematics Subject Classification (2000). Primary 35K65 ; Secondary 35A05 Degenerate hyperbolic-parabolic equation, conservation law, non-Lipschitz flux, entropy solution, Kato inequality, infinite speed of propagation, uniqueness

We study the Cauchy problem in R N for the parabolic equation

which can degenerate into a hyperbolic equation for some intervals of values of u. In the context of conservation laws (the case ϕ ≡ 0), it is known that an entropy solution can be non-unique when F ′ has singularities. We show the uniqueness of an entropy solution to the general parabolic problem for all L ∞ initial datum, under the isotropic condition on the flux F known for conservation laws. The only assumption on the diffusion term is that ϕ is a non-decreasing continuous function.

Introduction

Consider the convection-diffusion problem u t + div F (u) -∆ϕ(u) = f in (0, T ) × R N , u| t=0 = u 0 [START_REF] Maliki | Renormalized solution for a nonlinear anisotropic degenerated parabolic equation with nonlipschitz convection and diffusion flux functions[END_REF] with a source f measurable on (0, T ) × R N , with T 0 f (t, •) L ∞ dt < +∞ and an initial datum u 0 ∈ L ∞ (R N ). Here F = (F 1 , . . . , F N ) : R → R N is assumed merely continuous (a quantitative continuity assumption on F will be imposed in the sequel), and ϕ : R → R is a continuous non-decreasing function.

Degenerate and non-degenerate problems of the kind [START_REF] Maliki | Renormalized solution for a nonlinear anisotropic degenerated parabolic equation with nonlipschitz convection and diffusion flux functions[END_REF], often investigated under the local Lipschitz continuity assumption on ϕ and F , appear in various physical contexts, including e.g. flows and sedimentation in porous media. Mathematical treatment of these problems was boosted some ten years ago by the introduction of the adequate notion of entropy solution (see Carrillo [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF]).

Indeed, the framework (1) includes conservation laws as a particular case. It is well known that in general, global classical solutions of (1) may not exist; and that a weak solution in the sense of distributions may not be unique. The standard way to fix this problem is to work with the so-called entropy solutions (see Kruzhkov [START_REF] Kruzhkov | Generalized solutions of the Cauchy problem in the large for firstorder nonlinear equations[END_REF] for the case of conservation laws, and Carrillo [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF] for the adaptation of this notion to the case of a degenerate elliptic-parabolic-hyperbolic equation, of which (1) is a particular case). The classical result of Kruzhkov establishes uniqueness of an entropy solution (together with the property of finite domain of dependence on initial data) for the case where ϕ ≡ 0 and F is locally Lipschitz continuous. When the Lipschitz continuity assumption is dropped, uniqueness of entropy solutions for a conservation law can be lost (see the works [START_REF] Yu | Generalized solutions of the Cauchy problem for quasilinear conservation laws[END_REF][START_REF] Kruzhkov | First-order quasilinear conservation laws with infinite initial data dependence area[END_REF][START_REF] Kruzhkov | Conservation laws with the infinite domain of dependence on initial data[END_REF][START_REF] Kruzhkov | Osgood's type conditions for uniqueness of entropy solutions to Cauchy problem for quasilinear conservation laws of the first order[END_REF] of Kruzhkov and Panov). The effect of non-uniqueness is closely connected to the property of "infinite speed of propagation", which arises when F ′ is unbounded. This is the goal of this note to investigate the question of uniqueness of entropy solutions of (1) for a general nonlinearity ϕ in the diffusion term. Technically, the problem amounts to the difficulty of exploiting the so-called Kato inequality

(u -û) + t + div sign + (u -û)(F (u) -F (û) ≤ ∆(ϕ(u) -ϕ(û)) + + (f -f ) + in D ′ ([0, T ) × R N ); (2)
here u, û are two entropy solutions of (1) corresponding to source terms f, f . Formally, if we let the test function in (2) converge to one, we get the inequality

d dt R N (u -û) + (t) ≤ R N (f -f ) + in D ′ ([0, T )),
which implies uniqueness of an entropy solution. Even when one can justify that u -û ∈ L ∞ (0, T ; L 1 (R N )), a too slow decrease of |F (u) -F (û)| as |x| → ∞ could be an obstacle to this formal reasoning. In fact, the issue of uniqueness of L 1 ∩ L ∞ solutions for the conservation law u t + div F (u) = 0, u| t=0 = u 0 is not yet clearly understood; see [START_REF] Andreianov | L 1 theory of scalar conservation law with continuous flux function[END_REF] for a discussion of relevancy of the known conditions.

For the case ϕ ≡ 0 and L ∞ entropy solutions, sufficient uniqueness conditions for (1) in terms of the moduli of continuity of F were first formulated by Kruzhkov and Hil'debrand ([12]) (after that Bénilan ( [START_REF] Ph | Équations d'évolution dans un espace de Banach quelconque et applications[END_REF] obtained the same condition for mild solutions in L 1 ). Roughly speaking, the conditions of [START_REF] Ph | Équations d'évolution dans un espace de Banach quelconque et applications[END_REF][START_REF] Kruzhkov | The Cauchy problem for first order quasilinear equations in the case when the domain of dependence on the initial data is infinite. (Russian). Collection of articles dedicated to the memory of I.G. Petrovskii[END_REF] (see also [START_REF] Kruzhkov | On the nonlocal theory of the Cauchy problem for quasi-linear equations of first order in the class of locally summable functions[END_REF]) amount to the Hölder continuity of F of order α = 1 -1 N . This condition is "isotropic": the possibility that some of the components F 1 , . . . , F N of F may have a "better" modulus of continuity than the vector-function F is not exploited. This contrasts with the following "anisotropic" assumption

lim inf r↓0 N i=1 ω i (r) r N -1 < +∞ (3)
due to Kruzhkov and Panov ([13,[START_REF] Yu | Generalized solutions of the Cauchy problem for quasilinear conservation laws[END_REF]); here for i = 1, . . . , N , ω i : R + → R + is a modulus of continuity of F i on the interval [-M, M ] containing the values of u. Assumption (3) restricts the behaviour of the moduli of continuity ω i (r) of F i at r = 0. Assumption (3) is also sufficient for the uniqueness of entropy solutions of a scalar conservation law. A sharper condition is given in [START_REF] Kruzhkov | Osgood's type conditions for uniqueness of entropy solutions to Cauchy problem for quasilinear conservation laws of the first order[END_REF]. Notice that for the L 1 ∩ L ∞ data, sufficient uniqueness conditions of a completely different nature were found by Bénilan and Kruzhkov in [START_REF] Ph | Conservation laws with continuous flux functions[END_REF] (see also [START_REF] Andreianov | L 1 theory of scalar conservation law with continuous flux function[END_REF]).

In [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF], together with Touré the second author of the present paper proved uniqueness of an entropy solution to the equation ( 1) upon replacing ω i (r) in [START_REF] Andreianov | On well-posedness for nonlinear diffusion equations in R N[END_REF] with ω i (r) + (rω ϕ (r)) 1/2 ; here ω ϕ : R + → R + is a modulus of continuity of ϕ. Clearly, if the space dimension N equals 1, both the Kruzhkov-Panov and the Maliki-Touré conditions are always satisfied. If the space dimension is equal to 2, then the Maliki-Touré condition contains no restriction on the function ϕ.

In the work [START_REF] Andreianov | On well-posedness for nonlinear diffusion equations in R N[END_REF] we have investigated the exactness of the assumption of [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF] for the case of a pure diffusion equation (i.e., F ≡ 0). It turns out that uniqueness of L ∞ solutions for this case holds for all ϕ. In the present paper, we show a similar result for the full convection-diffusion equation [START_REF] Maliki | Renormalized solution for a nonlinear anisotropic degenerated parabolic equation with nonlipschitz convection and diffusion flux functions[END_REF]. More exactly, we show uniqueness of an entropy solution for (1) for all continuous non-decreasing ϕ, but under the assumption that F satisfies the isotropic local Hölder continuity condition of order α = 1 -1 N . According to the previous remark, we can restrict our attention to the case N ≥ 3.

Let us briefly describe the main idea of the proof. In order to make disappear the third term in (2), we choose a test function ρ that is, roughly speaking, a truncation of the fundamental solution to the Laplace equation in R N . Notice that we cannot avoid taking ρ convex in the radial direction, because we need ρ to be non-negative and equal to zero at infinity. Yet we can take ρ concave in the orthogonal directions, so that compensations make non-positive the expression (ϕ(u) -ϕ(û)) + ∆ρ in the D ′ formulation of (2). To this end, any positive superharmonic vanishing at infinity function ρ could be used. Among the radial superharmonic functions, the use of the truncated fundamental solution is optimal with respect to the restrictions on F that come from the second term in (2); indeed, the second term in (2) has to be controlled as well.

Our technique does not allow to benefit from the anisotropy of the flux F ; in particular, unlike in [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF], our assumptions do not reduce to (3) in the trivial case ϕ ≡ 0. The case of an anisotropic diffusion of the form N i=1 ∂ xixi ϕ i (u) cannot be covered neither (except when it reduces to the isotropic case by a change of coordinates in R N ; this happens when the functions ϕ i are multiples of some ϕ). Indeed, the anisotropy makes it impossible to benefit from the compensations between the different derivatives ρ xixi . We refer to Maliki and Ouedraogo [START_REF] Maliki | Renormalized solution for a nonlinear anisotropic degenerated parabolic equation with nonlipschitz convection and diffusion flux functions[END_REF] for results on the non-isotropic diffusion case under suitable assumptions on the moduli of continuity of ϕ i , along the guidelines of [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF]. The problem where the quasilinear diffusion operator ∆ϕ(u) is replaced with a fully nonlinear diffusion operator such as the p-laplacian ∆ p ϕ(u) is even more difficult; to our knowledge, no uniqueness result for entropy solutions in R N is available when p > 2.

Definitions and results

Recall that ϕ is a continuous function on R. For M > 0, we say that a subadditive, continuous function

ω ϕ : [0, 2M ] → R + such that ω ϕ (0) = 0 is a modulus of continuity of ϕ, if ∀z, ẑ ∈ [-M, M ] |ϕ(z) -ϕ(ẑ)| ≤ ω ϕ (|z -ẑ|). ( 4
)
Recall that we only work with bounded solutions of (1). Without loss of generality, we can assume that M is fixed, moreover, ω ϕ is strictly concave (and thus, strictly increasing) and extended to the whole of R + ; we denote its inverse function by Ω ϕ . We use the Fenchel (Legendre) transform of Ω ϕ :

Ω * ϕ (t) = sup z∈R + zt -Ω ϕ (z) .
It easily follows that Ω * ϕ is strictly increasing, thus it is invertible. With the above notation, we have for all z, t, r ∈ R + ,

zt ≤ Ω ϕ (z) + Ω * ϕ (t), (Ω ϕ • ω ϕ )(r) = r. (5)
For a vector-valued function F : R → R N , we introduce the (isotropic) modulus of continuity ω F and the related functions Ω F , Ω * F in the same way, replacing |ϕ(z) -ϕ(ẑ)| in (4) with |F (z) -F (ẑ)|. Here and in the sequel, we mean that R N is endowed with the euclidean norm, which we denote by | • |.

Definition 1. An entropy solution of (1) is a function u ∈ L ∞ ((0, T ) × R N ) such that ϕ(u) ∈ L 2 (0, T ; H 1 loc (R N )
) and the inequalities

- T 0 R N |u -k|ξ t + sign (u -k)(F (u) -F (k)) • ∇ξ + sign (u -k) ∇ϕ(u) • ∇ξ ≤ T 0 R N sign (u -k) f ξ + R N |u 0 -k| ξ(0, •) (6)
hold for all k ∈ R and all ξ ∈ D([0, T ) × R N ).

Here and in the sequel, we mean that

u 0 ∈ L ∞ (R N ), f (t, •) L ∞ ∈ L 1 (0, T ).
It is clear that an entropy solution is also a solution in the sense of distributions; it suffices to use [START_REF] Ph | Conservation laws with continuous flux functions[END_REF] with k = ± u L ∞ . It follows that in [START_REF] Ph | Conservation laws with continuous flux functions[END_REF], one can replace sign (u -k) and |u -k| with sign + (u -k) and (u -k) + , respectively, where sign + (r) := max{sign r, 0} and r + := max{r, 0}.

Existence of an entropy solution is standard; it can be obtained, e.g., by a regularization of F and ϕ (when ϕ ≡ 0, one takes ϕ ε (z) = εz, which is the so-called "vanishing viscosity" approximation), with the help of the translation invariance in x of the left-hand side of (1) and the L 1 contraction result of Maliki and Touré [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF].

Definition 1 implies the Kato inequality (2), with the help of the doublingof-variables approach of Kruzhkov ([9]) and the techniques of Carrillo ([8]) and Blanchard and Porretta ( [START_REF] Blanchard | Stefan problems with nonlinear diffusion and convection[END_REF]) (see e.g. [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF][START_REF] Andreu | Renormalized solutions for degenerate elliptic-parabolic problems with nonlinear dynamical boundary conditions and L 1 -data[END_REF][START_REF] Andreianov | On well-posedness for nonlinear diffusion equations in R N[END_REF]). Inequality (2) can also be obtained without doubling the variables, with the help of the so-called kinetic formulation (see Perthame [START_REF] Perthame | Uniqueness and error estimates in first order quasilinear conservation laws via the kinetic entropy defect measure[END_REF] for the case of a conservation law). Uniqueness of an entropy solution of (1) (and, more generally, the L 1 contraction and comparison principle) follows whenever we can pass to the limit in the Kato inequality (2) with test functions ξ → 1 on R N .

We assume that N ≥ 3 (for N ≤ 2, the results of Maliki and Touré [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF] apply with no restriction on ϕ).

Theorem 2.

Let N ≥ 3. Consider an arbitrary non-decreasing continuous function ϕ : R → R. Consider a locally Hölder continuous of order (1

-1 N ) function F : R → R N . Then whenever (u 0 -û0 ) + ∈ L 1 (R N ), (f -f ) + ∈ L 1 ((0, T ) × R N ), R N (u -û) + (t, •) ≤ R N (u 0 -û0 ) + + t 0 R N (f -f ) + a.e. on (0, T ), (7)
where u, û are entropy solutions corresponding, respectively, to given initial data u 0 , û0 ∈ L ∞ (R N ) and sources f,

f with f (t, •) L ∞ (R) , f (t, •) L ∞ (R) ∈ L 1 (0, T ).
In particular, under the above assumptions on ϕ, F there exists a unique entropy solution u u0,f for given data u 0 , f ; the map (u 0 , f ) → u u0,f is order-preserving, and the map

u 0 ∈ L ∞ (R N ) ∩ L 1 (R N ) → u u0,0 is a T-contraction in L 1 .

Proof of Theorem 2

The technique of the proof of the theorem is closely related to the previous work [START_REF] Andreianov | On well-posedness for nonlinear diffusion equations in R N[END_REF]. Roughly speaking, we take in the Kato inequality (2) radial test functions ξ such that ∆ξ ≤ 0. This allows us to drop the second term in the right-hand side of (2); thus restrictions on ϕ are bypassed. The test functions are constructed by truncating the laplacian's fundamental solution profile

1 |x| N -2 .
We are intended to use [START_REF] Andreianov | L 1 theory of scalar conservation law with continuous flux function[END_REF] with the test functions

ρ ε (x) = max{ |x| R , 1} 2-N -ε
with ε > 0, R > 1 (in order to lighten the notation, we do not indicate explicitly that ρ ε also depends on R). Then we let ε → 0, and finally we let R → +∞ . To this end, let

ρ ε,L (x) = R N -2+ε max{|x|, R} 2-N -ε -L 2-N -ε + , L > R.
By a density argument, we take in (2) test functions under the form ξ(t, x) = µ(t)ρ ε,L (x), where µ ∈ D([0, T )) + . Indeed, regularizing ρ ε,L by convolution, dropping the negative measure part of the distribution ∆ρ ε,L concentrated on the set {x ∈ R N | |x| = R}, using the definition of ω ϕ , ω F we deduce

T 0 R N (u -û) + ρ ε,L (-µ t ) ≤ T 0 R N ω F ((u -û) + )| ∇ρ ε,L | µ + T 0 R N ω ϕ ((u -û) + )∆ ac ρ ε,L µ + {|x|=L} ω ϕ ((u -û) + ) (N -2+ε)L 1-N -ε µ + T 0 R N (f -f ) sign + (u -û)ρ ε,L µ + R N (u 0 -û0 ) + ρ ε,L µ(0)
for a.e. L > R ′ ; here ∆ ac ρ ε,L represents the absolutely continuous (with respect to the Lebesgue measure on R N ) part of the measure ∆ρ ε,L . The integral on the sphere {|x| = L} is understood with respect to the (N -1)-dimensional Hausdorff measure. Because u, û are bounded, the integral on the sphere {|x| = L} is upper bounded by const L N -1 L 1-N -ε = const L -ε . We calculate

∆ ac ρ ε,L = ε(N -2+ε) |x| -2 ρ ε 1l R<|x|<L and | ∇ρ ε,L | = |N -2+ε| |x| -1 ρ ε 1l R<|x|<L ; here ρ ε (x) = max{ |x| R , 1} 2
-N -ε . Notice that 0 ≤ ρ ε,L ≤ 1 for all ε, R, L. Now we let L → ∞. Thanks to the boundedness of u, û and to the integrability assumption on (u 0 -û0 ) + , (f -f ) + we deduce that

T 0 R N (u -û) + ρ ε (-µ t ) ≤ c T 0 {|x|>R} ω F ((u -û) + )|x| -1 + ε ω ϕ ((u -û) + ) |x| -2 ρ ε + T 0 R N (f -f ) sign + (u -û) µ + R N (u 0 -û0 ) + µ(0). ( 8
)
Here and in the sequel, we assume ε ∈ (0, 1), so that (N -2 + ε) ≤ (N -1), and fix c = (N -1) µ L ∞ . Notice that each term in the right-hand side of ( 8) is finite.

Our goal is to show that, letting ε → 0 and R → ∞, we can drop the first term in the right-hand side of [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF]. The first step is to prove that (u -û) + is integrable on (0, T ) × R N .

To this end, fix δ > 0. Let us show that

c ε T 0 {|x|>R} ω ϕ ((u -û) + ) |x| -2 ρ ε ≤ δ T 0 {|x|>R} (u -û) + ρ ε + r δ,R (ε), (9)
where for all fixed δ > 0, R > 1, the quantity r δ,R (ε) tends to zero as ε decreases to zero. Indeed, using (5), we get

cε ω ϕ ((u -û) + ) |x| -2 = δ ω ϕ ((u -û) + ) cε δ |x| -2 ≤ δ (u -û) + + δ Ω * ϕ ( cε δ |x| -2 );
thus [START_REF] Kruzhkov | Generalized solutions of the Cauchy problem in the large for firstorder nonlinear equations[END_REF] holds with

r δ,R (ε) := T δ {|x|>R} Ω * ϕ ( cε δ |x| -2 )ρ ε .
By the convexity of Ω * ϕ , we have

Ω * ϕ ( cε δ |x| -2 ) ≤ (Ω * ϕ ) ′ ( cε δ R -2 ) cε δ |x| -2 whenever |x| ≥ R.
Without loss of generality, we can assume that Ω ϕ is convex and strictly increasing; then it is not difficult to prove that ess lim t↓0 (Ω * ϕ ) ′ (t) = 0 (see e.g. [START_REF] Andreianov | On well-posedness for nonlinear diffusion equations in R N[END_REF]). Hence we deduce that (Ω * ϕ ) ′ ( cε δ R -2 ) =: o ε tends to zero as ε → 0. Therefore using polar coordinates, we get

0 ≤ r δ,R (ε) = δ T {|x|>R} Ω * ϕ ( cε δ |x| -2 )ρ ε ≤ o ε cT ε {|x|>R} |x| -2 ρ ε = cT ε R N -2+ε o ε +∞ R r -2+2-N -ε r N -1 dr (10) = cT ε R N -2+ε R -ε ε o ε → 0 as ε → 0.
Similarly, from (5) we deduce

cω F ((u -û) + ) |x| -1 ρ ε ≤ 1 2 (u -û) + ρ ε + 1 2 Ω * F (2c|x| -1 ) ρ ε . (11)
By the Hölder continuity assumption on F , we can take

ω F (r) = C r 1-1 N , thus Ω F (z) = C z N N -1 , thus Ω * F (t) = C t N . ( 12
)
Here C is a generic constant that changes from one expression to another. Hence

T 0 {|x|>R} Ω * F (2c|x| -1 )ρ ε = C T R N -2+ε +∞ R 2c r N r 1-ε dr ≤ const. (13)
By density, we can take µ(•) = (T -•) + in (8), so that -µ t (t) = 1l (0,T ) (t). Putting δ = 1/2 and letting ε → 0, from ( 8) and ( 9)-( 13) we deduce that

T 0 {|x|<R} (u -û) + ≤ T R N (u 0 -û0 ) + + T T 0 R N (f -f ) + + const ≤ const.
Letting R → ∞, by the monotone convergence theorem we deduce that (u -û) + ∈ L 1 ((0, T ) × R N ). [START_REF] Kruzhkov | Osgood's type conditions for uniqueness of entropy solutions to Cauchy problem for quasilinear conservation laws of the first order[END_REF] In order to conclude the proof, we return to [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF]. We now replace [START_REF] Kruzhkov | On the nonlocal theory of the Cauchy problem for quasi-linear equations of first order in the class of locally summable functions[END_REF] with the estimate

cω F ((u -û) + ) |x| -1 ρ ε ≤ δ c Ω F 1 δ ω F ((u -û) + ) ρ ε + δ c Ω * F (|x| -1 ) ρ ε = δ 1-N N -1 c C (u -û) + + δ c C |x| -N R |x| N -2+ε
; [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF] the expressions [START_REF] Kruzhkov | The Cauchy problem for first order quasilinear equations in the case when the domain of dependence on the initial data is infinite. (Russian). Collection of articles dedicated to the memory of I.G. Petrovskii[END_REF] are used in [START_REF] Maliki | Uniqueness of entropy solutions for nonlinear degenerate parabolic problem[END_REF]. Hence setting C(δ) = δ

Using ( 9) and ( 10) once more, from ( 14 as ε → 0 and then R → ∞. Now we let ε → 0 and R → +∞ in [START_REF] Carrillo | Entropy solutions for nonlinear degenerate problems[END_REF]; notice that ρ ε converge to 1 and remains bounded. With the help of ( 16),( 17) and (18), we deduce

T 0 R N (u -û) + (-µ t ) ≤ T 0 R N (f -f ) sign + (u -û) µ + R N (u 0 -û0 ) + µ(0). ( 19
)
The claim [START_REF] Blanchard | Stefan problems with nonlinear diffusion and convection[END_REF] follows readily from (19). Because the existence of an entropy solution is already known, this ends the proof of Theorem 2.

F

  ((u -û) + ) |x| -1 ρ ε ≤ C(δ) T 0 {|x|>R} (u -û) + + δ c C T R N -2+ε {|x|>R} |x| 2-2N +ε ρ ε ≤ C(δ) T 0 {|x|>R} (u -û) + + const δ. (16)The left-hand side of (16) converges to zero as R → ∞, uniformly in ε; indeed, û) + + const δ → 0 as R → ∞.

) we get c ε T 0

 0 {|x|>R} ω ϕ ((u -û) + ) |x| -2 ρ ε û) + + r δ,R (ε) -→ 0 (18)


Mathias Legrand

Christophe Pierre

Numerical investigation of abradable coating wear through plastic constitutive law: application to aircraft engines

Keywords: Turbomachinery, Abradable coatings, Wear, Contact dynamics, Explicit timestepping technique

In the field of turbomachines, better engine performances are achieved by reducing possible parasitic leakage flows through the closure of the clearance distance between blade tips and surrounding casings. Together with new technologies involving higher casing conicity for improved compression rates, direct contact is now considered as part of aircraft engines normal life. In order to avoid possibly catastrophic scenarios due to high contact efforts between the rotating and static components, implementation of abradable coatings has been widely recognized as a robust solution offering several advantages: reducing potential damage to the incurring blade as well as adjusting operating clearances, in-situ, to accept physical contact events. Nevertheless, the process of wear undergone by abradable coatings is not well understood and its consequences are still under investigation. In the present work, its macroscopic behavior is numerically approximated through a piecewise linear plastic constitutive law which allows for real time access to the current abradable layer profile. First results prove convergence in time and space of the proposed approach and show that the frequency content of the blade response is clearly affected by the presence of abradable coatings. It seems that opening the clearance between the blade tip and the casing during wear leads to large amplitudes of motion far from the usual linear conditions provided by the well-known Campbell diagrams.

Introduction

Facing a constant need of improved performances for lower operating costs, jet engine manufacturers respond with new technologies such as, amongst others, higher operating temperatures, more efficient aerodynamic designs and lightweight materials. One of the last means being addressed lies in the reduction of possible parasitic leakage flows by closing the gap between blade tips and surrounding casings. This is made possible through the implementation of abradable coatings [START_REF] Yi | Friction and wear behaviour and abradability of abradable seal coating[END_REF] in the compressor and turbine sections (see Fig. 1 for the compressor of interest in the present study) where a minimal clearance is required. The mechanical properties of the abradable material are of primary importance as it must preserve the incurring blade-tips from damage by being reasonably soft, but also be sufficiently hard to stand very high temperatures and high-speed gas flows with inherent solid particles [START_REF] Ma | Investigation of abradable seal coating performance using scratch testing[END_REF]. The role of abradable coatings is to allow for closer clearances as well as to accept physical contact events. The latter may occur through a variety of mechanisms: coincidence of vibration modes, thermal gradient in the casing, rotor imbalance due to design uncertainties, etc. Unfortunately, it has been detected by experimental investigations that erosive wear of abradable coatings may play a significant role in the initiation of divergent behaviors such as propagating cracks in blade roots [START_REF] Padova | Experimental results from controlled blade tip/shroud rubs at engine speed[END_REF]. Accordingly, it seems urgent to enrich the limited current knowledge of the circumstances under which they occur [START_REF] Jiang | Contact model of a rotating rubbing blade[END_REF].

Although attention has been brought in the past to the dynamics of blades in presence of direct contact [START_REF] Sunil | Non-linear dynamic response of a rotating radial timoshenko beam with periodic pulse loading at the free-end[END_REF][START_REF] Lesaffre | Contact analysis of a flexible bladed-rotor[END_REF][START_REF] Legrand | Two-dimensional modeling of an aircraft engine structural bladed disk-casing modal interaction[END_REF], modeling the erosion process in a macroscopic manner seems rather new [START_REF] Salles | Analysis of a bladed disk with friction and fretting-wear in blade attachments[END_REF][START_REF] Legrand | Modèles de prédiction de l'interaction rotor/stator dans un moteur d'avion[END_REF] even though simple analytical derivations do exist [START_REF] Rabinowicz | Friction and wear of materials[END_REF]. This task is rendered difficult because of the complex and coupled physical mechanisms involved such as dislocation, thermal gradients, large displacements [START_REF] Andrews | A dynamic thermoviscoelastic contact problem with friction and wear[END_REF] and mass removal depending on the investigated type of material. In the framework of turbomachines, where large relative displacements between contacting components together with high abradable wear rates are observed, most of the existing theoretical statements with strongly limiting assumptions do not seem relevant and easy to implement [START_REF] Strömberg | Derivation and analysis of a generalized standard model for contact, friction and wear[END_REF], even though some of them seem promising [START_REF] Wang | Finite element model of erosive wear on ductile and brittle materials[END_REF][START_REF] Dmitriev | A multilevel computer simulation of friction and wear by numerical methods of discrete mechanics and a phenomenological theory[END_REF].

It is here assumed that plasticity with its inherent abilities to represent permanent deformation in a simple fashion stands as a natural first macroscopic approach in order to account for abradable coatings erosive wear. Even though mass removal is neglected and the exact dynamic of the abradable material is not retrieved, it is thought that the behavior of the blade will be properly predicted. Furthermore, the energy transferred from the blade to the casing during contact interaction is partially dissipated because of wear: this can be captured by a plastic constitutive law.

The proposed numerical tool embeds in an explicit time marching technique, a contact detection procedure together with the calculation of internal forces and plastic deformations arising in the abradable material, thus controlling the desired amount of wear. It allows for real time access to the current profile of the abradable, supposedly key feature for detecting such critical behaviors mentioned above.

Structural model and equations of motion 1.Finite element model

The present study deals with a single rotating blade and a surrounding casing of a low pressure compressor stage, as depicted in Fig. 2. Possible gyroscopic effects, centrifugal stiffening or imbalance loads are not accounted for. The considered sector is originally discretized in 3,764 prismatic finite elements connected through 6,734 nodes. Within the well-known finite element framework under the assumption of small displacements, vector u stores all the displacement degrees-of-freedom of the blade and the respective mass matrix M, damping matrix D, stiffness matrix K and contact forces F c are built accordingly. The resulting governing equations of motion take the form: ough preliminary simulations, it is here admitted that the casing remains unsensitive to the contact interaction with the blade and is not modeled as a flexible component.

M ü + D u + Ku + F c = 0 (

Reduced-order model and component mode synthesis

The introduced finite element model of the blade is numerically too large and leads to cumbersome computation times. It is reduced by following the Craig-Bampton procedure [START_REF] Craig | Coupling of substructures for dynamics analyses[END_REF]. The original equations of motion are projected onto the new reduced-order space such as:

u = u f u i = I 0 Φ R Φ L u f q (2)
where the size of the reduced displacement vector (u f q) T is substantially smaller than the size of physical displacement vector (u f u i ) T . The dynamics of the considered blade is now seen as a full set of constraint modes whose contributions u f are the physical displacements of the interface dof, complemented with a set of component modes of contribution q that control the precision of the numerical simulations. As deduced from Eq. ( 2), the contact constraints can directly be treated in the reduced space if the anticipated contact locations are defined as interface nodes, thus avoiding permanent forward and backward mappings to the physical space. This is a major feature motivating the choice of the Craig-Bampton technique. In this study, three nodes (leading edge, middle of the chord and tailing edge as displayed in Fig. 2) define the contact interface with the casing leading to a set of nine constraint modes: the subsequent reduced-order model should be capable of capturing complex flexural and torsional blade motions. Moreover, in order to ensure modal convergence, one hundred component modes are required: accordingly, the final size of the blade model after reduction is 109 dof. For the sake of simplicity, Eq. ( 1) has undergone the projection of Eq. ( 2) but notations are not modified.

Since the chosen Craig-Bampton interface nodes of the blade, as such, do not contain any information about the true geometry of the blade tip, this has to be numerically included in the solution method, as illustrated in Fig. 3, in order to ensure space convergence of the abradable profile.

Contact dynamics

In order to properly define the notations later used in the proposed algorithm, derivation of the equations is conducted in the context of contact mechanics [START_REF] Laursen | Computational contact and impact mechanics -Fundamentals of modeling interfacial phenomena in nonlinear finite element analysis[END_REF][START_REF] Wriggers | Computational contact mechanics[END_REF] even though contact forces exerting between blade interface nodes and facing abradable coatings will not be computed explicitly.

By choice, the blade supports the master surface Γ m c from which the abradable coating can be parameterized. It is then possible to find for any material point x ∈ Γ m c , limited here to the interface nodes 1 , its closest counterpart ȳ on the abradable material slave surface Γ s c :

ȳ = arg min y∈Γ s c x -y (3)
According to these notations, the discretized clearance between the two components can be stated:

g(x) = g 0 (x) + u m (x) -u s (ȳ(x)) • n (4)
where g 0 (x) represents the initial positive gap and n, the outward normal to Γ s c . The contact conditions, referred to as the Kuhn-Tucker optimality conditions, considered in a vectorcompact form 2 , are such that for all x ∈ Γ m c :

t N 0, g(x) 0, t N g(x) = 0 ( 5
)
where t N stands for the discretized contact pressure, assumed positive and acting on the contact interface. The initial clearances go from 1.5 • 10 -2 % to 4.3 • 10 -2 % of the blade length.

Abradable constitutive law with plasticity

As a first approach, the abradable coating is discretized with the usual one-dimensional twonode bar elements, as displayed in Fig. 3, undergoing a nonlinear plastic constitutive law. A single element is used over the thickness of the abradable layer since calculations are performed in a quasi-static compression framework only. The density, i.e. the number of bar elements along the circumference of the casing, of the abradable coating is left to investigation. By convention, strains ǫ and stresses σ are such that (ǫ, σ) ∈ + × + . The set of admissible stresses σ is defined as follows [START_REF] Simo | Computational inelasticity[END_REF]:

σ = {(σ, α) ∈ ( , )\f (σ, α) 0} (6)
where α : [0, T] → is an internal hardening variable and f , a yield function. It is also assumed that (1) the total strain is separated in an additive way between its elastic part ǫ e and plastic part ǫ p such as ǫ = ǫ e + ǫ p and (2) the relation between elastic strains and stresses is linear σ = Eǫ e . By choice hardening is isotropic. It corresponds to a uniform (isotropic) expansion of the initial yield surface (function) with no translation. In other words, the origin of σ does not move and the hardening is linear along the plastic flow which dictates the evolution of the plastic strain ∆ǫ p3 . This leads to:

f (σ, α) = σ -(σ Y + Kα) (7)
where σ Y > 0 stands for the elastic limit and K 0, for the plastic modulus of the abradable material. The second assumption yields:

∆α = ∆ǫ p (8)
and condition on the plastic flow is implies the existence of a consistency parameter γ, such as

∆ǫ p = γ ∂ f
∂ σ , equivalent to ∆ǫ p = γ because of Eq. ( 7). Dual variables γ and f obey the Kuhn-Tucker conditions, complemented by the consistency condition:

γ 0, f (σ, α) 0, γf (σ, α) = 0, γ∆f (σ, α) = 0 (9)
For a one-dimensional quasi-static strain formulation, more relevant to the finite element framework in displacement, the solution strategy is greatly simplified even though the nonlinear nature of the constitutive law can only be accounted for by incremental techniques. Consider an admissible state together with an imposed increment of deformation ∆ǫ within a purely elastic trial state:

σ trial = E∆ǫ + σ ∆ǫ p = 0 ∆α = 0 f trial = σ trial -(σ Y + Kα) (10)
In order to ensure that the trial state belongs to σ , f trial has to be tested:

• if f trial 0, trial and current states coincide;

• if f trial > 0, condition (9) 2 is violated and the trial state has to be corrected. The commonly adopted approach, named Return Mapping Algorithm [START_REF] Simo | A return mapping algorithm for plane stress elastoplasticity[END_REF], lies in the projection of the trial state on the boundary of the yield function f = 0 together with γ > 0 at constant strain. Variation of Eq. ( 7) yields:

f = f trial -γ (E + K) (11)
Consequently, f = 0 implies:

γ = f trial E + K (12)
and the following update is used:

σ = σ trial -Eγ ∆ǫ p = γ ∆α = γ (13)
The internal forces acting within each abradable element i is computed following the above mentioned procedure together with integration over the elementary domain.

During a contact phase, the virtual work of the internal forces acting within the abradable coating for a virtual displacement δu of the blade is equal by definition to the virtual work of the contact force for the same virtual displacement. By defining I = {i | g(i ) = 0} (blue bar elements in Fig. 3), equilibrium of the contact forces with the internal forces can be written as:

F c = i ∈I A i σ i ( 14
)
where A i stands for the cross-section area of an abradable element and depends on the density parameter. In other words, the role of the plastic constitutive law is twofold:

• computation of the contact forces.

• storage of the current abradable coating profile through ǫ p .

4 Time marching procedure

Background

The phenomenon under investigation is inherently highly dynamically transient and making use of time stepping techniques, either implicit or explicit, seems quite natural. Anyway, solving coupled nonlinear governing Eqs. ( 1) and ( 14) is a difficult task that requires full attention. As discussed in most of the literature, explicit and implicit approaches offer specific advantages and downsides. Among the scientific community has now been reached a consensus stipulating that explicit schemes were simpler and more straightforward to implement and implicit ones were consistently better formulated. It also turns out that depending on the nonlinear terms involved in the governing equations, such as smooth cubic restoring forces versus impact or plastic evolution laws for instance, categorizing amongst the available approaches remains unclear. Nevertheless, explicit techniques do not necessitate the calculation of tangent matrices as required in Newton-like algorithms inherently used in implicit procedures. For non-smooth and non-differentiable nonlinear terms such as those mentioned above, explicit algorithms seem more relevant [START_REF] Vola | Consistent time discretization for a dynamical contact problem and complementarity techniques[END_REF] and are adopted here. Nevertheless, great care is required in ensuring that the chosen time step does not yield erroneous results as no residual term is checked during integration. By noting u n +1 , the numerical approximation of the exact value u(t n +1 ) at time t n +1 = t n + h where h is the time-step, the classical explicit central finite difference scheme used in this work yields:

ün = u n +1 -2u n + u n -1 h 2 and un = u n +1 -u n -1 2h (15)

Solution method

The contact detection as well as the internal force contribution of the abradable material are handled by employing the prediction/correction technique developed in [START_REF] Carpenter | Lagrange constraints for transient finite element surface contact[END_REF] and proved to be relevant in such situations. The final algorithm is then divided into four steps:

1. prediction, at time step n +1, of the displacements u of the blade by neglecting the presence of the abradable coating. This predicted displacement, denoted with subscript p , is expressed as:

u n +1,p = M h 2 + D 2h -1 2M h 2 -K u n + D 2h - M h 2 u n -1 (16)
where displacements u n and u n -1 are known.

2. determination of the gap function vector g n +1,p between the two contacting components using Eq. ( 4). A search algorithm identifies all abradable elements i ∈ I being penetrated by the blade contact interface.

3. abradable internal forces computation through a deformation increment ∆ǫ induced by the predicted penetrations between the two bodies. Subsequent strains σ i ∈I , hardening variables α i ∈I and plastic deformations ǫ p i ∈I are updated using the above mentioned procedure. The final vector of internal forces is calculated through Eq. ( 14) and the abradable profil is then updated.

4. displacements correction consistent with the calculated contact forces [START_REF] Legrand | Two-dimensional modeling of an aircraft engine structural bladed disk-casing modal interaction[END_REF]:

u n +1 = u n +1,p - M h 2 + D 2h -1 F c ( 17
)
The situation where the abradable coating is totally removed is not tested here since there is always abradable to be worn. It is also interesting to note that the displacement correction in Eq. ( 17) could be moved to Eq. ( 16) then including the contact force calculated at the previous time step.

Results

Preliminaries

Several scenarios are possible regarding the initiation of the contact between the blade and surrounding rigid casing. It is here assumed that a temperature gradient equivalent to a multi-harmonic two-nodal diameter load quasi-statically distorts the casing in order to absorb the initial clearances, as depicted in Figs. is here limited to three boundary nodes located on the blade-tip, together with their respective abradable layer, but can be generalized to more nodes at the expense of CPU consumption. The blade meets the casing at least twice per round depending on the calculated level of wear. Due to the rotation of the blade, the spatial harmonics of the casing shape (see Fig. 4(b)) become temporal harmonics in the rotating reference frame rigidly fixed to the blade. Accordingly, in addition to the nonlinear contact/wear participation in the blade response, the latter is expected to contain these harmonics. The wear level is governed by the plastic law parameters E, K and σ Y illustrated in Fig. 5. Specific values are not provided for the sake of brevity but two different configurations, respectively with low and high wear, are later investigated. ) and high ( ) ductility of the abradable coatings Finally, each simulation final time, denoted by T f in the sequel, is normalized with respect to ten rounds of the blade. In a similar manner, the different depicted vibratory and wear levels and respective Fourier transforms are normalized with respect to the initial gap between interface node 1 and the casing.

Convergence of the erosion wear law

The convergence in space and time of the erosion wear law has to be checked before any further investigation. This is respectively achieved by increasing the density of abradable elements and by reducing the time-step of the numerical tool. Since the numerical width of the blade at the tip is constant, the profil of the abradable coating has to be independent of the mentioned density. Figure 6 depicts the final profiles of the abradable coating for different densities and same time step. Convergence is reached meaning that there exists a density threshold over which the profil becomes invariant. The sensitivity of the blade vibration to the same density parameters as in Fig. 6 is pictured in Fig. 7. The differences are almost undistinguishable and the vibratory level of the blade being a quantity of great interest in this study, we conclude that the convergence of the abradable space discretization and profil is satisfactory.

Regarding the convergence in time, Fig 8 depicts the vibratory level of interface node 1 for three different time steps. Similarly, it shows that the conditionally stable time step of the proposed numerical algorithm is reached. It is also noteworthy saying that the computation time is not highly dependent on the density as this parameter takes place in the correction step only. In the sequel, a density parameter offering the best compromise between efficiency and accuracy is chosen. to be excited in a dangerous manner through direct contact. Its frequency is denoted by f 1 with respect to which are normalized all the frequency results and rotational velocities Ω. A series of simulations has been conducted in order to understand the sensitivity of the abradable wear law and subsequent profile to the rotational velocity Ω. Beforehand, a quick modal analysis of the blade as a linear flexible structure is required to better understand the up-coming results. As the casing keeps a multi-harmonic two-nodal diameter shape during

Modal analysis and wear profile

Ω (Hz) = f 1 k (Hz), k = 2, 4, 6 . . . (18)
that describes engine-order lines crossing the first frequency of resonance of the blade. In Eq. ( 18), k is limited to even positive integers due to the assumed shape of the casing which leads to a nonlinear harmonic external excitation due to contact with an engine-order two fundamental component 4 . In this context, condition (18) will thus be satisfied for lower rotational velocities than a pure linear counterpart situation with a perfect mono-harmonic twonodal diameter shape on the casing where k = 2 would only be eligible. In what follows, we pay attention to k = 4 and k = 6 since k = 2 is out of the operating range in terms of Ω.

It is well known that direct unilateral contact conditions stiffen the interacting mechanical components and modify their frequency of resonance, phenomenon that can be captured by nonlinear modal analyses [START_REF] Jiang | Large-amplitude non-linear normal modes of piecewise linear systems[END_REF]. Accordingly, Eq. ( 18) could be revisited as follows:

Ω (Hz) = f 1 (|F c |) k (Hz), k = 2, 4, 6 . . . ( 19
)
where |F c | simply refers to the amplitude of the contact forces. Amplitude maps in Figs. 10 and 11 explicitly show the wear level in the abradable coating along the circumferential direction of the casing with respect to Ω and implicitly indicate the number of observed lobes. For low or high rotational velocities, the shape of the casing controls the wear profile since the blade does not respond in resonance to the nonlinear contact excitation and only two lobes are worn. On the contrary, when Eq. ( 19) is (almost) satisfied, large amplitudes of vibration are expected: this is clearly shown for k = 4 and k = 6 where four lobes and six lobes are distinguishable, respectively. The contact stiffening effect is well caught by the proposed algorithm since, in Figs. 10 and11, the worn lobe highest amplitudes should be located at Ω = 0.25 (k = 4) and 0.16 (k = 6) based on Eq. ( 18) but are located at Ω = 0.31 (k = 4) and Ω = 0.21 (k = 6) instead, see Eq. [START_REF] Simo | A return mapping algorithm for plane stress elastoplasticity[END_REF]. In other words, the first flexural mode of the blade is excited through intermittent contact with the casing increasing the level of erosion wear for very specific Ω. Nevertheless, the abradable ductility, determined by mechanical parameters E, K and σ Y do modify the conditions of interaction. As can be seen in Figs. 10 and 11 again, the rotational velocities for which the blade is in resonance are slightly different, depending on the level of wear. This will be further commented later on in the light of the analysis of the blade response frequency content. Higher harmonics for k = 8, 10, 12, 14 are also visible in Fig. 11 at lower rotational velocities.

The final abradable coating profile is compared in Fig. 12 for low and high wears and a rotational velocity around the respective first critical velocity numerically estimated for k = 4. The expected four lobes are obvious. and11 where the highest amplitudes are detected for Ω ≃ 0.21 and Ω ≃ 0.31, respectively. Most importantly, by comparing the pikes of resonance, the highest amplitudes of motion are not reached for pure unilateral contact conditions (see Fig. 13) for which the contact forces are the largest, but for a low level of wear as illustrated in Fig. 14. It means that the gap opening due to wear allows for higher displacements and are unfortunate in terms of divergent behaviors. Equivalently, pure unilateral contact conditions seem less dangerous than wear, to some extent, for the blade mechanical integrity as it inherently limits its displacements. Furthermore, very ductile abradable coatings conduct to softer contact efforts and subsequent smaller amplitudes of vibration (see Fig. 15). A compromise in the mechanical properties of the abradable material has to be found so that the useful and necessary mechanisms of wear do not lead to a structural failure of the blade.

Obviously, all the presented results strongly depend on the adopted scenario of interaction and further investigations have to be conducted to better understand the mechanisms of

Conclusion

The emphasis of the study has been placed on the understanding of the contact interaction occurring between a blade and a surrounding casing belonging to the low pressure compressor of an aircraft engine. The study more specifically focuses on modeling in a realistic and macroscopic fashion the erosion wear law of abradable coatings which are used to soften the direct contact between interacting components. Our numerical tool couples an explicit timestepping procedure to a plastic constitutive law that approximates wear. First results show that the developed model provides understandable and consistent physical results and is consequently fully reliable and may be used for further investigations with friction. They also exhibit unexpected complex behaviors of the blade. It seems that by opening the operating clearance between the blade tip and the casing, larger motions may be ex-pected far from the usual interaction conditions provided by the well-known Campbell diagrams.

In order to better estimate the wear parameter, comparisons with experimental results such as the ones presented in [START_REF] Padova | Casing treatment and blade tip configuration effects on controlled gas turbine blade tip/shroud rubs at engine conditions[END_REF][START_REF] Peyraut | Finite element modeling of abradable materials -identification of plastic parameters and issues on minimum hardness against coating's thickness[END_REF] have to be scheduled in a near future. Other approaches in the form of frequency-domain formulated nonlinear normal modes may be relevant for faster parameter studies [START_REF] Laxalde | Non-linear modal analysis for bladed disks with friction contact interfaces[END_REF].

Figure 1 -

 1 Figure 1 -Low pressure compressor. Courtesy of CFM International

1 )Figure 2 -

 12 Figure 2 -Blade under investigation with the three boundary nodes undergoing contact constraints and fixed displacement boundary conditions

Figure 3 -

 3 Figure 3 -Numerical profile of blade at CB interface node

Figure 4 -

 4 Figure 4 -System configuration at time t

Figure 5 -

 5 Figure 5 -Definition of the plasticity constitutive law for low () and high ( )

Illustration 9 Figure 6 -Figure 7 -Figure 8 -

 9678 Figure 6 -Final abradable profiles for different densities and a low rotational velocity after ten rounds of the blade

Figure 9 -

 9 Figure 9 -First five natural modes of the blade

Figure 10 -Figure 11 - 5 . 4 Figure 12 -Figure 13 -

 1011541213 Figure 10 -Map of the final abradable profiles with respect to Ω at interface node 1 with low ductility after ten rounds of the blade

Figure 14 -|FFTFigure 15 -

 1415 Figure 14 -Spectrum of the blade response for low ductility. The first natural frequency of the blade is indicated in red

In other words, x is here limited to a known set of interface dof and can be seen as a set of fixed indices.

These conditions written in a vector form have to be read coordinate by coordinate for each interface dof where contact is treated.

Plasticity being handled in a quasi-static framework, the usual time derivative notation is replaced by a quasistatic form such as • becomes ∆•.

Other configurations with a more general shape of the casing are of great interest too in which case k = 1, 3, . . .

Acknowledgement

Thanks go to Snecma for its technical and financial support. This work takes place in the framework of the MAIA mechanical research and technology program sponsored by CNRS, ONERA and SAFRAN Group.


Derya Malak
email: derya.malak@eurecom.fr

Weighted Graph Coloring for Quantized Computing

We consider the problem of distributed lossless computation of a function of two sources by one common user.

To do so, we first build a bipartite graph, where two disjoint parts denote the individual source outcomes. We then project the bipartite graph onto each source to obtain an edge-weighted characteristic graph (EWCG), where edge weights capture the function's structure, by how much the source outcomes are to be distinguished, generalizing the classical notion of characteristic graphs. Via exploiting the notions of characteristic graphs, the fractional coloring of such graphs, and edge weights, the sources separately build multi-fold graphs that capture vector-valued source sequences, determine vertex colorings for such graphs, encode these colorings, and send them to the user that performs minimum-entropy decoding on its received information to recover the desired function in an asymptotically lossless manner. For the proposed EWCG compression setup, we characterize the fundamental limits of distributed compression, verify the communication complexity through an example, contrast it with traditional coloring schemes, and demonstrate that we can attain compression gains higher than %30 over traditional coloring.

I. INTRODUCTION

Over the past years, we have been experiencing an everincreasing demand for computationally-intensive tasks, motivating us to devise new parallel processing techniques to speed up and efficiently distribute computations across groups of servers. In modern distributed computing, a primary concern is communication cost. While parallel processing to distribute communication can reduce the need for coordination and alleviate this cost, reduction of the same communication cost is challenged due to issues of scalability [START_REF] Soleymani | Analog lagrange coded computing[END_REF], accuracy [START_REF] Wang | Price of precision in coded distributed matrix multiplication: A dimensional analysis[END_REF], low capacity edges [START_REF] Ho | A random linear network coding approach to multicast[END_REF], and stragglers [START_REF] Behrouzi-Far | Efficient replication for straggler mitigation in distributed computing[END_REF] in distributed computing.

A. Related Work

Distributed coded computation. There have been various efforts to mitigate the communication cost in distributed computing following Yao's seminal work in [START_REF] Yao | Some complexity questions related to distributive computing (preliminary report)[END_REF] on communication complexity. Some recent breakthroughs in this direction include coded computing [START_REF] Yu | Lagrange coded computing: Optimal design for resiliency, security, and privacy[END_REF]- [START_REF] Prakash | Coded computing for distributed graph analytics[END_REF], and distributed computation of, e.g., matrix products [START_REF] Jia | On the capacity of secure distributed batch matrix multiplication[END_REF]- [START_REF] Chen | GCSA codes with noise alignment for secure coded multi-party batch matrix multiplication[END_REF], matrix multiplication with stragglers [START_REF] Li | Flexible constructions for distributed matrix multiplication[END_REF], and linearly separable functions [START_REF] Khalesi | Multi-user linearly-separable distributed computing[END_REF]- [START_REF]On secure distributed linearly separable computation[END_REF].

Distributed source and functional compression. Other attempts have been inspired from the seminal work of Slepian-Wolf [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] on distributed source compression, the ratedistortion coding models of Wyner-Ziv with side information [START_REF] Wyner | The rate-distortion function for source coding with side information at the decoder[END_REF], and for lossy source coding [START_REF] Yamamoto | Wyner-Ziv theory for a general function of the correlated sources[END_REF], toward function computation. These works include [START_REF] Orlitsky | Coding for computing[END_REF]- [START_REF] Feizi | On network functional compression[END_REF] that consider Funded by the European Union (ERC, SENSIBILITÉ, 101077361). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. function computation over networks, as well as [START_REF] Feizi | On network functional compression[END_REF] and [START_REF] Doshi | Source coding with distortion through graph coloring[END_REF], considering the generalization to functional rate-distortion, and [START_REF] Basu | Hypergraph-based source codes for function computation under maximal distortion[END_REF] and [START_REF]Functional epsilon entropy[END_REF], focusing on hypergraph-based source coding and function approximation under maximal distortion. Recent works also include hyperbinning for distributed function quantization [START_REF] Malak | A distributed computationally aware quantizer design via hyper binning[END_REF], generalizing the orthogonal binning ideas in Slepian-Wolf coding [START_REF] Cover | A proof of the data compression theorem of Slepian and Wolf for ergodic sources (corresp.)[END_REF], and fractional coloring-based distributed computation [START_REF] Malak | Fractional graph coloring for functional compression with side information[END_REF] that reduces complexity of [START_REF] Körner | Coding of an information source having ambiguous alphabet and the entropy of graphs[END_REF].

Coding for specific functions and channels. The communication cost is also affected by the nature of the computed function. Examples include Körner-Marton' encoding problem for computing modulo-two sum of binary sources [START_REF] Körner | How to encode the modulo-two sum of binary sources (corresp.)[END_REF], the generalization of Körner-Marton's problem to a two-terminal source coding scheme with common sum reconstruction [START_REF] Adikari | Two-terminal source coding with common sum reconstruction[END_REF], which has applications in distributed stochastic gradient descent, and Max-Lloyd's algorithms [START_REF] Suresh | Distributed mean estimation with limited communication[END_REF] to compute large-scale averages. Han and Kobayashi have established necessary and sufficient conditions on functions such that the Slepian-Wolf region is optimal for distributed lossless computing [START_REF] Han | A dichotomy of functions F (X, Y) of correlated sources (X, Y)[END_REF]. The authors in [START_REF] Witsenhausen | The zero-error side information problem and chromatic numbers (corresp.)[END_REF]- [START_REF] Körner | Zero-error information theory[END_REF] have explored the combinatorial aspects of source coding to compress correlated sources separately or with decoder side information. The joint source-channel scheme of Cover, El Gamal, and Salehi uses the source correlations to achieve a collaborative gain and create channel input distributions adapted to the channel [START_REF] Cover | Multiple access channels with arbitrarily correlated sources[END_REF]. To that end, Nazer and Gastpar have devised designs for distributed computing over multiple access channels [START_REF] Nazer | Computation over multiple-access channels[END_REF], and structured coding [START_REF]Lattice coding increases multicast rates for gaussian multipleaccess networks[END_REF].

B. Overview and Contributions

We focus on distributed computing of a function of two jointly distributed finite alphabet sources at a user. We pose this problem as an edge-weighted characteristic graph (EWCG) compression problem. To do so, we build a bipartite graph 1 where two disjoint parts denote the individual source outcomes, and the edges capture the joint source distribution.

Our main contributions can be summarized as follows:

• Edge-weighted b-fold compression. We propose an EWCG encoding scheme to provide low-complexity compression for computing, where we describe the weights by the joint source distribution and the function. An EWCG is a fractionally colored characteristic graph built by each source as an edge-weighted projection of the bipartite graph (Sect. II).

To capture the unequal edge weights, the source devises b characteristic graphs (one graph per source coordinate, see [41, App. A]), where the edge weights in EWCG are quantized across these graphs (that we detail via Example 1).

In an EWCG, a vertex captures a b-fold, i.e., vector-valued, source value, and is given b colors out of a available colors, where b captures the quantization depth of each source. The edge weights are used to determine a, b, and the overlap of colorings for any vertex pair (Sect. III), upon which each source establishes and encodes the colorings of its EWCG. • Edge-weighted fractional chromatic entropy. The fractional chromatic number χ f -given by the limit in ( 13) in [41, App. A] -determines the communication complexity when the edges have unit weights. Using OR power graphs, we can exploit the gains in complexity through fractional coloring as the blocklength n tends to infinity [START_REF] Scheinerman | Fractional graph theory: a rational approach to the theory of graphs[END_REF]Ch. 3].

To that end, we generalize the definition of χ f via EWCGs to provide a lower communication complexity (Sect. III).

• Joint quantization and distributed functional compression via EWCGs. In the edge-weighted fractional coloring of vector-valued sources, b is the quantization depth. The encoding rates for EWCGs are lower versus traditional or fractional coloring of graphs because the higher the value of b is, the more refined the weights in an EWCG are, enabling a lower rate of compression per source coordinate. We characterize in (3) the number of disjoint colors between two vertices of an EWCG. We provide in Theorem 1 (Sect. III) the encoding rate for a b-fold fractional coloring of EWCGs. • Numerical experiments. Contrasting it with the existing techniques via an example, EWCG exhibits significant savings in communication complexity by taking into account the structures of the sources (via the Slepian-Wolf theorem [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]) and the function (via the edge weights).

C. Notation

For a random variable X with a finite alphabet X , P X denotes its probability mass function (PMF). Similarly, for variables X 1 and X 2 , P X1,X2 denotes the joint PMF. We denote the probability of an event A by P(A). Let the entropy function of a PMF p be h(p) =i p i log p i where the logarithm is in base 2, h(p) be the binary entropy function with parameter p, and H(X) = E[-log P X (X)] be the Shannon entropy of X. We denote by

X n 1 = X 11 , X 12 , . . . , X 1n ∈ X n 1 the length n sequence of X 1 sampled from an n-fold finite alphabet X n 1 . We let [N ] = {1, 2, . . . , N }, N ∈ Z + .
II. MODEL AND PROBLEM STATEMENT We pose the problem of distributed computation of a function f (X 1 , X 2 ) of the two sources X 1 and X 2 as a compression problem for the edge-weighted projections of a bipartite graph that captures P X1,X2 . For this partially distributed setting, we will devise an encoding scheme for EWCGs and quantify the sum rate for computing f (X 1 , X 2 ), by exploiting the notions of characteristic graphs and their entropy [START_REF] Orlitsky | Coding for computing[END_REF]- [START_REF] Feizi | On network functional compression[END_REF] and the concept of bipartite graph projection.

A. Bipartite Graph Representation

We construct a bipartite graph representation G f = (X 1 , X 2 , E) to compute the function f (X 1 , X 2 ), whose par-tition has the parts X 1 and X 2 , which correspond to the set of realizations of the sources X 1 and X 2 , respectively, and E denotes the set of edges of G f . The bipartite graph G f is derived from the joint distribution P X1, X2 , and E captures the correlation between X 1 and X 2 . More specifically, 1) The set of vertices X 1 and X 2 that partition G f are disjoint.

2) G f is a balanced bipartite graph with |X 1 | = |X 2 |, i.e., the two subsets of vertices have the same cardinality. 3) There is an edge between vertices u k ∈ X 1 and v l ∈ X 2 , i.e., (u k , v l ) ∈ E, if and only if

P(X 1 = u k , X 2 = v l ) > 0. 4) If u k ∈ X 1 and v l ∈ X 2 are connected, i.e., (u k , v l ) ∈ E,
and (v l , u k ) ∈ E, then the symmetry of the edges does not imply that both edges yield the same function outcome.

If G f is complete, it has |X 1 | • |X 2 |
edges and the number of distinct function outcomes is determined by the structure of f (X 1 , X 2 ). On the other hand, if G f is not connected, it may have more than one bipartition [START_REF] Chartrand | Chromatic Graph Theory[END_REF]. In that case, encoding of f (X 1 , X 2 ) is facilitated upon the extraction of the bipartition information. We note that the sources do not have the full knowledge of E, as determined by P X1,X2 , but only the weights jointly determined by P X1,X2 and f (X 1 , X 2 ). We assume that the edge weights are available, and can be learned via feedback, the study of which is left as future work.

B. Weighted Bipartite Graphs through Projections of G f

Source one X 1 observes a weighted projection of G f onto a graph -the X 1 projection of G f -denoted by G w X1 , and similarly for source two. For the EWCG of X 1 , given by G w X1 , the edge weight between u k1 , u k2 ∈ X 1 of G w X1 , denoted by w(u k1 , u k2 ), is set to be the weighted number of common neighbors in X 2 . Hence, the notion G w X1 generalizes the concept of the characteristic graph G X1 detailed in [41, App. A]. In this paper, we determine {w(u k1 , u k2 ), u k1 , u k2 ∈ X 1 } as

w(u k1 , u k2 ) = v l ∈X2: f (u k 1 ,v l )̸ =f (u k 2 ,v l ) k∈{k 1 ,k 2 } P X 1 ,X 2 (u k ,v l )>0 P X1,X2 ([u k1 , u k2 ], v l ) , (1)
where P X1,X2 ([u k1 , u k2 ], v l ) = k∈{k1,k2} P X1,X2 (u k , v l ). The idea is similar for determining w(v l1 , v l2 ) of G w X2 . Similarly, towards realizing the limits of compression, for the n-th power graph of G w X1 , namely G n,w X1 , the edge weight between the vertices

u n i , u n j ∈ X n 1 of G n,w X1 is given as w(u n i , u n j ) = v n l ∈X n 2 : f (u n i ,v n l )̸ =f (u n j ,v n l ) k∈{i,j} P X n 1 ,X n 2 (u n k ,v n l )>0 P X n 1 ,X n 2 ([u n i , u n j ], v n l ) .
We can note that for the standard construction G X1 of X 1 [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF], [START_REF] Körner | Coding of an information source having ambiguous alphabet and the entropy of graphs[END_REF], as detailed in [41, App. A], the edge weights satisfy

1 v l ∈X2 : k∈{k 1 ,k 2 } P X 1 ,X 2 (u k ,v l )>0, f (u k 1 ,v l )̸ =f (u k 2 ,v l ) >0 .
In distributed compression, exploiting the notion of jointly typical sequences, it is possible for the user to estimate the number of X n 2 sequences jointly typical with X n 1 given X n 1 . Hence, as a simplification of this paper's model in [START_REF] Soleymani | Analog lagrange coded computing[END_REF], while still generalizing G X1 , the weight w(u k1 , u k2 ) for u k1 , u k2 ∈ X 1 can be set as the number of common neighbors in X 2 :

v l ∈X2 1 k∈{k 1 ,k 2 } P X 1 ,X 2 (u k ,v l )>0, f (u k 1 ,v l )̸ =f (u k 2 ,v l ) . (2)
The edge weights in (1) affect the quantization of the source outcomes through a b-tuple of graphs, which we detail next.

III. MAIN RESULTS

In this section, we provide an achievable encoding and decoding approach for asymptotically lossless distributed computation of f (X 1 , X 2 ), which is based on projecting the bipartite graph G f onto EWCGs and compressing the EWCGs.

A. Valid Colorings of Edge-Weighted Graphs

In traditional coloring of an unweighted graph G X1 , we note that given a pair of vertices u k1 , u k2 ∈ X 1 such that w(u k1 , u k2 ) = 0, it implies that the two vertices can have

identical colors c G X 1 (u k1 ) = c G X 1 (u k2 ). On the other hand, w(u k1 , u k2 ) > 0 implies c G X 1 (u k1 ) ̸ = c G X 1 (u k2 ).
In fractional coloring of EWCGs, prior to a valid coloring of vertices of G w X1 and G w X2 , we normalize each weight in (1) by max {w(u k1 , u k2 ), u k1 , u k2 ∈ X 1 }, and similarly for {w

(v l1 , v l2 ), v l1 , v l2 ∈ X 2 } of G w X2 . We next let c f G w X 1
(u k1 ), u k1 ∈ X 1 be a valid fractional coloring with a b-fold coloring, where u k1 is assigned b colors out of a available colors. Note that the distance between colors

c f G w X 1 (u k1 ) and c f G w X 1 (u k2 ), i.e., dist(c f G w X 1 (u k1 ), c f G w X 1 (u k2 )),
is an increasing function of w(u k1 , u k2 ) [START_REF] Toivonen | Compression of weighted graphs[END_REF]. To that end, we stretch Defns. ( 1) and ( 2) in [41, App. A] of the standard a : b coloring, and adopt the following model. As in traditional coloring, for a given u k1 , u k2 ∈ X 1 , when w(u k1 , u k2 ) = 0, then the b-

fold colors c f G w X 1 (u k1 ) and c f G w X 1 (u k2 ) could be identical, i.e., dist(c f G w X 1 (u k1 ), c f G w X 1 (u k2 )) = 0. On the other hand, when w(u k1 , u k2 ) = 1, then the b-fold col- ors c f G w X 1 (u k1 ) and c f G w X 1 (u k2 ) can have no overlaps, i.e., dist(c f G w X 1 (u k1 ), c f G w X 1 (u k2 )) = b. More generally, a valid a : b coloring of G w
X1 is such that given w(u k1 , u k2 ), the minimum number of disjoint colors between u k1 and u k2 of

G w X1 is dist(c f G w X 1 (u k1 ), c f G w X 1 (u k2 )) = ⌈w(u k1 , u k2 ) • b⌉ , (3)
meaning that if w(u k1 , u k2 ) ∈ b-(k+1) b , b-k b for k ∈ {0} ∪ [b -1],
then vertices u k1 and u k2 are assigned b -k distinct colors, and only if w(u k1 , u k2 ) = 0 they are assigned exactly the same b colors. We note that the number of different colors between two vertices of G w X1 changes as a function of the edge weight, as given in (3). The neighboring vertices in G w

X1i have at least one different color, and the endpoints of edges with large weights have a higher number of disjoint colors. Clearly, this coloring scheme generalizes the notion of fractional chromatic number (Defn. 2 in [41, App. A]).

We next expand G w X1 into a b-tuple of graphs represented by G w X1(S) = {G w X1i : i ∈ S, |S| = b}, where G w X1i , i ∈ S is an i-th replica of G w X1 . We jointly color the set of graphs G w X1(S)

such that c G X 1 (S) (X 1 (S)) = {c G w X 1i (X 1i ) : i ∈ S, |S| = b} and w(u k1 , u k2 ) = 1 b i∈S w i (u k1 , u k2 ) is split such that w i (u k1 , u k2 ) (4) = min 1, max b • w(u k1 , u k2 ) -b i-1 i ′ =1 w i ′ (u k1 , u k2 ), 0
denotes the weight between u k1 and u k2 of G w X1i , i ∈ S, i.e., the i-th replica of G w X1 . Note that (4) yields a sequence of monotone decreasing edge weights w i (u k1 , u k2 ) for i ∈ S that jointly determine the traditional colorings for the set of graphs G w X1(S) . In Fig. 1, we show a joint coloring for an example |S| = 2-tuple EWCG. We will detail this example in Sect. III-C to indicate the achievable gains in compression.

We next explore the fundamental rate limits for distributed computing of f (X 1 , X 2 ), by exploiting the notions of characteristic graph entropy, and EWCGs, where we determine the weights according to (4), following the bipartite projection scheme. To that end, we next detail encoding and decoding of G w X1 for asymptotically lossless compression of f (X n 1 , X n 2 ).

B. An Achievable Coloring Scheme for Edge-Weighted Graphs

In this part, we detail the encoding and decoding principle of EWCGs for distributed computing of f (X 1 , X 2 ). We next describe the encoding of b-fold colors. Note that the computation of f is lossless independent of the value of b ∈ Z + . a) Encoding: Given G f , the encoding phase includes the projections of G f onto G w X1 and G w X2 by determining the corresponding edge weights using (1) followed by their normalization. Each source then builds a b-tuple of characteristic graphs, G w X1(S) and G w X2(S) , respectively, for |S| = b. The sources can then compress their weighted graphs asymptotically at rates

H f G w X 1 (X 1 ) and H f G w X 1 (X 2 )
, where we next give the conditional fractional graph entropy of the EWCG G w X1 . Theorem 1. The fractional graph entropy of G w X1 is equal to

H f G w X 1 (X 1 | X 2 ) = lim n→∞ 1 n inf b 1 b min c f G n,w X 1 {H(c f G n,w X 1 (X 1 )) : c f G n,w X 1 (X 1 ) is a valid a : b coloring of G n,w X1 | X 2 } , (5)
where

c f G n,w X 1 (X 1 ) is a fractional coloring variable for G n,w X1 with an a : b coloring of each vertex of G n,w X1 . Proof. A proof sketch is given in [41, App. B].
b) Decoding: For lossless decoding, the user needs to be instructed on P X1,X2 , f , b, and the look-up table for recovering f (X n 1 , X n 2 ) using the received fractional colorings of the b-tuple of graphs from each source. The user first performs minimum-entropy decoding on its received information [START_REF] Csiszár | Information theory: coding theorems for discrete memoryless systems[END_REF]. Via Slepian-Wolf decoding, it achieves the sequences

c f G n,w X 1 (X 1 ) and c f G n,w X 2 (X 2 ) that model the b-fold color tuples.
The user then uses a look-up table to compute f (X n 1 , X n 2 ). To demonstrate the procedure for encoding and decoding of an EWCG G w X1 , determining the edge weights in (4), and We present an example to illustrate how to build an EWCG and how to encode and decode the coloring, to obtain the desired function outcomes. Through this example, we also contrast the performance of our scheme with that of traditional graph coloring that does not exploit the weight information.

Example 1. An EWCG and its chromatic entropy. The source variables X 1 and X 2 share a common alphabet such that X = {-2, -1, 0, 1, 2}. The ordered marginal PMFs are X 1 ∼ p 1 = (0.2, 0.15, 0.32, 0.24, 0.09) and X 2 ∼ p 2 = (0.2, 0.3, 0.32, 0.08, 0.1), and P X1,X2 is given as follows:

We note that the entropy of X 1 satisfies H(X 1 ) = h(0.2, 0.15, 0.32, 0.24, 0.09) = 2.2078 < H(X 1,u ) = 2.32, with X 1,u ∼ P X1,u , where P X1,u is uniform over X . Unweighted scenario. Without taking into account the edge weights, the minimum entropy coloring of G X1 is given as H(c G X 1 ) = h(0.44, 0.47, 0.09) = 1.35. The entropy with a 5 : 2 fractional coloring with χ f (G X1 ) = 2.5 satisfies

Fig. 1 .

 1 Fig.1. Distributed computation of f (X 1 , X 2 ): an end-to-end multi-fold encoding and decoding scheme for EWCGs. The encoding phase consists of determining the EWCG tuples and their colorings, followed by Slepian-Wolf encoding on the b-fold colors. Decoding relies on recovering the b-fold colors using Slepian-Wolf decoding followed by recovering the outcomes using a look-up table. We note that P X 1 = (0.2, 0.15, 0.32, 0.24, 0.09), and the edge weights are given in Example 1. In the bottom figure, the graph encoder for each source is independent -output is a b-tuple color sequence -with Slepian-Wolf encoding. In this example, the user uses 4 fractional colors received (b = 2 from each source per transmission) to reconstruct the function outcome.

Important classes of bipartite networks are the collaboration network and the opinion network. They are significant in information and economic systems, social networks, opinion networks and recommendation systems[START_REF] Zhou | Bipartite network projection and personal recommendation[END_REF].

) = 1 2 log 5 = 1.16, and for X 1,u uniform, 1 4

) = 1 4 log 13 = 0.92. Weighted scenario. We next take into account the edge weights. Using (1), the edge weights are w(-2, -1) = 0.2, w(-2, 0) = 0.3, w(0, 1) = 0.32, w(1, 2) = 0.08, and w(-1, 2) = 0.1. Note that for this specific example, W ∼ p 2 .

We next decompose G w X1 into b = 2 graphs, as shown in Fig. 1 (top row). Normalizing the edge weights, and then using (4), the weights are w 1 (-2, -1) = w 1 (-2, 0) = w 1 (0, 1) = 1, w 1 (1, 2) = 0.5, and w 1 (-1, 2) = 0.625 for G w X11 , and w 2 (-2, -1) = 0.25, w 2 (-2, 0) = 0.875, w 2 (0, 1) = 1, and w 2 (1, 2) = w 2 (-1, 2) = 0 for G w X12 . This yields a valid 5 : 2 coloring of G w X1(S) for |S| = 2, as also shown in the top row. Using the joint coloring information of G w X1(S) , i.e., for G w X11 and G w X12 , the color PMF for the 5 : 2 fractional coloring of G w X1 for the set of ordered colors {c 1 = Blue, c 2 = Orange, c 3 = Green, c 4 = P urple, c 5 = Y ellow} satisfies

which yields from (5) that

Hence, for b = 2, capturing the edge weights yields a saving of %16 over traditional coloring and does not offer enhancement over standard fractional coloring. For the same example, with b = 3 and with the inclusion of a sixth color, where c 6 = V iolet, we can achieve a 6 : 3 coloring as shown in Fig. 2, and the coloring PMF is

Then, a valid 6 :

) = 0.85, providing a saving of %37 over traditional coloring. Hence, a larger b can capture the edge weights more accurately.

We next consider the second power graph G 2,w X1 . We note that χ f (G w X1 ) = 2.5, and

) = 1.34. Hence, capturing the edge weights yields a saving of %32 over traditional coloring, and does not have much gain over the fractional coloring approach that does not capture the weights. Increasing b allows us to capture the edge weights more accurately. Similarly, we can determine the compression rate for general n. Exploiting [START_REF] Scheinerman | Fractional graph theory: a rational approach to the theory of graphs[END_REF]Cor. 3.4.3], χ(G n X1 ) ≈ χ n f (G X1 ) as n goes to infinity. Hence, we can derive the n-th power graph, G n,w X1 , along with its a : b fractional coloring, c f G n,w X 1 (X 1 ).

From Example 1, as b increases, we have a finer-grained quantization of the graph edge weights. As the skew of the edge weights increases, the efficiency in compressing the btuples of G w X1 increases (e.g., in Fig. 1 some edges have relatively low weights, e.g., w(1, 2) = 0.08, and w(-1, 2) = 0.1, yielding a fewer number of distinct colors between these two end vertices). As the value of b increases, the edge weights will be captured with greater precision, leading to a more refined fractional coloring (more skewed) and a reduced total number of colors and smaller graph entropy H f G w X 1 (X 1 ) given by [START_REF] Yao | Some complexity questions related to distributive computing (preliminary report)[END_REF]. When the total bit budget for quantization and compression is limited, there is a tradeoff between b that determines the fold of coloring, and the complexity of encoding the characteristic graph. That is, the number of bits spent on quantizing the edge weights determines the attainable gains in compression.