Jean-David Benamou

Brittany Froese

Adam Oberman

J.-D Benamou

Numerical solution of the second boundary value problem for the Elliptic Monge-Ampère equation

Keywords: Optimal Transportation, Monge-Ampère Equation Transport Optimal, Equation de Monge-Ampère

This paper introduces a numerical method for the solution of the nonlinear elliptic Monge-Ampère equation. The boundary conditions correspond to the optimal transportation of measures supported on two domains, where one of these sets is convex. The new challenge is implementing the boundary conditions, which are implicit and non-local. These boundary conditions are reformulated as a nonlinear Hamilton-Jacobi PDE on the boundary. This formulation allows us to extend the convergent, wide stencil Monge-Ampère solvers proposed by Froese and Oberman to this problem. Several non-trivial computational examples demonstrate that the method is robust and fast.

1. Introduction 1.1. Numerical Optimal transportation 1.2. Discussion of numerical methods for Optimal Transportation 1.3. Our approach to the numerical treatment of (HJ) 1.4. Discussion of OT and OT numerics 1.5. Discussion of Optimal Transportation 1.6. Applications of OT 2. Representation and approximation of (HJ) 2.1. Representation and properties of the distance function 2.2. Representation of the target set 2.3. Obliqueness 2.4. Monotone discretization of H 3. Convergence 3.1. General discussion of numerical methods 3.2. Convergence of approximation schemes 3.3. Discretization of Monge-Ampère equation 3.4. Proof of convergence 4. Solution methods 4.1. Explicit iteration 4.2. Newton's method Date: June 4, 2012.

1. Introduction 1.1. Numerical Optimal transportation. The paper introduces a numerical method for the solution of the fully nonlinear elliptic Monge-Ampère equation for a convex potential u :

(MA) det(D 2 u(x)) = ρ X (x) ρ Y (∇u(x))
for x ∈ X.

Here, D 2 u is the Hessian and ∇u the gradient of the function u : X ⊂ R d → R. The equation arises from the Monge-Kantorovitch problem where the map ∇u, from the probability density ρ X supported on X to the probability density ρ Y supported on Y ⊂ R d , minimizes a transportation cost (see subsection 1.5). We require that X, Y are convex and bounded. Our method will allow ρ X to vanish, but requires Lipschitz continuity of ρ Y .

The usual boundary conditions are replaced by a state constraint on the gradient map from X to Y , (BV2) ∇u(X) = Y This condition is referred to in the literature as the second boundary value problem for the Monge-Ampère equation [START_REF] Pogorelov | Generalized solutions of Monge-Ampère equations of elliptic type, A tribute to Ilya Bakelman[END_REF].

The main idea in this paper is to replace (BV2) by a Hamilton-Jacobi equation on the boundary :

(HJ) H(∇u(x)) = dist(∇u(x), ∂Y ) = 0, for x ∈ ∂X where we use the signed distance function to the boundary of the set Y as the Hamiltonian H. The problem at hand now is (MA-HJ), and solving this combined problem requires several theoretical and numerical ideas. First, we use convexity of the solution to demonstrate obliqueness of the boundary condition. This obliqueness condition ensures that H can be discretized using information inside the domain (upwinding). The upwind discretization gives a monotone and consistent scheme on the boundary. Together with a consistent and monotone scheme for (MA) inside the domain, we obtain convergence for the combined discretization of (MA-HJ) using the approximation framework of Barles-Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF]. Using the work of [START_REF]Convergent almost monotone finite difference approximations for viscosity solutions of the elliptic monge-ampère partial differential equation[END_REF], we also extend this framework to allow for more accurate (or nearly monotone) approximations. 1.2. Discussion of numerical methods for Optimal Transportation.

To the best of our knowledge, there was previously no method available for implementing the condition (BV2) together with (MA) and, indeed, previous works have restricted their attention to geometries/boundary conditions where it can be simplified.

A first and widely used simplification is to work on the torus (with periodic densities) using the change of variable u = Id + v (v is periodic). However, this severely restricts the range of solvable problems. Mass transfer between periodic cells may be optimal. There is no easy way to prevent it and capture the optimal transportation for the one cell non-periodic problem.

A second option for designing optimal transportation-compatible boundary conditions is to restrict attention to fixed simple geometries. For example, when dealing with square to square maps, e.g. X = Y = [0, 1] × [0, 1] and denoting by (x, y) the cartesian coordinates, the Neumann boundary condition ∂ x u| {x=0,1} = {0, 1}, ∂ y u| {y=0,1} = {0, 1} yields a face to face mapping on the boundary, which is optimal when mass does not vanish. Note that Neumann BCs prescribe only one component of the gradient map, thus leaving the map free to stretch or contract in the tangential direction.

An idea to treat more general density geometries would be to extend the density support to a square and pad with zeros, but numerical methods for (MA) are not able to treat vanishing densities in the target space Y . Mollifying and adding constant mass everywhere can significantly modify the optimal map.

In [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF], a more general heuristic method is proposed, consisting in iteratively solving (MA) with Neumann boundary conditions, and projecting the resulting set onto the target set Y . The new projection is then used to derive new Neumann boundary conditions. This method required several iterations, and no convergence proof was available.

1.3. Our approach to the numerical treatment of (HJ). The current work treats the boundary condition naturally, admits a convergence proof, and allows the equation to be solved quickly: at the same cost as solving the Dirichlet problem, and at a cost equivalent to several linear solves on the same grid. The projection method proposed in [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF], mentioned above, can be interpreted as a gradient descent solution method for (HJ).

We use a reformulation of (BV2) for which a convergent monotone finite difference scheme, consistent with the treatment of the PDE (MA), can be easily built and incorporated into a fast Newton solver. It is based on the concept of defining function used in [START_REF] Delanoë | Classical solvability in dimension two of the second boundaryvalue problem associated with the Monge-Ampère operator[END_REF][START_REF] Urbas | On the second boundary value problem for equations of Monge-Ampère type[END_REF] precisely to prove the existence of classical solutions for (MA-BV2). To summarize the idea: a convex function H defined on the whole space R d , which the target set Y , is a defining function for the set Y if the zero level set of H coincides with ∂Y . Such a function is easy to construct and compute; in this paper we use the signed distance function to the boundary of the set Y . As X, Y are convex, the second boundary value condition (BV2) is then equivalent to the nonlinear but local boundary condition:

(HJ) H(∇u(x)) = 0, for x ∈ ∂X.

The problem at hand now is (MA-HJ), and we show that it is tractable using the classical viscosity approximation theory.

1.4. Discussion of OT and OT numerics. We recall that the term "second boundary value" was proposed in the pioneering work of Pogorelov [START_REF] Pogorelov | Generalized solutions of Monge-Ampère equations of elliptic type, A tribute to Ilya Bakelman[END_REF]. Pogorelov's constructive method for solving Monge-Ampère assumes a target density ρ Y in the form of a (possibly weighted) sum of Dirac masses at prescribed supporting points in the target space. He then constructs the convex potential solution u as a supremum of affine functions whose gradients/slopes necessarily take values in the finite set of supporting points. The support domain of u, X, is split into cells supporting the contribution of each affine function to the solution. Adjusting the constant/height of these affine functions, one can increase or decrease their sizes in order to satisfy the Jacobian equation. In this framework, the "second boundary value" problem arises as a natural and easy to treat constraint instead of the usual "first" Dirichlet boundary conditions. The theory for Neumann and more general oblique boundary conditions is more technical and was addressed later; see [START_REF] Lions | The Neumann problem for equations of Monge-Ampère type[END_REF]. Pogorelov solutions also provide examples of weak solutions, as the gradient map is discontinuous.

A similar idea has been pursued numerically in the contexts of meteorology [START_REF] Cullen | An extended Lagrangian theory of semigeostrophic frontogenesis[END_REF], antenna design [START_REF] Glimm | Optical design of single reflector systems and the Monge-Kantorovich mass transfer problem[END_REF], and more recently by in image processing [START_REF] Merigot | A multiscale approach to optimal transport[END_REF]. In this context, optimal mass transfer is a linear programming problem. When the initial density is also a sum of Diracs, the popular auction algorithm proposed by Bertsekas (see the survey paper [Ber92]) solves it with O(N 2 log N ) complexity. In [START_REF] Bosc | Numerical approximation of optimal transport maps[END_REF], the author compares different linear programming approaches and discusses the non-trivial issue of quantization (discretization of densities towards sum of Diracs), which is necessary to treat more general mass transfer problems.

The other (large) family of numerical iterative methods uses gradient flows combined with a linearization of the optimal mass transfer problem (which boils down to a linear second order elliptic equation). It can be solved either by deterministic [CDF11, DAT08, HRT10] or stochastic [START_REF] Maury | Handling congestion in crowd motion modeling[END_REF] methods. These approaches lack a convergence theory. A provably convergent method is the CFD (Computation Fluid Dynamics) reformulated optimal transportation "time" problem [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF], which relaxes the nonlinearity of the constraints at the cost of an additional virtual time dimension. Classical efficient numerical optimization methods may also be used: Augmented Lagrangian [BB00] and classical optimal control methods where the gradient of the functional is computed by a direct/adjoint system of PDEs [START_REF] Benamou | Mixed L 2 -Wasserstein optimal mapping between prescribed density functions[END_REF][START_REF] Lachapelle | Computation of mean field equilibria in economics[END_REF]. Solving the Monge-Ampère equation using a Newton's method as in [START_REF] Loeper | Numerical solution of the Monge-Ampère equation by a Newton's algorithm[END_REF][START_REF] Khouider | An efficient numerical algorithm for the l2 optimal transport problem with applications to image processing[END_REF] may also be counted in this class of numerical methods.

The optimal transportation problem for general cost functions can be formulated as a Linear Programming problem. However, this requires doubling the dimension of the problem and using LP solvers, which scale poorly for large problems sizes, compared to PDE methods. An implementation of the LP solution method can be found in [START_REF] Rüschendorf | Numerical and analytical results for the transportation problem of Monge-Kantorovich[END_REF].

1.5. Discussion of Optimal Transportation. Our interest in (MA-BV2) is linked to the Monge Kantorovitch or optimal transportation or optimal mass transfer problem in the case of quadratic cost :

(1) inf

M ∈M 1 2 X x -M (x) 2 ρ X (x)dx (2) M = {M : X → Y, ρ Y (M ) det(∇M ) = ρ X }.
In [START_REF] Brenier | Polar factorization and monotone rearrangement of vectorvalued functions[END_REF], it is proved that (1-2) is well posed and that the unique map M at which the minimum is reached is the gradient of a convex potential u, which is therefore also unique up to a constant. The correspondence with (MA-BV2) is then formally straightforward: just replace M by ∇u in the constraints (2). The mass transfer problem can be seen as a variational formulation of the second boundary value problem and has been a important tool in understanding well-posedness and regularity or lack of regularity of Monge-Ampère solutions. In particular, sensitive conditions for the existence of globally smooth solutions are the convexity of the sets X and Y and the strict positivity of the densities [START_REF] Caffarelli | Boundary regularity of maps with convex potentials[END_REF].

1.6. Applications of OT. The problem of optimal mass transport arises in a large number applications including image registration [START_REF] Haker | Optimal mass transport for registration and warping[END_REF], mesh generation [START_REF] Budd | Moving mesh generation using the parabolic Monge-Ampère equation[END_REF], reflector design [START_REF]Optical design of single reflector systems and the Monge-Kantorovich mass transfer problem[END_REF], astrophysics (estimating the shape of the early universe) [START_REF] Frisch | A reconstruction of the initial conditions of the universe by optimal mass transportation[END_REF], and meteorology [START_REF] Cullen | Generalised Lagrangian solutions for atmospheric and oceanic flows[END_REF]. Motivated by economic applications, Kantorovich contributed1 to the understanding of optimal transport by reformulating the problem as a linear program and describing a simple dual formulation [START_REF] Kantorovich | On the transfer of masses[END_REF][START_REF]On a problem of Monge[END_REF]. While this has made many theoretical questions easier to answer, this approach also effectively doubles the dimension of the problem. Consequently, computing the solution to even a small-scale problem is prohibitively expensive.

A large class of nonlinear continuity equations with confinement and/or possibly non local interaction potentials can be considered as semi-discrete gradient flows, known as JKO gradient flows [START_REF] Jordan | The variational formulation of the Fokker-Planck equation[END_REF][START_REF] Otto | The geometry of dissipative evolution equations: the porous medium equation[END_REF], with respect to the Euclidean Wasserstein distance. The distance is the value function of the Optimal transportation problem. Again, the cost of its numerical resolution, let alone computing the gradient (with respect to one of the densities), has so far prevented the numerical use of this technique. In 1D the problem is trivial and [START_REF] Kinderlehrer | Approximation of parabolic equations using the Wasserstein metric[END_REF] implements JKO gradient flow simulations for nonlinear diffusion. An interesting recent work [START_REF] Carrillo | Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms[END_REF] starts attacking the 2D case.

The performance of our solver offers new perspectives for implementing JKO gradient flows.

Representation and approximation of (HJ)

We now describe the numerical approach to solving the second boundary value problem (BV2). We implement the boundary condition using the signed distance function to the boundary of the set Y . We are able to treat the boundary condition using a monotone finite difference scheme, which is consistent with the treatment of the PDE (MA).

Remark 2.1. It is now common to use a distance function to determine a set, as is the case in the level set method. In this case, one solves a Hamilton-Jacobi equation for the distance function. What we are doing here is to use the distance function as the nonlinear PDE operator.

The resulting boundary conditions are implicit, in contrast to, for example, Dirichlet or Neumann boundary conditions, which have been previously implemented for (MA). However, at each grid point the boundary condition can be treated as an implicit equation in a similar manner to how the interior grid points are treated: in our case, with a Newton solver.

2.1. Representation and properties of the distance function. The unsigned distance function can be represented as dist(y, ∂Y ) = inf y 0 ∈∂Y yy 0 , but since it is not convex, it is not suited to our purposes. For a bounded, convex set Y , the signed distance function,

H(y) = + dist(y, ∂Y ), y outside of Y -dist(y, ∂Y ), y inside Y
is convex and can be written in terms of the supporting hyperplanes to the convex set,

(3) H(y) = sup

y 0 ∈∂Y {n(y 0 ) • (y -y 0 )} ,
where n(y 0 ) is the outward normal to ∂Y at y 0 ; see Figure 1. Equivalently, since the image of the normals to ∂Y is the unit sphere, we can write (4)

H(y) = sup n =1 {n • (y -y(n))}
where y(n) is the point in ∂Y with normal n. This last representation is useful for computationally determining these values from a given representation of the target set; see subsection 2.2. The last representation is also valid in the case where the convex set is not smooth. These statements follow from the Supporting Hyperplane Theorem [BV04, Section 2.5], which says that if y 0 ∈ ∂Y , for a convex set Y , then y 0 has a (possibly non-unique) supporting hyperplane, where A(y) ≤ 0, for y ∈ Y . Without loss of generality, n = 1, and we can define n to be (an) outward normal to Y at y 0 . Then, we can define

P = {A(y) = 0 | A(y) ≡ n • (y -y 0 )},
H * (n) = n • y(n) = sup y∈∂Y n • y,
where the equality follows from the supporting hyperplane result. We have proven the following lemma.

Lemma 2.2. Let H be the signed distance function to a smooth, bounded set, Y . Then

H(y) = sup n =1 {y • n -H * (n)} where (5) H * (n) = sup y 0 ∈∂Y {y 0 • n}.
2.2. Representation of the target set. The target set Y may be represented by its convex hull, or simply by scattered points. In the latter case, we wish to obtain the representation (3). This can be accomplished using computational geometry, or even convex optimization [START_REF] Boyd | Convex optimization[END_REF]. We now describe a method for obtaining the representation (3) from scattered points, which is convenient to our purposes, using the Legendre-Fenchel transform [BV04, section 3.3].

In the implementation, we will further discretize this Hamilton-Jacobi equation by computing the supremum over a finite subset of the admissible directions. These direction vectors are typically given by a uniform discretization of the directions, with discretization parameter dα. We require only that dα → 0 for convergence.

We found this to be the simplest and computationally most efficient method to represent the geometry.

Even for an elliptical domain, where a large (hundreds, or on the order of the number of grid points on the perimeter) number of hyperplanes was needed to represent the convex set, this formulation was accurate and computationally inexpensive. This resulted from the fact that the hyperplanes (i.e. the values H * below) were precomputed. Evaluating (5) is inexpensive.

2.3. Obliqueness. We recall here a fundamental property of maps characterized as the gradient of a convex potential. In, [START_REF] Delanoë | Classical solvability in dimension two of the second boundaryvalue problem associated with the Monge-Ampère operator[END_REF][START_REF] Urbas | On the second boundary value problem for equations of Monge-Ampère type[END_REF] this obliqueness result is used to prove existence of classical solutions to (MA-BV2).

This condition, which leads to Lemma 2.4, will allow us to build an explicit monotone upwind discretization of (3), using points inside the domain. Lemma 2.3. Suppose X is a convex domain, and Y = ∇u(X) is the image of Y under the mapping ∇u, where u is a convex twice continuously differentiable function. Then the normal vectors make an acute angle,

∇u(X) = Y x y X n x n y Y n y = (D 2 u(x)) -1 n x
(6) n x • n y ≥ 0. See Figure 2.
Proof. Let ∇u(x) = y ∈ ∂Y and let H(y) = dist(y, ∂Y ) be the signed distance function to Y , so that

Y = {y | H(y) = 0} and X = {x | H(∇u(x)) = 0}.
Then n y = ∇H(y) and, by the chain rule for differentiation,

n x = c∇D 2 u(x)∇H(∇u(x)) = cD 2 u(x)∇H(y)
for a normalization constant, c. Thus

n x • n y = c(∇H(y)) T D 2 u(x)∇H(y) ≥ 0,
since convexity of u means D 2 u is positive definite.

Lemma 2.4. Let u ∈ C 2 (X) be any convex function that satisfies (BV2).

For any x ∈ ∂X with unit outward normal n x , the supremum in (HJ) can be restricted to vectors making an acute angle with n x :

(7) H(∇u(x)) = sup n =1 {∇u(x) • n -H * (n) | n • n x > 0} = 0.
Proof. The supremum above will be attained for a value of n = n * , which will be identical to the unit outward normal to the target at the point ∇u(x).

From Lemma 2.3, we know that n * • n x = n y • n x ≥ 0. Consequently, it is only necessary to check values of n that make an acute angle with the boundary of the domain.

Monotone discretization of H.

In this section we explain how to build a monotone discretization of H using points at the boundary and on the inside of the domain X.

The expression (7), which comes from writing the convex set Y in terms of its tangent hyperplanes, leads to a natural convergent finite difference discretization. This expression can be understood as a Hamilton-Jacobi-Bellman equation arising from a control problem.

We recall (see [START_REF]Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems[END_REF]) that an elliptic (monotone) discretization of H(∇u) at the point x i will take the form

H i (u(x i ) -u(x j ))
and be non-decreasing in each of its arguments.

If we let Γ i = {n | n • n x i > 0, n = 1}, a simple way of writing an upwind discretization is to approximate the signed distance function by

H(∇u(x i )) = sup n∈Γ i {∇u(x i )•n-H * (n)} ≈ sup n∈Γ i u(x i ) -u(x i -nh) h -H * (n)
where h is a small discretization parameter. As long as the domain is uniformly convex and h is sufficiently small, obliqueness ensures that the point x inh is inside the domain. However, this form does not lead to a simple, compact finite difference approximation. Instead, for simplicity, we describe the discretization on a square domain. We note that a slightly more complicated discretization will generalize this to more general triangulated domains. However, by padding the source density ρ X with zeros (see subsection 5.1), we can handle different geometries while still computing on a simple, square domain. We can also easily generalize the discretization to higher dimensions.

We describe the discretization along the left side of the square domain, with normal n x = (-1, 0). Along this side, the set of admissible directions will be given by {n = (n 1 , n 2 ) | n 1 < 0, n = 1}. Then, letting h denote the spatial resolution of the grid, we can approximate the advection terms by

∇u(x i ) • n ≈ n 1 u(x i + (h, 0)) -u(x i ) h + max{n 2 , 0} u(x i ) -u(x i -(0, h)) h + min{n 2 , 0} u(x i + (0, h)) -u(x i ) h .
This scheme only relies on values inside the square and, because n 1 < 0, it is monotone. Taking the supremum of these monotone schemes over all admissible directions, we preserve monotonicity of the scheme. We write a similar scheme on the other sides of the square. At corners, we take formal limits of the obliqueness constraint to limit the admissible directions to a single quadrant, which ensures that the required information will continue to reside inside the square.

Convergence

We begin with a review of background material that will be needed to construct and prove the convergence of our scheme for solving the second boundary value problem for the Monge-Ampère equation.

3.1. General discussion of numerical methods. The viscosity approximation theory developed by Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF] provides criteria for the convergence of approximation schemes: schemes that are consistent, monotone, and stable converge to the unique viscosity solution of a degenerate elliptic equation. This general framework can be applied to a wide class of nonlinear second order equations and, in particular, when the PDE operator is defined on the closure of the support domain and may be discontinuous. For the second boundary value problem the equations can be written using the abstract operator

(8) F (x, u(x), ∇u(x), ∇ 2 u(x)) = 0, x ∈ X
where F depends on ρ X , ρ Y and H:

(9) F (x, u, p, M ) = det(M ) -ρ X (x)/ρ Y (p), x ∈ X H(p), x ∈ ∂X.
Remark 3.1. For the Dirichlet problem, for example, we would write ug instead of H for x ∈ ∂X.

Note that H depends only on p; therefore, it will not affect the degenerate ellipticity of the whole problem cast in the discontinuous viscosity framework of [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF]. This abstract framework does not indicate how to build such schemes, or how to produce fast solvers for the schemes. It is not obvious how to ensure that schemes satisfy the required comparison principle. A class of schemes which for which this property holds was identified in [START_REF]Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems[END_REF], and were called degenerate elliptic, by analogy with the structure condition for the PDE.

For uniformly elliptic PDEs, monotone schemes are not always necessary for convergence (for example, most higher order finite element methods are not monotone). However, for fully nonlinear or degenerate elliptic equations, the only convergence proof currently available requires that schemes be (nearly) monotone. One way to ensure monotonicity is to use wide stencil finite difference schemes; this has been done for the equation for motion by mean curvature [START_REF] Oberman | A convergent monotone difference scheme for motion of level sets by mean curvature[END_REF], for the Infinity Laplace equation [START_REF]A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions[END_REF], for functions of the eigenvalues [START_REF]Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian[END_REF], for Hamilton-Jacobi-Bellman equations [BZ03], and for the convex envelope [START_REF]Computing the convex envelope using a nonlinear partial differential equation[END_REF]. Even for linear elliptic equations, a wide stencil may be necessary to build a monotone scheme [START_REF] Motzkin | On the approximation of linear elliptic differential equations by difference equations with positive coefficients[END_REF].

3.2.

Convergence of approximation schemes. The techniques we use to prove the convergence of our scheme are based on the framework for approximating viscosity solutions that was introduced by Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF]. A framework for the construction of convergent schemes for degenerate elliptic equation in general, and the Monge-Ampère equation in particular, has been further developed in [START_REF]Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems[END_REF][START_REF] Froese | Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher[END_REF][START_REF]Convergent almost monotone finite difference approximations for viscosity solutions of the elliptic monge-ampère partial differential equation[END_REF].

The key properties required to construct a scheme F that converges to the viscosity solution of the underlying PDE F are consistency and near ellipticity; these terms are recalled below. Definition 3.2 (Consistent). The scheme F is consistent with the equation F = 0 if for any smooth function φ and x ∈ Ω, lim sup →0,y→x,ξ→0

F (y, φ(y) + ξ, φ(•) + ξ) ≤ F * (x, φ(x), ∇φ(x), D 2 φ(x)), lim inf →0,y→x,ξ→0 F (y, φ(y) + ξ, φ(•) + ξ) ≥ F * (x, φ(x), ∇φ(x), D 2 φ(x)).
Definition 3.3 (Elliptic). The scheme F is elliptic if it can be written

F [v] = F (x, v(x), v(x) -v(•)),
where F is nondecreasing in its second and third arguments,

(10) s ≤ t, u(•) ≤ v(•) =⇒ F (x, s, u(•)) ≤ F (x, t, v(•))
Definition 3.4 (Nearly Elliptic). The scheme F is nearly elliptic if it can be written as

(11) F [v] = F M [u] + F P [u]
where F M is a monotone (elliptic) scheme and F P is a perturbation, which satisfies lim

→0 F P = 0.
Using these definitions, we now recall the main convergence theorem from [START_REF]Convergent almost monotone finite difference approximations for viscosity solutions of the elliptic monge-ampère partial differential equation[END_REF].

Theorem 3.5 (Convergence of Approximation Schemes). Let u be the unique viscosity solution of the PDE (8) and let u be a stable solution of the consistent, nearly elliptic approximation scheme (11). Then u → u, locally uniformly, as → 0.

Moreover, if the non-monotone perturbation F P is continuous, u exists and is stable.

In the same paper, the authors describe filtered approximation schemes, which combine a monotone (elliptic) scheme F M with a more accurate, nonmonotone scheme F A . These schemes, which are convergent, have the form

(12) F [u] = F M [u] + r( )S F A [u] -F M [u] r( )
where r( ) → 0 as → 0. Here the function S, which is called a filter, can be defined, for example, by

(13) S(x) =          x x ≤ 1 0 x ≥ 2 -x + 2 1 ≤ x ≤ 2 -x -2 -2 ≤ x ≤ -1.
See Figure 3.

1 2 3 -1 -2 -3 1 -1 x y y = S(x)
(D 2 u(x)) = ρ X (x)/ρ Y (∇u(x)) + u .
However, to reduce the cost of computations, we will replace the mean u with the value u(x 0 ) for some point x 0 ∈ X, which should coincide with a grid point. The solution to the two problems is the same up to an additive constant.

We first describe the elliptic (monotone) scheme for the Monge-Ampère operator, which underlies the filtered scheme. This scheme was developed in [START_REF] Froese | Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher[END_REF][START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF].

To begin, we use Hadamard's inequality to represent the determinant of a positive definite matrix, det(M ) ≤ Π i m ii , with equality when M is diagonal. Then, we can write

det(M ) = min Π i (O T M O) ii | O T O = I
where O is an orthogonal matrix. This last inequality, applied to the Hessian of a convex function, corresponds to taking products of second derivatives of the function along orthogonal directions,

det(D 2 u) ≡ min {ν 1 ...ν d }∈V d j=1 u ν j ν j ,
where V is the set of all orthonormal bases for R d .

In the special case where the source density ρ X vanishes, the Monge-Ampère operator reduces to the convex envelope operator [START_REF]The convex envelope is the solution of a nonlinear obstacle problem[END_REF][START_REF] Oberman | The dirichlet problem for the convex envelope[END_REF]. In this case, the operator enforces directional convexity in each direction, which is approximated by looking in grid directions [START_REF]Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian[END_REF][START_REF]Computing the convex envelope using a nonlinear partial differential equation[END_REF]. In order to enforce the convexity constraint, we need to replace the derivatives with their positive part. As well, to guard against the possibility of nonconvex solutions when the right-hand side vanishes, we will also subtract the negative parts of these second derivatives,

det + (D 2 u) ≡ min {ν 1 ...ν d }∈V    d j=1 max{u ν j ν j , 0} + d j=1 min{u ν j ν j , 0}    .
These modifications ensure that a non-convex function cannot solve our Monge-Ampère equation (with non-negative right-hand side) since it will lead to a negative value of the "convexified" Monge-Ampère operator. To discretize this, we limit ourselves to considering a finite number of vectors ν that lie on the grid and have a fixed maximum length; this is the directional discretization, which gives us the angular resolution dθ of our stencil (see Figure 4). In this figure, values on the boundary are used to maintain the directional resolution dθ (at the expense of lower order accuracy in space because the distances from the reference point are not equal). Another option is to narrower stencils as the boundary is approached, which leads to lower angular resolution, but better spatial resolution. We denote the resulting set of orthogonal vectors by G.

Each of the directional derivatives in the Monge-Ampère operator is then discretized using centered differences:

D νν u i = 1 ν 2 h 2 (u(x i + νh) + u(x i -νh) -2u(x i )) .
In order to handle non-constant densities, we also need to discretize the gradient. A simple approach to this is akin to the Lax-Friedrichs scheme, which involves adding a small multiple of the laplacian and discretizing with centered differences.

-ρ X /ρ Y (∇u) ≈ -ρ X /ρ Y (D x 1 u, . . . , D x d u) + δ d j=1 D x j x j u.
The centered difference discretization of the first derivatives is

D ν u i = 1 2h (u(x i + νh) -u(x i -νh)) .
To preserve monotonicity, we require the parameter δ to satisfy δ > Kh where K is the Lipschitz constant (with respect to y) of ρ X (x)/ρ Y (y).

Remark 3.6. In practice, we do not add a multiple of the laplacian, but instead absorb the parameter δ into the second-derivative operators that are already present in the equation. The gradient can then be discretized using centered differences along rotated coordinate frames, which correspond to the directions that are active in the Monge-Ampère operator. This approach, which is described in [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF], leads to sparser systems and improves the consistency error of the monotone scheme. These differences do not affect the convergence proof or the formal consistency error of the more accurate filtered scheme.

Then an elliptic discretization of the Monge-Ampère equation is

(14) M A h,dθ,δ M [u] = min (ν 1 ,...,ν d )∈G G h,dθ,δ (ν 1 ,...,ν d ) [u]
where each of the G h,dθ,δ (ν 1 ,...,ν d ) [u] is defined as

G h,dθ,δ (ν 1 ,...,ν d ) [u] = d j=1 max{D ν j ν j u, 0} + d j=1 min{D ν j ν j u, 0} -ρ X (x)/ρ Y (D x 1 u, . . . , D x d u) + δ d j=1 D x j x j u -u(x 0 ). ( 15
)
This monotone scheme forms the basis of the filtered scheme (12). For improved accuracy on smooth solutions, we combine it with the accurate scheme F A , which is simply a standard centered difference discretization of the (two-dimensional) equation

u x 1 x 1 u x 2 x 2 -u 2 x 1 x 2 -ρ X (x)/ρ Y (u x 1 , u x 2 ) -u(x 0
). We denote the resulting discretization by M A S [u]. A similar discretization is easily constructed in higher dimensions. Additional details can be found in [FO11b].

3.4. Proof of convergence. We combine the almost monotone schemes for (MA) with the upwind, monotone scheme for (HJ) into one equation, which we show converges to the unique convex viscosity solution of the system (MA),(HJ). The combined scheme is given as

(16) F h,dθ,dα [u i ] = F h,dθ F [u i ] x i ∈ X H h,dα [u i ] x i ∈ ∂X.
In this definition, F F is the filtered scheme for the Monge-Ampère equation (12), which relies on the discretizations described in subsection 3.3, and H is the upwind discretization of the boundary condition described in subsection 2.4. Theorem 3.7 (Convergence). Let u be the unique convex viscosity solution of the PDE (MA) with boundary condition (HJ). Let u h,dθ,dα be a solution of the finite difference scheme (16). Then u h,dθ,dα converges uniformly to u as h, dθ, dα → 0.

Proof. From Theorem 3.5, we need only verify that the scheme is consistent and nearly elliptic (nearly monotone).

Consistency and near monotonicity of the scheme for the Monge-Ampère equation have been established in [START_REF] Froese | Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher[END_REF][START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF].

We recall the form of the boundary condition in (7),

H(∇u(x)) = sup n =1 {∇u(x) • n -H * (n) | n • n x > 0}.
This is discretized using forward or backward differences for the gradient, which are consistent as h → 0. The supremum is further approximated by restricting to a finite subset of directions, with resolution dα. Since the Legendre-Fenchel transform H * (n) is continuous, and since these admissible directions are approximated with an accuracy on the order of dα, this approximation is consistent as dα → 0. By exploiting the obliqueness property (Lemma 2.4), we were able to construct an upwind discretization of the boundary condition, which is monotone by construction.

Solution methods

In the preceding sections, we have described a method for approximating the second boundary value problem for the Monge-Ampère equation by a system of nonlinear equations on a grid. Now we describe several different approaches for solving these equations. 4.1. Explicit iteration. The simplest approach to solving the almost-monotone system is to simply perform a forward Euler iteration on the parabolic equation

u t = det(D 2 u) = ρ X /ρ Y (∇u), x ∈ X.
In order to enforce the boundary conditions, we can evolve the Hamilton-Jacobi equation

u t = H(∇u), x ∈ ∂X.
By allowing this system to evolve to steady state, we can obtain the solution of the discrete system.

While this explicit solution method will work, it is subject to a very restrictive nonlinear CFL condition [START_REF]Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems[END_REF]. Consequently, this approach is very slow. 4.2. Newton's method. A much more efficient approach is to use an implicit solver, such as Newton's method. The filtered scheme for the Monge-Ampère equation has previously been solved with Newton's method [START_REF]Convergent almost monotone finite difference approximations for viscosity solutions of the elliptic monge-ampère partial differential equation[END_REF] in the case of Dirichlet boundary conditions. Because we are now enforcing an implicit (nonlinear) boundary condition, the Newton solver must also be used to enforce the correct boundary values. 4.2.1. The Monge-Ampère equation. We begin by reviewing the form of a damped Newton's method for the filtered discretization of the Monge-Ampère equation in the interior of the computational domain. This involves performing an iteration of the form

u k+1 = u k -α(∇M A[u k ]) -1 M A[u k ]
where the Jacobian is given by

∇M A[u] = 1 -S [u] ∇M A M [u] + S [u]∇M A S [u].
The derivative of the filter (13) is

S (x) =      1 x < 1 -1 1 < x < 2 0 x > 2.
To prevent this from taking on negative values, which can lead to poorly conditioned or ill-posed linear systems, we approximate the Jacobian by

∇M A[u] = 1 -S [u] ∇M A M [u] + max{S [u], 0}∇M A S [u].
The damping parameter α is chosen to ensure that the residual is decreasing.

This iteration requires the Jacobians of the monotone and accurate schemes. To simplify the expression, we define F (x, p) = ρ X (x)/ρ Y (p). We also use 1 0 to denote the matrix that has entries equal to one in the column corresponding to the point x 0 . We begin with the monotone scheme, recalling that this discretization has the form

M A M [u] = min (ν 1 ,...,ν d )∈G G (ν 1 ,...,ν d ) [u].
By Danskin's Theorem [Ber03], we can write the Jacobian of this as

∇M A M [u] = ∇G (ν 1 ,...,ν d ) [u],
where the (ν 1 , . . . , ν d ) are the directions active in the minimum. We also have

∇ u i G (ν 1 ,...,ν d ) [u] = d m=1     j =m max{D ν j ν j u i , 0}   1 Dν j ν j u i ≥0 + 1 Dν j ν j u i <0   D νmνm - d j=1 ∂F ∂p j (x, D x 1 u i , . . . , D x d u i ) D ν j + δ d j=1 D x j x j -1 0 .
Remark 4.1. In fact, as mentioned in Remark 3.6, we use a slightly more sophisticated discretization. The resulting Jacobian is similar to this, though slightly more complicated; see [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF] for details.

The Jacobian of the accurate scheme is (in two dimension)

∇ u i M A S [u] = (D x 2 x 2 u i )D x 1 x 1 + (D x 1 x 1 u i )D x 2 x 2 + 2(D x 1 x 2 u i )D x 1 x 2 - ∂F ∂p 1 (x, D x 1 u i , D x 2 u i )D x 1 - ∂F ∂p 2 (x, D x 1 u i , D x 2 u i )D x 2 -1 0 .
4.2.2. The boundary condition (BV2). The Newton update is also used to enforce the correct boundary conditions. We recall that the discrete form of the boundary condition obtained in section 3 can be written in compact form

H[u i ] = max n∈Λ i max{n 1 , 0}D - x u i + min{n 1 , 0}D + x u i + max{n 2 , 0}D - y u i + min{n 2 , 0}D - y u i -H * (n) .
Again we stress that at each point x i on the source boundary, the admissible set Λ i will only include directions n that allow for upwinding. We also recall that these directions, and the corresponding values of H * (n), are given or computed before the start of the Newton solve. Now at boundary points, the Newton step will take the form

u k+1 = u k -α ∇H[u k ] -1 H[u k ].
As with the Monge-Ampère operator itself, we can use Danskin's Theorem to compute the Jacobian at these points:

∇ u i H[u] = max{n 1 , 0}D - x + min{n 1 , 0}D + x + max{n 2 , 0}D - y + min{n 3 , 0}D + y
where again, the value of ν used is simply the direction that is active in the maximum.

4.3. The projection method. As an alternative solution method, we also consider the projection method described in [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF]. We show that it can be viewed as a simple iterative relaxation strategy for solving (MA-HJ). The idea of this approach is that we wish to solve for the solution u to the Monge-Ampère equation in the domain, as well as its gradient p = ∇u on the boundary of the domain. We use a splitting approach that involves alternating between:

(i) the solution of a Monge-Ampère equation with Neumann boundary data obtained from the current estimate of the gradient map p at the boundary. (ii) the solution of the Hamilton-Jacobi equation for the gradient p at the boundary. More precisely, step (i) involves updating u k+1 by solving the following Monge-Ampère equation with Neumann boundary conditions.

     det(D 2 u k+1 (x)) = ρ X (x)/ρ Y (∇u k+1 (x)) + u k+1 x ∈ X ∇u k+1 • n x = p k • n x x ∈ ∂X u k+1 is convex.
The gradient map ∇u k+1 obtained from solving this PDE may not solve the correct Hamilton-Jacobi boundary condition. Thus step (ii) involves updating the value of p k+1 to ensure that it does satisfy H(p k+1 ) = 0. To ensure that we are making use of the information from the Monge-Ampère equation, we define an intermediate value of the map p k+1/2 = ∇u k+1 at the boundary. Next, we update using a gradient descent approach.

p k+1 = p k+1/2 -H(p k+1/2 )∇H(p k+1/2 ).
This step has a geometric interpretation. Should we miss the target set so that ∇u k+1 / ∈ Y , the new value of p k+1 is precisely its projection onto the boundary of the target (∂Y ). Consequently, we recover the projection method of [START_REF] Froese | A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions[END_REF].

Numerical study

We now provide the particular details of our numerical implementation of the second boundary value problem. This is followed by computational results for a number of challenging examples.

Extension of densities.

When computing with finite difference methods, it is most convenient to work in rectangular domains. However, it is often desirable to solve the mass transport problem in more general domains. A simple solution, allowed by our solver, is to extend the density function ρ X into a square, assigning it the value zero at points outside the set X that we are interested in. This will lead to a degenerate Monge-Ampère equation, but the filtered scheme is robust enough to handle this problem. As we will show in the numerics section, this approach allows to treat non-convex or non-connected domains, or even Dirac measures in the source density.

We emphasize that this trick cannot be used to extend the target density ρ Y into a square. This is because the convergence and discretization error of the scheme are dependent on the Lipschitz constant of ρ X (x)/ρ Y (y). Even if the target density is smoothly extended to have a small positive density outside the target set Y , this function will have a very large Lipschitz constant, which makes it impractical to obtain computational results with any reasonable accuracy.

However, it is still important to extend the target density so that it is defined in all space. This is because, while the given optimal transportation problem will require a density ρ Y that is defined only in the set Y , we may be required to compute this density function at other points during the process of numerically solving the equation. As we have just noted, we cannot simply allow the density to vanish outside the target set. Instead, we must use a positve, Lipschitz continuous extension of ρ Y into all space. In some cases, when ρ Y is a given function, there is an obvious way of extending it into all space. Lipschitz extensions can always be obtained by using, for example, the method of [START_REF]A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions[END_REF]. The resulting function ρ * Y (y) can always be bounded away from zero by considering max{ρ * Y (y), ρ 0 } for some 0 < ρ 0 ≤ min y∈Y ρ Y (y).

Details of implementation.

5.2.1. Discretization of Monge-Ampère operator. There are several sources of discretization error in this method. The first source is the discretization of the Monge-Ampère equation in the interior of the domain. This discretization includes three small parameters that contribute to the error: the spatial step size dx coming from the number of grid points N X along each dimension, the angular resolution dθ coming from the width of the stencil, and the parameter δ that is used to bound the eigenvalues of the Hessian away from zero.

The precise accuracy we can expect to achieve will depend on the regularity of the solution. For sufficiently regular solutions, we expect the filtered scheme to reduce to the more accurate scheme, which has a formal accuracy of O(dx 2 ). For singular solutions, we cannot expect high accuracy. With this in mind, we simply use a narrow (9 point) stencil version of the scheme.

We previously observed that for convergence of general problems, the parameter δ should be O(dx). However, when the target density ρ Y is constant, δ can be arbitrarily small. With this in mind, we set the parameter δ = dx 2 so that it will not have an appreciable effect on the formal discretization error. The filtered scheme also requires us to define the maximum size of the non-monotone perturbation; in our computations we set this to √ dx + dθ.

Discretization of transport equations.

The implementation of the boundary conditions requires the discretization of a number of transport equations. We use simple upwinding to accomplish this, which leads to a discretization error that is O(dx).

Discretization of target set.

If the target set is polyhedral, we can determine exactly which vectors n are needed to represent the target, as well as the exact value of the Legendre-Fenchel transform of the distance function.

However, in the general case, our method leads us to approximate the target set by a polygon, which introduces additional error into the computations. In the discretization of the boundary condition (4), we will consider only N Y different directions n j = 2πj/N Y , which represent the normal vectors to the polyhedral approximation. The boundary condition is the supremum of functions that are linear in n, so we expect this approximation to lead to error that is first order: O(1/N Y ).

We must also provide a discretization of the target boundary in order to estimate the Legendre-Fenchel transform, which is done using the formula (5). This requires us to compute the supremum of terms that are linear in the boundary points y 0 so that the discretization leads to firstorder accuracy. In our computations, we discretize the boundary using 4N X points, which is similar to the number of grid points along the boundary of the domain X.

Computational examples.

We now provide several computational tests to validate the theoretical claims made in this paper.

As discussed in §5.1, we use a square domain in every example, setting the source density ρ X to zero where necessary.

Whenever an exact solution is available, we provide the maximum norm of the distance between the mappings obtained from the exact and computed solutions (u ex and u comp respectively):

max x∈X ∇u ex (x) -∇u comp (x) 2 .
We also provide the number of Newton iterations and total computation time for computations done using the most refined target boundary (largest value of N Y ). We note that there is no appreciable difference in computation time as the value of N Y is varied from 8 to 256. 5.3.1. Mapping a square to a square. We begin by recovering a mapping with an exact solution, which involves mapping a square onto a square. To set up this example, we define the function

q(z) = - 1 8π z 2 + 1 256π 3 + 1 32π
cos(8πz) + 1 32π 2 z sin(8πz). Now we map the density f (x 1 , x 2 ) = 1 + 4(q (x 1 )q(x 2 ) + q(x 1 )q (x 2 )) + 16(q(x 1 )q(x 2 )q (x 1 )q (x 2 )q (x 1 ) 2 q (x 2 ) 2 ) in the square (-0.5, 0.5) × (-0.5, 0.5) onto a uniform density in the same square. This transport problem has the exact solution u x 1 (x 1 , x 2 ) = x 1 + 4q (x 1 )q(x 2 ), u x 2 (x 1 , x 2 ) = x 2 + 4q(x 1 )q (x 2 ). This gradient map is picture in Figure 5.

Since the target set is a square, there is no need to discretize its boundary in this case.

Results are presented in Table 1. As anticipated in §5.2, we observe firstorder accuracy. Table 1. Distance between exact and computed gradient maps for map from a square to a square. The number of Newton iterations and computation time are also given.

5.3.2.

Mapping an ellipse to an ellipse. Next, we consider the problem of mapping an ellipse onto an ellipse. To describe the ellipses, we let M x , M y be symmetric positive definite matrices and let B 1 be the unit ball in R d . Now we take X = M x B 1 , Y = M y B 2 to be ellipses with constant densities f , g in each ellipse. In R 2 , the optimal map can be obtained explicitly [START_REF] Mccann | Exact semi-geostrophic flows in an elliptical ocean basin[END_REF] from

∇u(x) = M y R θ M -1
x x where R θ is the rotation matrix R θ = cos(θ)sin(θ) sin(θ) cos(θ) , the angle θ is given by tan(θ) = trace(M -1 x M -1 y J)/ trace(M -1 x M -1 y ), and the matrix J is equal to

J = R π/2 = 0 -1 1 0 .
We use the particular example M x = 0.8 0 0 0.4 , M y = 0.6 0.2 0.2 0.8 , which is pictured in Figure 6.

Results are presented in Table 2, which demonstrates first order accuracy in both N X and N Y . 5.3.3. Mapping from a disconnected region. We now consider the problem of mapping the two half-circles Table 2. Distance between exact and computed gradient maps for map from an ellipse to an ellipse. The number of Newton iterations and computation time is given for the largest number of directions (256).

X = {(x 1 , x 2 ) | x 1 < -0.2, (x 1 + 0.2) 2 + x 2 2 < 0.85 2 } ∪ {(x 1 , x 2 ) | x 1 > 0.1, (x 1 -0.1) 2 + x 2 2 < 0.85 2 } onto the circle Y = {(y 1 , y 2 ) | y 2 1 + y 2 2 < 0.85 2 }.
This example, which is pictured in Figure 7, is extremely degenerate since the domain is not simply connected. Nevertheless, our method correctly computes the optimal map, as the results of Table 3 verify. Table 3. Distance between exact and computed gradient maps for map from two semi-circles to a circle. The number of Newton iterations and computation time is given for the largest number of directions (256).

5.3.4. Inverse mapping. Next, we show that we can use our method to recover inverse mappings. In this particular example, we compute in the unit square using variable densities in both the source and the target set. The target density is simply a gaussian in the center of the domain:

ρ Y (y) = 2 + 1 0.2 2 exp - 0.5|x| 2 0.2 2 .
For the source density, we use four gaussians centered at the four corners of the domain. For example, in the quadrant [-1, 0] × [-1, 0], we use

ρ X (x) = 2 + 1 0.2 2 exp - 0.5|x -(-1, -1)| 2 0.2 2 .
These density functions are pictured in Figure 8.

To visualize the mapping between these non-constant densities, we plot several curves in the domain X, as well as the image of these curves under the gradient map. These are also in Figure 8.

The optimal mapping is computed in two different ways:

(1) By solving the problem directly.

(2) By solving the inverse problem (mapping ρ Y to ρ X ), the inverting the resulting gradient map. In order to check that these two approaches produce the same result, we look at the distance between the two maps (Table 4). Even for this challenging example, which involves splitting the gaussian into several pieces or joining these pieces back together, the difference between the two computed maps depends linearly on the spatial resolution h. 5.3.5. Mapping from a non-convex source. As another challenging computational example, we consider the problem of mapping from a non-convex domain, which can lead to a breakdown in regularity. In this example, we choose a domain shaped like the letter "C", which is mapped into the unit circle. See Figure 9 for images of these sets, as well as the computed gradient map.

ρ Y = j=N d j=1 q j δ y j .
The initial density is taken to be the Lebesgue measure on a closed convex subset of X, but any non-vanishing smooth probability density could be treated:

ρ X = 1 X .
This configuration is actually the "reconstruction of the early shape of the universe" model used in [START_REF] Frisch | A reconstruction of the initial conditions of the universe by optimal mass transportation[END_REF]. Classical solution methods are based on the Pogorelov remark that the solution (a convex potential) is necessarily of the form

u(x) = max j=1..N d {x • y j -v j }
and a necessary and sufficient condition on the {v j } j=1..N d to solve the Monge-Kantorovitch problem is shown to be operations, where N is the number of points used in the quantization (assuming this is bigger than N d ). See [START_REF] Bosc | Numerical approximation of optimal transport maps[END_REF] for a review and also [START_REF] Merigot | A multiscale approach to optimal transport[END_REF] for a multiscale approach. The Monge-Ampère solver used in this paper can deal with a singular right-hand side (ρ X ), but needs smooth target densities (ρ Y ). It does not rely on quantization, just on the discretization of the X and Y spaces using uniform grids. There is no theoretical proof of convergence, but the numerical experiments indicate that the cost of the Newton's method is linear in terms of the number of grid points (N2 ). The method will therefore not depend on the (delicate) quantization step. This means that the cost is the same for 1 or 1000 Dirac masses.

(17) ρ X (V j ) = q j , j = 1..N d where V j = {x ∈ X, j = argmax k [x • y k -v k ]}
In order to solve the problem above, we simply remark that the optimal {v j } are actually (18) v j = u * (y j ), j = 1, . . . , N d where u * is the Legendre-Fenchel transform of u and the solution of the dual problem of mapping ρ Y (singular) to ρ X (smooth). We first solve this dual problem using our approach, then reconstruct the potential u and the cells {V J }s from the solution 2 . Note that it is an extremely singular righthand side for the Monge-Ampère equation. Given M , the mass of the target density, we brutally set the weight at grid points representing the Dirac masses to M N d h 2 and 0 elsewhere. As we will see, the solution necessarily loses accuracy.

Figures (11) to (13) show randomly positioned Dirac masses embedded in a square, which are mapped to a uniform density on a ball. We plot the cells, and the colormap indicates the error with respect to the optimality condition (17). We also show the convex potential, noting that there is a one to one correspondence between the gradient of the affine facets and the positions of the target Dirac masses. We use a 256 × 256 discretization. All computation are done in Matlab on a 2.2 GHz intel Core I7 Laptop with 8 GB of RAM.

Table (5) shows the maximum and L 2 percentage error, together with the (modest) runtime. We recall that the convex potential computed by our method is the dual conjugate of the one represented in the figures. This potential will be singular at Dirac locations 3 and the solution loses accuracy and causes deterioration in the values we compute for (18). Note, however, that the solution has the correct form of a convex piecewise affine potential. We get the correct number of cells, and the optimal map ordering must be correct. These solutions could be used for initialization of exact combinatorial optimization methods.

Table ( 5) also shows that, with this dual approach, the number of Dirac masses has no impact on the run time. In Table ( 6) we look at the run times and accuracy for 300 Dirac masses when we increase resolution up to 4 million points (remember the discretisation of the initial square domain is N X × N X .) The cost of the method is linear until N X = 1024 because of out of core memory overheads. Table 6. Run time and error (percentage) for increasing grid resolution with 300 Dirac masses.

Conclusion and Perspectives

We presented a new algorithm for solving the Monge Kantorovich Optimal transportation problem. The method is robust to source densities that vanish, are singular, or have non-convex support. The target density 3 Keep in mind that these computations are being done using a compact (9 point) filtered scheme. While this is enough to observe convergence and good accuracy for smooth or even moderately singular solutions, a wide stencil can become necessary for more singular examples. This is what we observed when we computed the cone solution in [START_REF]Convergent almost monotone finite difference approximations for viscosity solutions of the elliptic monge-ampère partial differential equation[END_REF]. Additionally, these Pogorolev solutions (and the cone solution) are not actually viscosity solutions, so it is a bit remarkable if we can compute them at all. is Lipschitz continuous and non-vanishing, with support on a convex set. (Of course, the numerical method allows us to choose the target and source densities, so the restriction is on only one of the densities).

The algorithm run time, using Newton's Method, is experimentally linear in the number of grid points.

Extensions and perspectives to the work presented in this paper include:

Figure 12. The convex potential surface (red) and cell projections V j , with the colormap indicating the percentage error in cell area, for 30 randomly positioned Dirac masses (stars) mapped to a uniform density on a ball with a 256×256 grid.

• writing a 3D code. The 3D version of the Monge-Ampere solver for classical boundary conditions exist. The extension of the Hamilton-Jacobi solver on the boundary will be straightforward. • studying the structure of the linear problem in the Newton iterate.

We currently use the Matlab backslash operator, which utilizes a direct LU solver. Ellipticity suggests that an iterative Multigrid may be more efficient. • extending the method as a tool for JKO gradient seems straightforward since the linearized equations will directly give the gradient.

Figure 1 .

 1 Figure 1. Polyhedral target set.

Figure 2 .

 2 Figure 2. Illustration of the mapping y = ∇u(x) and the normal vectors.

Figure 3 .

 3 Figure 3. Filter function

Figure 4 .

 4 Figure 4. Neighboring grid points used for width one (green), two (yellow), and three (blue) stencils. The illustration shows the neighbors in the first quadrant. The modification near the boundary is illustrated in the second and third figures.

Figure 5 .

 5 Figure 5. (a) A cartesian mesh X and (b) its image under the gradient map ∇u ( §5.3.1).

Figure 6 .

 6 Figure 6. (a) An ellipse X and (b) its image under the gradient map ∇u ( §5.3.2).

Figure 7 .

 7 Figure 7. (a) Two half-circles X and (b) its image under the gradient map ∇u ( §5.3.3).

Figure 8 .

 8 Figure 8. (a) The source density ρ X and (b) target density ρ Y . (c) Curves in the domain X and (d) their image under the gradient map.

Figure 9 .Figure 10 .

 910 Figure 9. The boundaries of the (a) source X and (b) target Y sets. (c) Curves in the domain and (d) their image under the gradient map.

  are the support cells of each of the affine functions. Modern methods rely on the quantization of the density ρ X to a sum of Diracs. It reduces the problem to a classical assignment problem which can be solved by the Auction algorithm in O(N 2 log N )

Figure 11 .

 11 Figure11. The convex potential surface (red) and cell projections V j , with the colormap indicating the percentage error in cell area, for 3 randomly positioned Dirac masses (stars) mapped to a uniform density on a ball with a 256 × 256 grid.

Figure 13 .

 13 Figure 13. The convex potential surface (red) and cell projections V j , with the colormap indicating the percentage error in cell area, for 300 randomly positioned Dirac masses (stars) mapped to a uniform density on a ball with a 256 × 256 grid. • extending to c-convexity. A popular generalization of the Monge-Kantorovitch problem is to replace the Euclidean distance xy 2 by a convex function c(x, y) in the transportation cost. The theory is well developed and one can write a version of the nonlinear Monge-Ampère PDE for c-convex potential solutions. The numerical solution of this equation is an open problem.

Table 4 .

 4 Distance between forward map and the inverse of the computed inverse map. The number of Newton iterations and computation time is also given for the two different approaches for computing the map.

	N X Max Distance	Iterations	CPU Time (s)
			Forward Inverse Forward Inverse
	32	0.2337	6	3	0.3	0.2
	64	0.1252	6	3	1.1	1.1
	128	0.0649	8	3	6.3	5.2
	256	0.0329	9	4	35.8	32.6
	362	0.0233	11	4	95.2	52.2

Table 5 .

 5 N d L ∞ Error L 2 err CPU Time (s) Normalized errors (percentage) for N X = 256

	3	0.05	0.02	10.48
	30	0.48	0.21	10.56
	300	0.56	0.18	11.8
	N X L ∞ Error L 2 err CPU Time (s)
	64	0.93	0.28	1.48
	128	0.96	0.24	2.6
	256	0.83	0.21	11.7
	512	0.66	0.20	46.76
	1024	0.64	0.20	281.53

He earned the '75 Nobel prize in economics.

We use the MPT Matlab toolbox http://control.ee.ethz.ch/ ~mpt/.


Béatrice Parguel

EFFECTS OF ANTI-TOBACCO BRANDS AD PARODIES ON CIGARETTE BRANDS ATTITUDE

This paper compares the effects of anti-tobacco ad parodies and visual cigarette package warnings on emotional and cognitive responses of young adults. The findings indicate that graphic-only ad parodies can compete with warnings in their attempt to damage consumers' attitude toward tobacco brands through the health beliefs they lead consumers to associate to the brand. On the contrary, text-only ad parodies prove counterproductive and lead to a boomerang effect characterized by an increase in consumers' tobacco brand attitude.

INTRODUCTION

Cigarette consumption is a major cause of premature death, killing nearly 6 million people each year (World Health Organization 20111). In particular, young adulthood is a period of continued smoking progression when smokers establish regular and long-term smoking practices [START_REF] Hammond | Health Warning Messages on Tobacco Products: A Review[END_REF]. As a result, many government agencies are taking initiatives to keep young adults away from cigarette consumption.

In the same attempt to reduce the number of smokers, anti-tobacco nonprofit groups use creative alternative methods of communication to voice their message, by creating ad parodies they spread though web-sites [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF]. Spoofing advertising allows activists sharing entertainment, attacking brands and showing off personal skills [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF]. However, studies mainly focused on consumer-created ad parodies undertaken by brand loyalists on behalf of the brand and left anti-brand ad parodies effects on persuasion largely unexplored [START_REF] Berthon | Ad lib: When Customers Create the Ad[END_REF]. Clearly, research is lacking on whether anti-brand ad parodies could be a means of influencing the attitudes, perceptions and resulting behaviors. In the case of tobacco, it is now important for both anti-brand activists who create and spread anti-tobacco brand ad parodies, and the researchers who study them, to gain a better understanding of their relative efficiency compared to more classical anti-tobacco warnings, such as cigarette package warnings.

We thus focus in this paper on anti-tobacco brand ad parodies to study whether they can really impact consumer's attitude toward tobacco brands, and, if so, the mechanisms by which such an effect occurs. Such a focus on cigarette brands attitude as the dependent variable appears highly relevant since cigarette brands attitude has largely been shown to influence tobacco consumption behaviors as a means of self-expression and peers acceptance among young adults [START_REF] Pechmann | The Effects of Antismoking and Cigarette Advertising on Young Adolescents' Perceptions of Peers Who Smoke[END_REF][START_REF] Pechmann | An Experimental Investigation of the Joint Effects of Advertising and Peers on Adolescents' Beliefs and Intentions about Cigarette Consumption[END_REF]. Also, focusing on consumers' attitude toward specific cigarette brands and not toward smoking in general finds support in that anti-tobacco warnings appear relatively ineffective in influencing attitude toward smoking among young adults who already hold strong preconceptions on smoking's adverse health effects [START_REF] Pechmann | The Effects of Antismoking and Cigarette Advertising on Young Adolescents' Perceptions of Peers Who Smoke[END_REF]. However, they can clearly influence a more changing variable such as cigarette brands attitude [START_REF] Germain | Adolescents' Perceptions of Cigarette Brand Image: Does Plain Packaging Make a Difference[END_REF]). Thus, we focus more precisely on the following questions: What is the influence of anti-tobacco brand ad parodies compared with cigarette package warnings on consumers' attitude about cigarette brands? Do the effects of antitobacco brand ad parodies that parody only the ad text differ from those that parody both the ad text and graphics?

ANTI-BRAND AD APRODIES: AN OVERVIEW

Two main criterions are likely to discriminate between ad parodies: valence (i.e., positive, neutral or negative) and source (i.e., the brand itself, its competitors, brands in other categories, ordinary individuals wishing to express their personal creativity or activists, including unsatisfied customers and employees). Within this typology, anti-brand ad parodies belong to the kind of negatively valenced parodies designed by activists to warn consumers against brands. They range from poking harmless fun to malicious and spiteful jibes directed at some of the world's best known brands [START_REF] Hollenbeck | Consumer Activism on the Internet: the Role of Anti-Brand Communities[END_REF].

From a practical point of view, ad parodies refer to hijack actions on official brand ads, mixing part of those official ads' materials ( logo, slogan, picture, style) with new ones in a sarcastic way to make the original ad ridiculous or distasteful. Ad parodies display different levels depending on the materials that they parody. In this paper, we distinguish between "text-only ad parodies", only parodying the official ad text, and "graphic-only ad parodies", only parodying the official graphics. While ad parodies were previously the prerogatives of professionals, today, anyone with a computer, a sense of inventiveness and a statement to make can craft a professional looking ad parody, strongly resembling in form to the ad of the brand to be criticized [START_REF] Berthon | Ad lib: When Customers Create the Ad[END_REF][START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF].

Besides, the Internet has empowered ordinary consumers and nonprofit groups by providing powerful means to express their views effectively and tools to reach a large targeted audience at will. Easier to make thanks to inexpensive media software, ad parodies are then as well easier to spread through the Internet and its vehicles (e.g., YouTube, Facebook, DailyMotion). Therefore, anti-brand ad parodies are becoming increasingly common on line, especially for cigarette brands, which appear among the most spoofed brands worldwide along with alcohol, computer and clothing brands. As an illustration, anti-brand activists have for instance launched Adbusters, a website (http://www.adbusters.org) on which appears Joe Chemo, the Joe Camel mascot, suffering from lung cancer in his retirement years.

Spoofing cigarette brands ads on line, activists question cigarette brands advertising impact and legitimacy. In the long term, their objective is to counter the effects of official cigarette brands advertising, to warn people against their hazards and to affect individual cigarette consumption. To do so, they target specific brands, such as Marlboro or Camel, because they symbolize the tobacco industry. Still, we do not know much on their precise effects in the short term on cigarette brands attitude. Vanden [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF] suggest the brand may be harmed if the denunciation effect predominates and the original brand is its target. However, if the humorous effect predominates, humor might reinforce pleasant emotional associations with the brand, preventing it form being harmed. Alternatively, one would expect that the brand may not be harmed if people understand that the parody's purpose is to use the brand's meanings to attack something more general and not the targeted brand in particular. Our goal is thus to ensure that activists are right in targeting specific brands through humoristic ad parodies to warn people against hazards of smoking and to damage consumer's attitude toward the brand. The question remains howthat is through what specific route -ad parodies exert their persuasive effects.

CONCEPTUAL BACKGROUND: PERSUASION OF ANTI-TOBACCO WARNINGS

Persuasion refers to any instance in which an active attempt is made to change a person's mind (Petty and Cacioppo 1981, 6). Advertising researchers have long been studying attitude change because it is presumed to direct behaviors (Petty and Cacioppo 1981, 7). Focusing on brand attitude, they clearly recognize the influence of consumers' emotional and cognitive reactions to advertising [START_REF] Mitchell | Are Product a Beliefs the Only Mediator of Advertising Effects on Brand Attitude[END_REF][START_REF] Mackenzie | The Role of Attitude Toward the Ad as a Mediator of Advertising Effectiveness: A Test of Competing Explanations[END_REF]. These two routes are here used to explain cigarette brands attitude and compare anti-tobacco brand ad parodies and cigarette package warnings relative efficiency in persuading young adults.

The emotional route to persuasion

As kinds of anti-tobacco warnings, anti-tobacco brand ad parodies and cigarette package warnings are both likely to induce negative emotional reactions, such as fear or disgust [START_REF] Goodall | Adolescents' Perception of Canadian Cigarette Package Warning Labels: Investigating the Effects of Message Framing[END_REF]. However, the extent to which ad parodies and cigarette package warnings elicit negative emotional responses may differ. Comparing central versus peripheral elements way of influence, the elaboration likelihood model [START_REF] Petty | Attitudes and Persuasion: Classic and Contemporary Approaches[END_REF] suggests that peripheral elements, such as execution elements or the characteristics of the source, have their main influence through the emotional route. On the contrary, central elements, including texts, have their main influence through the cognitive route. Thus, the influence of ad parodies on negative emotional reactions might more depend on the image they parody than on the text they parody. As text-only parodies display the positive official ad graphics, when graphic-only ad parodies display new striking materials, we expect graphic-only ad parodies to elicit more negative emotional reactions than text-only ad parodies. Besides, as cigarette package warnings often feature particularly shocking pictures while graphic-only ad parodies take their inspiration in official ads materials and advertising conventions and therefore depict the dangers of tobacco use in a less concrete manner, we predict that cigarette package warnings will elicit more negative emotional reactions than graphic-only ad parodies. Hence we posit the following: H1: Graphic-only ad parodies elicit more negative emotional reactions than text-only ad parodies (a) but less than cigarette package warnings (b).

At the same time, anti-tobacco brand ad parodies are consumer-created ad parodies designed to make laugh, even when they are created to have specific effects on a targeted audience and not just for fun [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF]). An observation of the comments left on YouTube regarding anti-tobacco brand spoof videos highlight that they do make laugh. On YouTube, the main emotional reactions induced by anti-tobacco brand ad parodies are upbeat feelings, far ahead of negative emotional reactions. Therefore, ad parodies are likely to elicit more positive emotional reactions compared with cigarette package warnings. Besides, the literature has pointed out that a caricature has to create a gap (i.e., there should be a disparity between the image and the realty of the object of caricature) to work and make laugh in the field of politics [START_REF] Speck | The Humorous Message Taxonomy: A Framework for the Study of Humorous Ads[END_REF]. Humor is thus experienced when a discrepancy is experienced and finally solved when the subject understands the origin of the incongruity and feels release. Applying these proposals to ad parodies, Vanden [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF] suggest that an ad parody surprises the viewer when it creates confusion by incorporating elements that do not fit with his expectations. Then, the viewer understands that the parody is indicating how the original ad might not have been telling the whole truth and experiences positive emotions such as release and humor. Considering spoof advertising, text-only ad parodies display a strong discrepancy, mixing graphic elements favorable to cigarette brands and familiar to the viewer with an unfavorable text. On the contrary, there is no such gap in graphic-only ad parodies, where all elements display a convergent message. Therefore, as text-only ad parodies create a bigger incongruity than graphic-only ad parodies, they might elicit more positive emotional reactions. Thus, we propose the following: H2: Graphic-only ad parodies elicit less positive emotional reactions than text-only ad parodies (a), but more than cigarette package warnings (b).

The cognitive route to persuasion

The cognitive route represents the product of a consumers' elaboration of the information presented in a persuasive message. Elaboration means that the receiver takes the arguments of the brand and integrates them into his or her own attitude. As a component of brand image, the role of brand associations is crucial in the process of elaboration. In this paper, we focus on the two strongest cigarette brands associations, namely their perceived risk and their symbolic image. Regarding perceived risk, studies on graphic tobacco warnings conclude that visual labels are more visible and easier to understand [START_REF] Gallopel-Morvan | The Use of Visual Warnings in Social Marketing: The Case of Tobacco[END_REF], leading to more efficacy in communicating smoking health hazards [START_REF] Hammond | Health Warning Messages on Tobacco Products: A Review[END_REF]. The same reasoning should play to compare text-only ad parodies with graphic-only ad parodies. Besides, the former communicate smoking health hazards in an ambivalent way as it contains non-convergent elements when the latter depict them in a clearer way with two convergent elements. Therefore, the risks associated with cigarette brands are easier to understand in graphic-only ad parodies compared with text-only ad parodies. When comparing the relative influence of graphic-only ad parodies versus cigarette package warnings on risks perception, we may observe that cigarette packages are poorly branded. They only exhibit cigarette brands name and warnings, and could be perceived as boring and unattractive, making therefore health warning more noticeable [START_REF] Germain | Adolescents' Perceptions of Cigarette Brand Image: Does Plain Packaging Make a Difference[END_REF] compared with the richer message developed by graphic-only ad parodies. Relying on previous arguments, we propose the following hypotheses: H3: Subjects exposed to graphic-only ad parodies perceive cigarette brands as more risky than subjects exposed to text-only ad parodies (a), but less risky than subjects exposed to cigarette package warnings (b).

Cigarette brands official ads are crafted to address young adults' need for independence, self reliance, and freedom [START_REF] Pechmann | The Effects of Antismoking and Cigarette Advertising on Young Adolescents' Perceptions of Peers Who Smoke[END_REF]. They also aim at promoting peer acceptance among targeted young people and positive lifestyle images to enhance smoking social acceptability and enhance cigarette brands symbolic beliefs. As noted by Vanden [START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF], when creating ad parodies, consumers create a viral object that might help in spreading the original ad's themes and imagery. Anti-tobacco activists might thus potentially reactivate cigarette brands positive symbolic beliefs in consumers' mind and obtain the same results as official ads. They also might enhance social benefits associated to smoking that, those having been found by researchers relying on theories like the Social Learning Theory [START_REF] Bandura | Social Learning Theory[END_REF][START_REF] Parguel | Peer Influence on Smoking Initiation During Early Adolescence: A Comparison of Group Members and Group Outsiders[END_REF] or the Stereotype Priming Theory (Maheswaran1994; Pechmann and Knight 2002) to be very efficient to influence young. If anti-tobacco brand ad parodies present smokers as physically attractive, engaged in exciting activities, then they could run counter to messages that smoking is dangerous to one's health and reinforce perceptions that smoking is a normative consumption product [START_REF] Devlin | Comparative Study of Young People's Response to Anti-Smoking Messages[END_REF]. As text-only ad parodies appropriate the graphic elements of official ads, they are more likely to enhance brands positive symbolic beliefs compared with other forms of anti-tobacco warnings.

Besides, ad parodies may create a "Doppelgänger Brand Image", a set of disparaging images about a brand that are able over time to coalesce into a coherent set of opposing meanings that plague brand [START_REF] Thompson | Emotional Branding and the Strategic Value of the Doppelgänger Brand Image[END_REF]. This is especially true for graphic-only ad parodies which associate brands with new negative graphical conventions. As graphiconly ad parodies crash brands previous meanings, they are less likely to enhance brands positive symbolic beliefs compared with cigarette package warnings. Thus, we posit: H4: Subjects exposed to graphic-only ad parodies associate less positive symbolic beliefs to cigarette brands than subjects exposed to text-only ad parodies (a) and cigarette package warnings (b).

The change in cigarette brands attitude

On the emotional route, negative emotions experienced by the individual exposed to cigarette warnings result in an increase in the persuasiveness of these warnings [START_REF] Rogers | Attitude Change and Information Integration in Fear Appeals[END_REF]. Fear appeals have been shown to have the most impact on behaviors such as quitting [START_REF] Tanner | The Protection Motivation Model: A Normative Model of Fear Appeals[END_REF][START_REF] Hammond | Health Warning Messages on Tobacco Products: A Review[END_REF]). Besides, negative emotions are supposed to transfer to the object to which they are associated by mere association [START_REF] Mitchell | Are Product a Beliefs the Only Mediator of Advertising Effects on Brand Attitude[END_REF]. Following the same argument, anti-tobacco brand ad parodies that generate upbeat feelings might enhance cigarette brands attitude.

The cognitive route provides an alternative explanation for the process of change in cigarette brands attitude. First, the Protection Motivation Model [START_REF] Rogers | A Protection Motivation Theory of Fear Appeals and Attitude Change[END_REF]) and the Health Belief Model [START_REF] Rosenstock | Historical Origins of the Health Belief Model[END_REF]) posit that consumers' persuasion depends on the appraisal of the severity of the risks. In the end, this perception of the risks associated with cigarette brands consumption is likely to lead to brand avoidance. Second, the positive symbolic meanings associated with cigarette brands are likely to transfer to cigarette brands attitude [START_REF] Pechmann | The Effects of Antismoking and Cigarette Advertising on Young Adolescents' Perceptions of Peers Who Smoke[END_REF][START_REF] Pechmann | An Experimental Investigation of the Joint Effects of Advertising and Peers on Adolescents' Beliefs and Intentions about Cigarette Consumption[END_REF]. Our last hypothesis will test these conjectures and compare the mechanisms by which graphic-only and text-only ad parodies, as well as cigarette package warnings, can lead to changes in consumer's attitude toward the tobacco brand. We expect that the effect of anti-tobacco warnings (representing both ad parodies and cigarette package warnings) on attitude toward the brand is mediated by the emotional reactions experienced by the subjects, and by their brand beliefs. Specifically: H5: The effects of anti-tobacco warnings (representing both ad parodies and cigarette package warnings) on attitude toward the brand are mediated by emotional and cognitive reactions. Graphic-only ad parodies will lead to lower attitude toward the brand because of their positive effect on negative emotions (fear and disgust) (H5a and H5b) and health beliefs (H5c). On the contrary, text-only ad parodies will lead to higher attitude toward the brand because of their effect on positive emotions (upbeat feelings) (H5d) and on symbolic beliefs (H5e).

METHOD

Research design, stimulus selection and sample

To test our predictions, we carried an experiment considering 3 different kinds of anti-tobacco warnings: a text-only ad parody, a graphic-only ad parody and a cigarette package warning. The text-only and graphic-only ad parodies, as well as the cigarette package warning used for the experiment were all real materials in order to increase the realism of the study.

To ensure that respondents were familiar with the brand and thus to control also for familiarity, Marlboro, a top selling brand in the United States and Europe [START_REF] Hemdev | Marlboro -A Mini Case Study[END_REF] was chosen as the brand in the experiment. The text-only ad parody which has been chosen was the Marlboro picture presenting two cowboys riding into the sunset. The only single change from the original ad which had been made by the ad parody developers resulted from the humoristic text warning "I miss my lung Bob". The graphic-only ad parody used the original sentence "Welcome to Marlboro Country", the graphic change made by the ad parody developers had consisted in depicting a graveyard in the background. Since pictorial warnings have been found to be the most persuasive [START_REF] Hammond | Health Warning Messages on Tobacco Products: A Review[END_REF], the cigarette package warning condition included a graphic-only warning. Precisely, the pack provided a warning showing one healthy lung and one damaged, and a verbal warning "Smoking causes fatal lung cancer".

As the goal of the research was to study the effects of ad parodies on young adults, participants were 139 university students (mean age = 22, 35% being men and 65% being women, 43% being smokers). The respondents were randomly assigned to one of the three experimental conditions. Chi-Square tests and a t-test revealed that respondents in the three experimental conditions were similar in terms of gender (χ² Gender = .868, df= 2, p > .05) and tobacco consumption habits (χ² Smoker = 1.345, df = 2, p > .05).

Measures

Outcome variables included upbeat feelings, fear and disgust evoked by the ad parody and the cigarette package warning, health and symbolic beliefs associated to the brand, and attitude toward the brand. All the scales were either entirely or partially adopted from previous research. Note that to keep the questionnaire short without compromising the quality of the measure [START_REF] Bergkvist | The Predictive Validity of Multiple-Item Versus Single-Item Measures of the Same Constructs[END_REF], attitude toward the brand was measured through a single-item measure asking respondents "the extent to which they liked the Marlboro Brand". A description of the scale and of their psychometric properties including reliability coefficients are presented in Table 1. Each item was rated on a 7-point scale ranging from 1 (Not at all) to 7 (Very Strongly). We also measured participants' smoking status as a potential covariate. Participants had to rate the extent to which they were "non-smokers" or "heavy smokers". People answering "non-smokers" were labeled nonsmokers, the other were labeled "smokers".

RESULTS

The effects of ad parodies versus cigarette package warning exposure on emotional and cognitive responses were examined using analyses of variance (ANOVA). Independent samples t-tests were also used to test the differences between graphiconly ad parodies and respectively text-only ad parodies and cigarette package warnings (Table 2).

Effects of ad parodies exposure on emotional responses

Findings indicate that the ad parodies versus cigarette package warning exposure manipulation had a significant effect on fear (F(4, 136) = 7.54; p < .05). Results from t-tests show that graphic-only ad parody exposure condition resulted in a significant increase in fear only when compared with text-only ad parody exposure condition (M Graphic = 4.06 vs. M Text = 2.72, p < .001). No significant difference between graphic-only ad parody exposure condition and cigarette package warning exposure condition was found (M Warning = 3.80, p > .05). Results dealing with disgust offer the same pattern of results. However, the results differ in that the highest level of disgust is obtained in the cigarette package warning condition (M Warning = 4.84). Disgust in the graphic-only ad parody exposure condition is significantly higher than the ones obtained in the text-only ad parody exposure condition (M Graphic = 4.06 vs. M Text = 2.75, p < .001) but lower than in the cigarette package warning exposure condition (M Warning = 4.84, p < .05). These results offer support for H1(a) and partial support for H1(b).

Regarding positive emotions, our findings indicate that the ad parodies versus cigarette package warning exposure manipulation had a significant effect on upbeat feelings (F(2, 136) = 6.62 ; p < .01). Specifically, graphic-only ad parody exposure condition resulted in a significant decrease in upbeat feelings when compared with text-only ad parody exposure condition (M Graphic = 1.46 vs. M Text = 2.25, p < .01). However, the graphic-only ad parody exposure did not induce more upbeat feelings that the cigarette package warning exposure (M Warning = 1.55, p > .05). Thus, H2(a) is supported but not H2 (b).

Effects of ad parodies exposure on cognitive responses

Results indicate that the ad parodies and warning exposure manipulation has a marginally significant effect on health beliefs (F(2, 136) = 2.65 ; p < .10), and a much highly significant effect on symbolic beliefs associated to the brand (F(2, 136) = 4.99; p < .01). Regarding health beliefs, the graphic-only ad parody exposure condition led to the highest mean of health beliefs (M = 5.49). More precisely, t-tests revealed a marginally significant between graphic-only and text-only ad parodies exposure conditions difference (M Graphic = 5.49 vs. M Text = 4.96, p < .10), and a more significant difference when comparing the effect of graphic-only ad parody to the one of cigarette package warning (M Graphic = 5.49 vs. M Warning = 4.79, p < .05). Thus, these results offer support for H3(a), but not for H3(b).

Results regarding the effects of ad parodies and warnings on symbolic beliefs are clearer. They reveal that being exposed to text-only ad parodies significantly leads to the highest level of symbolic beliefs (M Text = 3.64). This level is significantly higher than the one of individuals exposed to graphic-only ad parodies (M Text = 3.64 vs. M Graphic = 2.82, p < .05). Symbolic beliefs induced by exposure to graphic-only ad parodies did not differ to the ones elicited by exposure to cigarette package warnings (M Graphic = 2.82 vs. M Warning = 2.72, p > .05). These results offer support for H4(a) but not H4(b).

Tests of the Mediating Roles of Emotions and Cognitions

http://www.who.int/mediacentre/factsheets/fs339/en/index.html

A primary goal of this study was to examine a potential underlying mechanism that might account for the ad parodies exposure effects on attitude toward the brand. Thus, we tested emotions and cognitions as potential mediators of these effects. Following [START_REF] Zhao | Reconsidering Baron and Kenny: Myths and Truths about Mediation Analysis[END_REF] procedure, we used [START_REF] Preacher | Asymptotic and Resampling Strategies for Assessing and Comparing Indirect Effects in Multiple Mediator Models[END_REF] macro and 5000 bootstrapped samples to determine whether the indirect effect was significant.

We decided to study the mechanism explaining the effects of ad parodies exposure on attitude toward the brand by comparing the effects of graphic-only ad parodies to respectively the ones of text-only ad parodies, and then the ones of cigarette package warnings. For each mediation analysis, the graphic-only ad parody condition was coded 1, so that a positive effect of the independent variable on the mediator in the indirect path can be interpreted as the effect of the graphic-only ad parody exposure and a negative effect as the one caused by the other kind of warning. Furthermore, smoking status was included in the analyses as a control variable. Since gender, age and education were not significantly different from one group to one another, no other individual variable was included as a control variable.

First, when comparing the mechanism by which being exposed to graphic-only ad parodies versus text-only ad parodies lead to changes in attitude toward the tobacco brand, the most striking result lies in the absence of mediating effects of any emotions. Indeed, all indirect effects of fear, disgust and upbeat feelings are not significant with 95 confidence intervals including zero, providing no support to H5 (a), H5(b) and H5 (c). On the contrary, results highlight that the only mediating variables is symbolic beliefs (a × b = -.12, the confidence interval excluding 0). The negative sign of the mediating effect reveals that increases in Ab may be due to increases in symbolic beliefs induced by text-only ad parodies. This result thus supports H5 (e). No mediating effect of health beliefs was found out. Smoking status was not significant as a covariate (p >. 10). These results bring to the light the importance of symbolic beliefs in the influence of anti-tobacco ad parodies and their ability to lead consumers to develop better attitudes toward the tobacco brand, the exact opposite effect assigned to such textonly ad parodies.

Second, when comparing the mechanism underlying the effects of being exposed to graphic-only ad parodies versus cigarette package warnings, the only indirect effect that is significant is the one of health beliefs (a × b = -.18, the confidence interval excluding 0). Thus, here again, emotions do not play any mediating role in the influence of ad parodies versus warnings exposure on attitude, leaving the influence of ad parodies and warnings on attitude to be explained by cognitions. Since graphic-only ad parodies exposure condition was coded 1, the negative sign of the mediating effect reveals that increases in Ab may be due to health beliefs induced by the graphic-only ad parodies exposure. This result supports H5 (b). As for the analysis of emotions as mediators, smoking status here was not significant as a covariate (p >. 10).

GENERAL DISCUSSION

This research aimed at demonstrating that ad parodies may be an original and creative new way to take part in the public fight against smoking behavior by leading young adults to develop negative attitudes toward tobacco brands. Overall, our study contributes to a better understanding of the effects of ad parodies in the three following ways. First, we introduce a distinction between text-only and graphic-only ad parodies, whereas most studies focus on parody without proposing any distinction between the different kinds of parodies [START_REF] Rumbo | Consumer Resistance in a World of Advertising Clutter: The Case of Adbusters[END_REF][START_REF] Bergh | The Multidimensional Nature and Brand Impact of User-Generated Ad Parodies in Social Media[END_REF]. This distinction allows refining the process through which ad parodies may or may not reach the goal of damaging consumers' attitude toward tobacco brands. Second, we oppose ad parodies to anti-tobacco warnings to compare their efficiency in leading to negative emotions, such as fear, or negative beliefs, such as health beliefs. Third, we explain the mechanism under which both text-only and graphic-only ad parodies influence consumer's attitude toward tobacco brands.

Regarding this third objective, results show that what mediates the comparative effects of ad parodies and warnings are not emotions but cognitions. Second, results show that graphic-only ad parodies can compete with warnings in their attempt to damage consumers' attitude toward tobacco brands through the health beliefs they lead consumers to associate to the brand, which decreases attitude toward the brand. Furthermore and of much importance, due to the symbolic beliefs they induce, text-only ad parodies may prove counterproductive and lead to a boomerang effect characterized by an increase in consumers' tobacco brand attitude.

Practical implications for public policy and activists

The preceding findings offer potentially important implications. for both public health policy and activists or organizations who aim at disparaging smoking behavior. These implications stem from the direct and mediating effects that we found in the study. Although many antismoking campaigns have focused primarily on emotional-based reasons not to smoke, especially through a focus on fear [START_REF] Laroche | A Cross-Cultural Study of the Persuasive Effect of Fear Appeal Messages in Cigarette Advertising: China and Canada[END_REF], our main result relates to the mediating role of health beliefs. This result suggests that cognitive approaches may also be of interest to study the beneficial effects of warnings labels. Contrary to warnings, graphic-only ad parodies are more likely to hurt tobacco brands' image through the negative health-related associations that consumers draw. This result reveals for public policy officers that by directly showing how through graphic ad parodies the hazards related to tobacco consumption, they can lead consumers to develop negative attitude toward tobacco brands.

For activists who create ad parodies to hurt tobacco brands, graphic-only ad parodies may represent creative ways of decreasing such attitude indirectly through health beliefs. Meanwhile, our results also suggest avoiding text-only spoof ads prime symbolic beliefs which in turn positively affect consumers' attitude toward the tobacco brand, the exact opposite reaction of the one that ad parodies developers aim at generating.

Limitations and further research

Future studies should attempt to uncover whether the change in attitude toward the tobacco brands is an actual reflection of intention to quit and quitting behavior. Because attitude toward the brand has been shown to mediate the effect of warnings of intentions to quit [START_REF] Sabbane | Recency Versus Repetition Priming Effects of Cigarette Warnings on Nonsmoking Teenagers: the Moderating Effects of Cigarette Brand Familiarity[END_REF], graphic-only warning that damage the attitude toward the brand may lead to less intention to smoke. However, nicotine is very addictive [START_REF] Andrews | Understanding Adolescent Intentions to Smoke: An Examination of Relationships Among Social Influence, Prior Trial Behavior, and Antitobacco Campaign Advertising[END_REF][START_REF] Kees | Understanding How Graphic Pictorial Warnings Work on Cigarette Packaging[END_REF]) and we recognize that that it may be difficult to really distinguish between the effect of ad-parodies (text-only and graphic-only ad parodies versus warning exposure) and the effect of addiction.

TABLES