Paweł Guzewicz
email: pawel.guzewicz@telecom-paristech.fr

Ioana Manolescu
email: ioana.manolescu@inria.fr

Quotient RDF Summaries Based on Type Hierarchies

Summarization has been applied to RDF graphs to obtain a compact representation thereof, easier to grasp by human users. We present a new brand of quotient-based RDF graph summaries, whose main novelty is to summarize together RDF nodes belonging to the same type hierarchy. We argue that such summaries bring more useful information to users about the structure and semantics of an RDF graph.

I. INTRODUCTION

The structure of RDF graphs is often complex and heterogeneous, making them hard to understand for users who are not familiar with them. This problem has been encountered in the past in the data management community, when dealing with other semi-structured graph data formats, such as the Object Exchange Model (OEM, in short) [START_REF] Papakonstantinou | Object exchange across heterogeneous information sources[END_REF]. Structural summaries for RDF graphs. To help discover and exploit such graphs, [START_REF] Goldman | Dataguides: Enabling query formulation and optimization in semistructured databases[END_REF], [START_REF] Nestorov | Representative objects: Concise representations of semistructured, hierarchical data[END_REF] have proposed using Dataguide summaries to represent compactly a (potentially large) data graph by a smaller one, computed from it. In contrast with relational databases where the schema is fixed before it is populated with data (a priori schema), a summary is computed from the data (a posteriori schema). Each node from the summary graph represents, in some sense, a set of nodes from the input graph. Many other graph summarization proposals have been made, for OEM [START_REF] Milo | Index structures for path expressions[END_REF], later for XML trees with ID-IDREF links across tree nodes (thus turning an XML database into a graph) [START_REF] Chen | D(K)-index: An adaptive structural summary for graph-structured data[END_REF], [START_REF] Kaushik | Covering indexes for branching path queries[END_REF], [START_REF] Li | Indexing and querying XML data for regular path expressions[END_REF], and more recently for RDF [START_REF] Udrea | GRIN: A graph based RDF index[END_REF], [START_REF] Gurajada | Using graph summarization for join-ahead pruning in a distributed RDF engine[END_REF], [START_REF] Čebirić | Query-oriented summarization of RDF graphs (demonstration)[END_REF], [START_REF]Query-oriented summarization of RDF graphs[END_REF], [START_REF]A framework for efficient representative summarization of RDF graphs[END_REF], [START_REF] Palmonari | ABSTAT: linked data summaries with abstraction and statistics[END_REF]; many more works have appeared in this area, some of which are presented in a recent tutorial [START_REF] Khan | Summarizing static and dynamic big graphs[END_REF]. Related areas are concerned with graph compression, e.g. [START_REF] Sadri | Shrink: Distance preserving graph compression[END_REF], ontology summarization [START_REF] Troullinou | Ontology understanding without tears: The summarization approach[END_REF] (focusing more on the graph semantics than on its data) etc. Quotient-based summaries are a particular family of summaries, computed based on a (summary-specific) notion of equivalence among graph nodes. Given an equivalence relation ≡, for each equivalence class C (that is, maximal set of graph nodes comprising nodes all equivalent to each other), the summary has exactly one node n C in the summary. Example of quotient-based summaries include [START_REF] Milo | Index structures for path expressions[END_REF], [START_REF] Chen | D(K)-index: An adaptive structural summary for graph-structured data[END_REF], [START_REF] Kaushik | Covering indexes for branching path queries[END_REF], [START_REF] Li | Indexing and querying XML data for regular path expressions[END_REF], [START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF], [START_REF]Query-oriented summarization of RDF graphs[END_REF], [START_REF] Čebirić | Query-oriented summarization of RDF graphs (demonstration)[END_REF], [START_REF]A framework for efficient representative summarization of RDF graphs[END_REF]; other summaries (including Dataguides) are not quotient-based.

This work is placed within the quotient-based RDF summarization framework introduced in [START_REF]A framework for efficient representative summarization of RDF graphs[END_REF]. That framework adapts the principles of quotient-based summarization to RDF graphs, in particular preserves the semantics (ontology), which may come with an RDF graph, in its summary. This is important as it guarantees that any summary defined within the framework is representative, that is: a query having answers on an RDF graph, has answers on its summary. This allows to use summaries as a first user interface with the data, guiding query formulation. Note that here, query answers take into account both the data explicitly present in the RDF graph, and the data implicitly present in the graph, through reasoning based on the explicit data and the graph's ontology.

Two RDF summaries introduced in [START_REF]Query-oriented summarization of RDF graphs[END_REF] have been subsequently [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF] redefined as quotients. They differ in their treatment of the types which may be attached to RDF graph nodes. One is focused on summarizing the structure (non-type triples) first and copies type information to summary nodes afterwards; this may erase the distinctions between resources of very different types, leading to confusing summaries. The other starts by separating nodes according to their sets of types (recall that an RDF node may have one or several types, which may or may not be related to each other). This ignores the relationships which may hold among the different classes present in an RDF graph. Contribution and outline. To simultaneously avoid the drawbacks of the two proposals above, in this paper we introduce a novel summary based on the same framework. It features a refined treatment of the type information present in an RDF graph, so that RDF graph nodes which are of related types are represented together in the summary. We argue that such a summary is more intuitive and more informative to potential users of the RDF graph.

The paper is organized as follows. We recall the RDF graph summarization framework introduced in [START_REF]A framework for efficient representative summarization of RDF graphs[END_REF] which frames our work, as well as the two abovementioned concrete summaries. Then, we formally define our novel summary, and briefly discuss a summarization algorithm and its concrete applicability.

II. RDF GRAPHS AND SUMMARIES A. RDF and RDF Schema

We view an RDF graph G as a set of triples of the form s p o. A triple states that its subject s has the property p, and the value of that property is the object o. We consider only well-formed triples, as per the RDF specification [START_REF] W3c | Resource description framework[END_REF], using uniform resource identifiers (URIs), typed or untyped literals (constants) and blank nodes (unknown URIs or literals). The RDF standard [START_REF] W3c | Resource description framework[END_REF] includes the property rdf∶type (τ in short), which allows specifying the type(s) or class(es), of a resource. Each resource can have zero, one or several types, which may or may not be related. We call the set of G triples, whose property is τ , the type triples of G, denoted TG. RDF Schema and entailment. G may include a schema (ontology), denoted SG, and expressed through RDF Schema (RDFS) triples using one of the following standard properties: subclass, subproperty, domain and range, which we denote by the symbols ≺ sc , ≺ sp , ↩ d and ↪ r , respectively. Our proposal is beneficial in the presence of ≺ sc schema statements; we do not constrain SG in any way.

RDF entailment is the mechanism through which implicit RDF triples are derived from explicit triples and schema information. In this work, we consider four entailment rules, each based on one of the four properties above: (i) c 1 ≺ sc c 2 means any resource of type c 1 is also of type c 2 ; (ii) p 1 ≺ sp p 2 means that as long as a triple s p 1 o belongs to G, the triple s p 2 o also holds in G; (iii) p ↩ d c means that any resource s having the property p in G is of type c, that is, s τ c holds in G; finally (iv) p ↪ r c means that any resource that is a value of the property p in G, is also of type c.

The fixpoint obtained by applying entailment rules on the triples of G and the schema rules in SG until no new triple is entailed, is termed saturation (or closure) of G and denoted G ∞ . The saturation of an RDF graph is unique (up to blank node renaming), and does not contain implicit triples (they have all been made explicit by saturation).

We view an RDF graph G as: G = SG ⊍ TG ⊍ DG , where the schema SG and the type triples TG have been defined above; DG contains all the remaining triples, whose property is neither τ nor ≺ sc , ≺ sp , ↩ d or ↪ r . We call DG the data triples of G.

In the presence of an RDFS ontology, the semantics of an RDF graph is its saturation; in particular, the answers to a query posed on G must take into account all triples in G ∞ [START_REF] W3c | Resource description framework[END_REF].

Figure 1 shows an RDF graph we will use for illustration in the paper. Schema nodes and triples are shown in blue; type triples are shown in dotted lines; boxed nodes denote URIs of classes and instances, while d1, d2, e1 etc. denote literal nodes; "desc" stands for "description".

B. Quotient RDF summaries

We recall the summarization framework introduced in [START_REF]A framework for efficient representative summarization of RDF graphs[END_REF]. In a graph G, a class node is an URI appearing as subject or object in a ≺ sc triple, as object in a ↩ d or ↪ r triple, or as object in a τ triple. A property node is an URI appearing as subject or object in a ≺ sp triple, or as subject in a ↩ d or ↪ r triple. The framework brings a generic notion of equivalence among RDF nodes:

Definition 1: (RDF EQUIVALENCE) Let ≡ be a binary relation between the nodes of an RDF graph. We say ≡ is an RDF equivalence relation iff (i) ≡ is reflexive, symmetric and transitive, (ii) any class node is equivalent w.r.t. ≡ only to itself, and (iii) any property node is equivalent w.r.t. ≡ only to itself.

Graph nodes which are equivalent will be summarized (or represented) by the same node in the summary. The reason behind class and property nodes being only equivalent to themselves in every RDF equivalence relation, is to ensure that each such node is preserved in the summary, as they appear in the schema and carry important information for the graph's semantics. A summary is defined as follows:

Definition 2: (RDF SUMMARY) Given an RDF graph G and an RDF node equivalence relation ≡, the summary of G by ≡ is an RDF graph denoted G ≡ and defined as follows:

• G ≡ contains exactly one node for each equivalence class of G nodes through ≡; each such node has a distinct, "fresh" URI (that does not appear in G).

• For each triple s p o ∈ G such that s ≡ , o ≡ are the G ≡ nodes corresponding to the equivalence classes of s and o, the triple s ≡ p o ≡ belongs to G ≡ .

The above definition can also be stated "G ≡ is the quotient graph of G by the equivalence relation ≡", based on the classical notion of quotient graph1 . We make two observations:

• Regardless of the chosen ≡, all SG triples are also part of G ≡ , as class and property nodes are represented by themselves, and thanks to the way G ≡ edges are defined; indeed, G and G ≡ have the same schema;

• No particular treatment is given to type triples: how to take them into account is left to each individual ≡. Different RDF equivalence relations lead to different summaries. At one extreme, if all data nodes are equivalent, the summary has a single data node; on the contrary, if ≡ is "empty" (each node is equivalent only to itself), the summary degenerates into G itself. Well-studied equivalence relations for graph quotient summaries are based on the so-called forward, backward, or forward and backward (FB) bisimulation [START_REF] Milo | Index structures for path expressions[END_REF], [START_REF] Chen | D(K)-index: An adaptive structural summary for graph-structured data[END_REF], [START_REF] Kaushik | Covering indexes for branching path queries[END_REF], [START_REF] Li | Indexing and querying XML data for regular path expressions[END_REF]. It has been noted though, e.g. in [START_REF] Khatchadourian | Constructing bisimulation summaries on a multi-core graph processing framework[END_REF], that RDF graphs exhibit so much structural heterogeneity that bisimulationbased summaries are very large, almost of the size of G, thus not very useful. In contrast, [START_REF]Query-oriented summarization of RDF graphs[END_REF], [START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF] introduced ≡ relations which lead to compact summaries, many orders of magnitude smaller than the original graphs.

C. Types in summarization: first or last?

Let us consider how type triples can be used in quotient RDF summaries. Two approaches have been studied in the literature, and in particular in quotient summaries. The approach we will call data-first focuses on summarizing the data (or structure) of G, and then carries (or copies) the possible types of G nodes, to the summary nodes representing them. Conversely, type-first approaches summarize graph nodes first (or only) by their types. Below, we recall two quotient summaries described in [START_REF]Query-oriented summarization of RDF graphs[END_REF], [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF], which are the starting point of this work; they are both very compact, and illustrate the data-first and typefirst approaches respectively. They both rely on the notion of property cliques: Definition 3: (PROPERTY RELATIONS AND CLIQUES) Let p 1 , p 2 be two data properties in DG: For example, in Figure 1, the properties email and webpage are source-related since Alice is the subject of both; webpage and officeHours are source-related due to Bob; also due to Alice, registeredIn and attends are source-related to the above properties, leading to a source clique SC 1 = {attends, email, webpage, officeHours, registeredIn}. Another source clique is SC 2 = {desc, givenIn}.

It is easy to see that the set of non-empty source (or target) property cliques is a partition over the data properties of DG. Further, all data properties of a resource r ∈ G are all in the same source clique, which we denote SC(r); similarly, all the properties of which r is a value are in the same target clique, denoted T C(r). If r is not the value of any property (respectively, has no property), we consider its target (respectively, source) is ∅. For instance, in our example, SC 1 is the source clique of Alice, Bob, Carole and David, while Figure 2 shows the weak summary of our sample RDF graph. The URIs W 1 to W 6 are "new" summary nodes, representing literals and/or URIs from G. Thus, W 3 represents Alice, Bob, Carole and David together, due to their common source clique SC 1 . W 3 represents the course and the master program, due to their common source clique SC 2 . Note that the givenIn edge from G leads to a summary edge from W 2 to itself; also, W 1 carries over the types of the nodes it represents, thus it is both of type MasterProgram and MasterCourse. This example shows that data-first summarization may represent together G resources whose types clearly indicate their different meaning; this may be confusing.

In contrast, the typed weak [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF] summary recalled below illustrates the type-first approach:

Let ≡ T be an RDF equivalence relation which holds on two nodes iff they have the exact same set of types.

Let ≡ UW be an RDF equivalence relation which holds on two nodes iff (i) they have no type, and (ii) they are weakly equivalent.

Definition 6: (TYPED WEAK SUMMARY) The typed weak summary of an RDF graph G, denoted G TW , is the summary through ≡ UW of the summary through ≡ T of G:

G TW = (G ≡T ) ≡UW This double-quotient summarization acts as follows. First, nodes are grouped by their sets of types (inner quotient through ≡ T ); second, untyped nodes only are grouped according to weak (structural) equivalence.

For instance, our sample G has six typed data nodes (Alice to David, BigDataMaster and HadoopCourse), each of which has a set of exactly one type; all these types are different. Thus, ≡ T is empty, and G TW (drawing omitted) has eight typed nodes U T W 1 to U T W 8 , each with a distinct type and the property(ies) of one of these nodes. We now consider G's eight untyped data nodes. We have d1 ≡ W d2 due to their common target clique {desc}, and similarly w1 ≡ W w2 and h2 ≡ W h3 ≡ W h4. Thus, G TW has four untyped nodes, each of which is an object of desc, email, webpage and respectively officeHours triples.

The typed weak summary, as well as other type-first summaries, e.g. [START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF], also have limitations:

• They are defined based on the type triples of G, which may change through saturation, leading to different G TW summaries for conceptually the same graph (as all G leading to the same G ∞ are equivalent). Thus, for a typefirst summary to be most meaningful, one should build it on the saturated graph G ∞ . Note the reason for saturation at Figure 8 in [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF].

• They do not exploit the relationships which the ontology may state among the types. For instance, AssistantProfessor nodes like Carole are summarized separately from Professors like David, although they are all instructors.

III. SUMMARIZATION AWARE OF TYPE HIERARCHIES

A. Novel type-based RDF equivalence

Our first goal is to define an RDF equivalence relation which:

1) takes type information into account, thus belongs to the "types-first" approach; 2) leads (through Definition 2) to a summary which represents together, to the extent possible (see below), nodes that have the same most general type. Formally, let C = {c 1 , c 2 , . . . , } be the set of class nodes present in G (that is, in SG and/or in TG). We can view these nodes as organized in a directed graph where there is an edge c 1 → c 2 as long as G's saturated schema SG ∞ states that c 1 is a subclass of c 2 . By a slight abuse of notation, we use C to also refer to this graph2 . In principle, C could have cycles, but this does not appear to correspond to meaningful schema designs. Therefore, we assume without loss of generality that C is a directed acyclic graph (DAG, in short) 3 . In Figure 1, C is the DAG comprising the eight (blue) class nodes and edges between them; this DAG has four roots.

First, assume that C is a tree, e.g., with Instructor as a root type and PhDStudent, AssistantProfessor as its subclasses. In such a case, we would like instances of all the abovementioned types to be represented together, because they are all instances of the top type Instructor. This extends easily to the case when C is a forest, e.g., a second type hierarchy in C could feature In general, though, C may not be a forest, but instead it may be a graph where some classes have multiple superclasses, potentially unrelated. For instance, in Figure 1, PhDStudent has two superclasses, Student and Instructor. Therefore, it is not possible to represent G nodes of type PhDStudent based on their most general type, because they have more than one such type. Representing them twice (once as Instructor, once as Student) would violate the framework (Definition 2), in which any summary is a quotient and thus, each G node must be represented by exactly one summary node.

To represent resources as much as possible according to their most general type, we proceed as follows.

Definition 7: (TREE COVER) Given a DAG C, we call a tree cover of C a set of trees such that: (i) each node in C appears in exactly one tree; (ii) together, they contain all the nodes of C; and (iii) each C edge appears either in one tree or connects the root of one tree to a node in another.

Given C admits many tree covers, however, it can be shown that there exists a tree cover with the least possible number of trees, which we will call min-size cover. This cover can be computed in a single traversal of the graph by creating a tree root exactly from each C node having two supertypes such that none is a supertype of the other, and attaching to it all its descendants which are not themselves roots of another tree. For instance, the RDF schema from Figure 1 leads to a min-size cover of five trees:

• A tree rooted at Instructor and the edges connecting it to its children AssistantProfessor and Professor;

• A single-node tree rooted at PhDStudent;

• A tree rooted at Student with its child MasterStudent;

• A single-node tree for MasterProgram and another for MasterCourse.

Figure 3 illustrates min-size covers on a more complex RDF schema, consisting of the types A to Q. Every arrow goes from a type to one of its supertypes (for readability, the figure does not include all the implicit subclass relationships, e.g., that E is also a subclass of H, I, J etc.). The pink areas each denote a tree in the corresponding min-size cover. H and L are tree roots because they have multiple, unrelated supertypes.

To complete our proposal, we need to make an extra hypothesis on G:

( †) Whenever a data node n is of two distinct types c 1 , c 2 which are not in the same tree in the min-size tree cover of C, then (i) c 1 and c 2 have some common subclasses, (ii) among these, there exists a class c 1,2 that is a superclass of all the others, and (iii) n is of type c 1,2 .

For instance, in our example, hypothesis ( †) states that if a node n is an Instructor and a Student, these two types must have a common subclass (in our case, this is PhDStudent), and n must be of type PhDStudent. The hypothesis would be violated if there was another common subclass of Instructor and Student, say MusicLover4 , that was neither a subclass of PhDStudent nor a superclass of it.

( †) may be checked by a SPARQL query on G. While it may not hold, we have not found such counter-examples in a set of RDF graphs we have examined (see Section IV). In particular, ( †) immediately holds in the frequent case when C is a tree (taxonomy) or, more generally, a forest: in such cases, the min-size cover of C is exactly its set of trees, and any types c 1 , c 2 of a data node n are in the same tree.

( †) holds, we can state: Lemma 1 (Lowest branching type): Let G be an RDF graph satisfying ( †), n be a data node in G, cs n be the set of types of n in G, and cs ∞ n be the classes from cs n together with all their superclasses (according to the saturated schema of G). Assume that cs ∞ n ≠ ∅. Then there exists a type lbt n , called lowest branching type, such that:

• cs ∞ n = cs ′ n ⊍ cs ′′ n
, where {lbt n } ∈ cs ′ n and cs ′′ n may be empty;

• the types in cs ′ n (if any) can be arranged in a tree according to ≺ sc relation between them, and the most general one is lbt n ;

• if cs ′′ n is not empty, it is at least of size two, and all its types are superclasses of lbt n . Proof: Let's assume to the contrary that there exists an RDF graph G 1 satisfying ( †), a node n in G 1 , cs n the set of types of n, cs ∞ n ≠ ∅ is the set of types of n with all their supertypes (according to saturated schema of G 1 ) and there is no lowest branching type for n.

Let G be the set of all such RDF graphs and let G be the G graph containing a node n that violates the lemma and such that cs ∞ n is the smallest, across all such lemma-violating nodes n in any graph from G.

Let k = cs ∞ n . Note that k > 0 by definition. Let's consider the cases:

1) k = 1 In this case, the lemma trivially holds. From the above discussion, it follows that Carole ≡ TH David, matching the intuition that they are both instructors and do not belong to other type hierarchies. In contrast, PhD students (such as Bob) are only type-hierarchy equivalent to each other; they are set apart by their dual Student and Instructor status. Master students such as Alice are only type-hierarchy equivalent among themselves, as they only belong to the student type hierarchy. Every other typed node of G is only type-hierarchy equivalent to itself. More summaries based on ≡ TH could be obtained by replacing UW with another RDF equivalence relation.

IV. ALGORITHM AND APPLICATIONS

A. Constructing the weak type-hierarchy summary

An algorithm which builds G WTH is as follows:

1) From SG, build C and its min-size cover.

2) For every typed node n of G, identify its lowest branching type lbt n and (the first time a given lbt n is encountered) create a new URI U RI lbtn : this will be the G WTH node representing all the typed G nodes having the same lbt n . 3) Build the weak summary of the untyped nodes of G, using the algorithm described in [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF]. This creates the untyped nodes in G WTH and all the triples connecting them.

4) Add type edges: for every triple n τ c in G, add (unless already in the summary) the triple U RI lbtn τ c to G WTH . 5) Connect the typed and untyped summary nodes: for every triple n 1 p n 2 in G such that n 1 has types in G and n 2 does not, add (unless already in the summary) the triple U RI lbtn 1 p U W n2 to G WTH , where U W n2 is the node representing n 2 , in the weak summary of the untyped part of G. Apply a similar procedure for the converse case (when n 1 has no types but n 2 does).

Step 1) is the fastest as it applies on the schema, typically orders of magnitude smaller than the data. The cost of the steps 2)-4) depend on the distribution of nodes (typed or untyped) and triples (type triples; data triples between typed/untyped nodes) in G. [START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF] presents an efficient, almost-linear time (in the size of G) weak summarization algorithm (step 3). The complexity of the other steps is linear in the number of triples in G, leading to an overall almost-linear complexity.

B. Applicability

To understand if G WTH summarization is helpful for an RDF graph, the following questions should be answered:

1) Does SG feature subclass hierarchies? If it does not, then G WTH reduces to the weak summary G TW . 2) Does SG feature a class with two unrelated superclasses? a) No: then C is a tree or a forest. In this case, G WTH represents every typed node together with all the nodes whose type belong to the same type hierarchy (tree). b) Yes: then, does G satisfy ( †)?

i) Yes: one can build G WTH to obtain a refined representation of nodes according to the lowest branching type in their type hierarchy. ii) No: G WTH is undefined, due to the lack of a unique representative for the node(s) violating ( †). Among the RDF datasets frequently used, DBLP 5 , the BSBM benchmark [START_REF] Bizer | The Berlin SPARQL Benchmark[END_REF], and the real-life Slegger ontology 6whose description has been recently published [START_REF] Hovland | Ontology-based data access to slegge[END_REF] exhibited subclass hierarchies. Further, BSBM graphs and the Slegger ontology feature multiple inheritance. BSBM graphs satisfy ( †). On Slegger we were unable to check this, as the data is not publicly shared; our understanding of the application though as described implies that ( †) holds.

An older study [START_REF] Magkanaraki | Benchmarking RDF schemas for the semantic web[END_REF] of many concrete RDF Schemas notes a high frequence of class hierarchies, of depth going up to 12, as well as a relatively high incidence of multiple inheritance; graphs with such schema benefit from G WTH summarization when our hypothesis ( †) holds.

Figure 1 :

 1 Figure 1: Sample RDF graph.

  1) p 1 , p 2 ∈ G are source-related iff either: (i) a data node in DG is the subject of both p 1 and p 2 , or (ii) DG holds a data node r and a data property p 3 such that r is the subject of p 1 and p 3 , with p 3 and p 2 being source-related. 2) p 1 , p 2 ∈ G are target-related iff either: (i) a data node in DG is the object of both p 1 and p 2 , or (ii) DG holds a data node r and a data property p 3 such that r is the object of p 1 and p 3 , with p 3 and p 2 being target-related. A maximal set of properties in DG which are pairwise source-related (respectively, target-related) is called a source (respectively, target) property clique.

  SC 2 is the source clique of the BigDataMaster and of the HadoopCourse. Definition 4: (WEAK EQUIVALENCE) Two data nodes are weakly equivalent, denoted n 1 ≡ W n 2 , iff: (i) they have the same non-empty source or non-empty target clique, or (ii) they both have empty source and empty target cliques, or (iii) they are both weakly equivalent to another node of G.

Figure 2 :

 2 Figure 2: Weak summary of the sample RDF graph in Figure 1. Definition 5: (WEAK SUMMARY) The weak summary of the graph G, denoted G W , is the RDF summary obtained from the weak equivalence ≡ W .Figure2shows the weak summary of our sample RDF graph. The URIs W 1 to W 6 are "new" summary nodes, representing literals and/or URIs from G. Thus, W 3 represents Alice, Bob, Carole and David together, due to their common source clique SC 1 . W 3 represents the course and the master program, due to their common source clique SC 2 . Note that the givenIn edge from G leads to a summary edge from W 2 to itself; also, W 1 carries over the types of the nodes it represents, thus it is both of type MasterProgram and MasterCourse. This example shows that data-first summarization may represent together G resources whose types clearly indicate their different meaning; this may be confusing.In contrast, the typed weak[START_REF] Čebirić | Query-Oriented Summarization of RDF Graphs[END_REF] summary recalled below illustrates the type-first approach:Let ≡ T be an RDF equivalence relation which holds on two nodes iff they have the exact same set of types.Let ≡ UW be an RDF equivalence relation which holds on two nodes iff (i) they have no type, and (ii) they are weakly equivalent.Definition 6: (TYPED WEAK SUMMARY) The typed weak summary of an RDF graph G, denoted G TW , is the summary through ≡ UW of the summary through ≡ T of G:G TW = (G ≡T ) ≡UW This double-quotient summarization acts as follows. First, nodes are grouped by their sets of types (inner quotient through ≡ T ); second, untyped nodes only are grouped according to weak (structural) equivalence.For instance, our sample G has six typed data nodes (Alice to David, BigDataMaster and HadoopCourse), each of which has a set of exactly one type; all these types are different. Thus, ≡ T is empty, and G TW (drawing omitted) has eight typed

Figure 3 :

 3 Figure 3: Sample RDF schema and min-size cover of the corresponding C. a root type Paper whose subclasses are ConferencePaper, JournalPaper etc. In this case, we aim to represent all authors together because they are instances of Paper.In general, though, C may not be a forest, but instead it may be a graph where some classes have multiple superclasses, potentially unrelated. For instance, in Figure1, PhDStudent has two superclasses, Student and Instructor. Therefore, it is not possible to represent G nodes of type PhDStudent based on their most general type, because they have more than one such type. Representing them twice (once as Instructor, once as Student) would violate the framework (Definition 2), in which any summary is a quotient and thus, each G node must be represented by exactly one summary node.To represent resources as much as possible according to their most general type, we proceed as follows.Definition 7: (TREE COVER) Given a DAG C, we call a tree cover of C a set of trees such that: (i) each node in C appears in exactly one tree; (ii) together, they contain all the nodes of C; and (iii) each C edge appears either in one tree or connects the root of one tree to a node in another.Given C admits many tree covers, however, it can be shown that there exists a tree cover with the least possible number of trees, which we will call min-size cover. This cover can be computed in a single traversal of the graph by creating a tree root exactly from each C node having two supertypes such that none is a supertype of the other, and attaching to it all its descendants which are not themselves roots of another tree. For instance, the RDF schema from Figure1leads to a min-size cover of five trees:

Figure 4 :

 4 Figure 4: Weak type-hierarchy summary of the RDF graph in Figure 1. The roots of the trees in the min-size cover of C are underlined. B. RDF summary based on type hierarchy equivalence Based on ≡ TH defined above, and the ≡ UW structural equivalence relation (two nodes are ≡ UW if they have no types, and are weakly equivalent), we introduce a novel summary belonging to the "type-first" approach: Definition 9: (WEAK TYPE-HIERARCHY SUMMARY) The type hierarchy summary of G, denoted G WTH , is the summary through ≡ UW of the summary through ≡ TH of G: G WTH = (G ≡TH ) ≡UW Figure 4 illustrates the G WTH summary of the RDF graph in Figure 1. Different from the weak summary (Figure 2), it does not represent together nodes of unrelated types, such as BigDataMaster and HadoopCourse. At the same time, different from the typed weak summary of the same graph, it does not represent separately each individual, and instead it keeps Carole and David together as they only belong to the instructor type hierarchy.More summaries based on ≡ TH could be obtained by replacing UW with another RDF equivalence relation.

  2) k ≥ 2 In this case, let t 1 , . . . , t k be the types of node n (their order not important).Let's consider graph G ′ which is the same as G but without node n having type t k . From the way we chose G and G ′ , G ′ satisfies the lemma, thus there exists a lowest branching type lbt n for n in G ′ . Now, let's add t k to the types of n in G ′ . There are 3 possibilities: a) t k is a subclass of lbt n . Then lbt n is also lowest branching type after this addition. b) t k is a superclass of lbt n . If it's the only superclass of lbt n then t k is a new lowest branching type, else n still admits the lowest branching type lbt n . c) t k is neither a sub-nor a superclass of lbt n . Then it is in another tree in min-size cover of G, thus by ( †) it follows that t k and some other type between t 1 , . . . , t k-1 have a common subtype which serves as a lowest branching type for n. From the above discussion we conclude that the node n for which k = cs ∞ n is not the lemma counterexample with the smallest k, which contradicts the assumption we made when picking it! Therefore no graph exists in G, thus all Gs satisfy the lemma. ◻ For instance, let n be Bob in Figure 1, then cs n is {PhDStudent}, thus cs ∞ n is {PhDStudent, Student, Instructor}. In this case, lbt n is PhDStudent, cs ′ n is {PhDStudent} and cs ′′ n is {Student, Instructor}. If we take n to be Carole, cs ∞ n is {AssistantProfessor, Instructor}; no type from this set has two distinct superclasses, thus cs ′′ n must be empty, lbt Carole is Instructor, and cs ′ n is {AssistantProfessor, Instructor}. By a similar reasoning, lbt David is Instructor, and lbt Alice is Student. When n has a type without subclasses or superclasses, such as BigData-Master, it leads to cs ′′ n being empty, and cs ′ n is lbt n , the only type of n. Thus, lbt BigDataMaster is MasterProgram and lbt HadoopCourse is MasterCourse. For a more complex example, recall the RDF schema in Figure 3, and let n be a node of type E in an RDF graph having this schema. In this case, cs n is {E, G, H, B, I, J}, lbt n is H, cs ′ n is {E, G, H} while cs ′′ n is {B, I, J}. Based on Lemma 1, we define our novel notion of equivalence, reflecting the hierarchy among the types of G data nodes: Definition 8: (TYPE-HIERARCHY EQUIVALENCE) Typehierarchy equivalence, denoted ≡ TH , is an RDF node equivalence relation defined as follows: two data nodes n 1 and n 2 are type-hierarchy equivalent, noted n 1 ≡ TH n 2 , iff lbt n1 = lbt n2 .

https://en.wikipedia.org/wiki/Quotient graph

Ontology languages such as RDF Schema or OWL feature a top type, that is a supertype of any other type, such as rdfs:Resource. We do not include such a generic, top type in C.

If C has cycles, the types in each cycle can all be seen as equivalent, as each is a specialization of all the other, and could be replaced by a single (new) type in a simplified ontology. The process can be repeated until C becomes a DAG, then the approach below can be applied, following which the simplified types can be restored, replacing the ones we introduced. We omit the details.

MusicLover may be a subclass of yet another class (distinct type c 3 in third other min-size tree) and it would still violate the hypothesis

http://dblp.uni-trier.de/

http://slegger.gitlab.io/


Joseph Frédéric Bonnans

Axel Kröner
email: axel.kroener@math.hu-berlin.de

J Fr Éd

Éric Bonnans
email: eric.bonnans@inria.fr

Axel Kr Öner

Variational analysis

Keywords: finance, options, partial differential equations, variational formulation, parabolic variational inequalities AMS subject classifications. 35K20, 35K85, 91G80

HAL is

Introduction.

In this paper we consider variational analysis for the partial differential equations associated with the pricing of European or American options. For an introduction to these models, see Fouque et al., [START_REF] Fouque | Derivatives in financial markets with stochastic volatility[END_REF]. We will set up a general framework of variable volatility models, which is in particular applicable on the following standard models which are well established in mathematical finance.

The well-posedness of PDE formulations of variable volatility poblems was studied in [START_REF] Achdou | Computational methods for option pricing[END_REF][START_REF] Achdou | Variational analysis for the Black and Scholes equation with stochastic volatility[END_REF][START_REF] Achdou | A partial differential equation connected to option pricing with stochastic volatility: regularity results and discretization[END_REF][START_REF] Pironneau | Partial differential equations for option pricing, Handbook of numerical analysis[END_REF], and in the recent work [START_REF] Feehan | Schauder a priori estimates and regularity of solutions to boundary-degenerate elliptic linear second-order partial differential equations[END_REF][START_REF] Feehan | Degenerate-elliptic operators in mathematical finance and higher-order regularity for solutions to variational equations[END_REF].

Let the W i (t) be Brownian motions on a filtered probability space. The variable s denotes a financial asset, and the components of y are factors that influence the volatility:

(i) The Achdou-Tchou model [START_REF] Achdou | Variational analysis for the Black and Scholes equation with stochastic volatility[END_REF], see also Achdou, Franchi, and Tchou [START_REF] Achdou | A partial differential equation connected to option pricing with stochastic volatility: regularity results and discretization[END_REF]:

(1. [START_REF] Achdou | A partial differential equation connected to option pricing with stochastic volatility: regularity results and discretization[END_REF] ds(t) = rs(t)dt + σ(y(t))s(t)dW 1 (t), dy(t) = θ(µ -y(t))dt + νdW 2 (t), with the interest rate r, the volatility coefficient σ function of the factor y whose dynamics involves a parameter ν > 0, and positive constants θ and µ.

(ii) The Heston model [START_REF] Heston | A closed-form solution for options with stochastic volatility with applications to bond and currency options[END_REF] (1.2) ds(t) = s(t) rdt + y(t)dW 1 (t) , dy(t) = θ(µ -y(t))dt + ν y(t)dW 2 (t).

(iii) The Double Heston model, see Christoffersen, Heston and Jacobs [START_REF] Jacobs | The shape and term structure of the index option smirk: Why multifactor stochastic volatility models work so well[END_REF], and also Gauthier and Possamaï [START_REF] Gauthier | Efficient simulation of the double Heston model[END_REF]:

(1.3)     
ds(t) = s(t) rdt + y 1 (t)dW 1 (t) + y 2 (t)dW 2 (t) , dy 1 (t) = θ 1 (µ 1 -y 1 (t))dt + ν 1 y 1 (t)dW 3 (t), dy 2 (t) = θ 2 (µ 2 -y 2 (t))dt + ν 2 y 2 (t)dW 4 (t).

In the last two models we have similar interpretations of the coefficients;

in the double Heston model, denoting by •, • the correlation coefficients, we assume that there are correlations only between W 1 and W 3 , and W 2 and W 4 .

Consider now the general multiple factor model

(1.4) ds = rs(t)dt + N k=1 f k (y k (t))s β k (t)dW k (t), dy k = θ k (µ k -y k (t))dt + g k (y k (t))dW N +k (t), k = 1, . . . , N.

Here the y k are volatility factors, f k (y k ) represents the volatility coefficient due to y k , g k (y k ) is a volatility coefficient in the dynamics of the kth factor with positive constants θ k and µ k . Let us denote the correlation between the ith and jth Brownian motions by κ ij : this is a measurable function of (s, y, t) with value in [0, 1] (here s ∈ (0, ∞) and y k belongs to either (0, ∞) or R), see below. We asssume that we have nonzero correlations only between the Brownian motions W k and W N +k , for k = 1 to N , i.e. (1.5) κ ij = 0 if i = j and |j -i| = N .

Note that, in some of the main results, we will assume for the sake of simplicity that the correlations are constant.

We apply the developed analysis to a subclass of stochastic volatility models, obtained by assuming that κ is constant and

(1.6) |f k (y k )| = |y k | γ k ; |g k (y k )| = ν k |y k | 1-γ k ; β k ∈ (0, 1]; ν k > 0; γ k ∈ (0, ∞).
This covers in particular a variant of the Achdou and Tchou model with multiple factors (VAT), when γ k = 1, as well as a generalized multiple factor Heston model (GMH), when γ k = 1/2, i.e., for k = 1 to N :

(1.7) VAT:

f k (y k ) = y k , g k (y k ) = ν k , GMH: f k (y k ) = √ y k , g k (y k ) = ν k √ y k .
For a general class of stochastic volatility models with correlation we refer to Lions and Musiela [START_REF] Lions | Correlations and bounds for stochastic volatility models[END_REF].

The main contribution of this paper is variational analysis for the pricing equation corresponding to the above general class in the sense of the Feynman-Kac theory.

This requires in particular to prove continuity and coercivity properties of the corresponding bilinear form in weighted Sobolev spaces H and V , respectively, which have the Gelfand property and allow the application of the Lions and Magenes theory [START_REF] Lions | Non-homogeneous boundary value problems and applications[END_REF] recalled in Appendix A and the regularity theory for parabolic variational inequalities recalled in Appendix B. A special emphasis is given to the continuity analysis of the rate term in the pricing equation. Two approaches are presented, the standard one and an extension of the one based on the commutator of first-order differential operators as in Achdou and Tchou [START_REF] Achdou | Variational analysis for the Black and Scholes equation with stochastic volatility[END_REF], extended to the Heston model setting by Achdou and Pironneau [START_REF] Pironneau | Partial differential equations for option pricing, Handbook of numerical analysis[END_REF]. Our main result is that the commutator analysis gives stronger results for the subclass defined by (1.6), generalizing the particular cases of the VAT and GMH classes, see remarks 6.2 and 6.4. In particular we extend some of the results by [START_REF] Achdou | Variational analysis for the Black and Scholes equation with stochastic volatility[END_REF].

This paper is organized as follows. In section 2 we give the expression of the bilinear form associated with the original PDE, and check the hypotheses of continuity and semi-coercivity of this bilinear form. In section 3 we show how to refine this analysis by taking into account the commutators of the first-order differential operators

This manuscript is for review purposes only.

associated with the variational formulation. In section 4 we show how to compute the weighting function involved in the bilinear form. In section 5 we develop the results for a general class introduced in the next section. In section 6 we specialize the results to stochastic volatility models. The appendix recalls the main results of the variational theory for parabolic equations, with a discussion on the characterization of the V functional spaces in the case of one dimensional problems.

Notation. We assume that the domain Ω of the PDEs to be considered in the sequel of this paper has the following structure. Let (I, J) be a partition of {0, . . . , N }, with 0 ∈ J, and

(1.8) Ω := N Π k=0 Ω k ; with Ω k := R when k ∈ I, (0, ∞) when k ∈ J.
Let L 0 (Ω) denote the space of measurable functions over Ω. For a given weighting function ρ : Ω → R of class C 1 , with positive values, we define the weighted space

(1.9) L 2,ρ (Ω) := {v ∈ L 0 (Ω); Ω v(x) 2 ρ(x)dx < ∞},
which is a Hilbert space endowed with the norm

(1.10) v ρ := Ω v(x) 2 ρ(x)dx 1/2
.

By D(Ω) we denote the space of C ∞ functions with compact support in Ω. By H 2 loc (Ω) we denote the space of functions over Ω whose product with an element of D(Ω) belongs to the Sobolev space H 2 (Ω).

Besides, let Φ be a vector field over Ω (i.e., a mapping Ω → R n ). The first-order differential operator associated with Φ is, for u : Ω → R the function over Ω defined by

(1.11) Φ[u](x) := n i=0 Φ i (x) ∂u ∂x i (x), for all x ∈ Ω.
2. General setting. Here we give compute the bilinear form associated with the original PDE, in the setting of the general multiple factor model (1.4). Then we will check the hypotheses of continuity and semi-coercivity of this bilinear form.

2.1. Variational formulation. We compute the bilinear form of the variational setting, taking into account a general weight function. We wil see how to choose the functional spaces for a given ρ, and then how to choose the weight itself.

2.1.1. The elliptic operator. In financial models the underlying is solution of stochastic differential equations of the form

dX(t) = b(t, X(t))dt + nσ i=1 σ i (t, X(t))dW i . (2.1)
Here X(t) takes values in Ω, defined in (1.8). That is, X 1 corresponds to the s variable, and X k+1 , for k = 1 to N , corresponds to y k . We have that n σ = 2N . So, b and σ i , for i = 1 to n σ , are mappings (0, T ) × Ω → R n , and the W i , for i = 1 to n σ , are standard Brownian processes with correlation κ ij : (0, T ) × Ω → R This manuscript is for review purposes only.

between W i and W j for i, j ∈ {1, . . . , n σ }. The n σ × n σ symmetric correlation matrix

κ(•, •) is nonnegative with unit diagonal: (2.2) κ(t, x) 0; κ ii = 1, i = 1, . . . , n σ , for a.a. (t, x) ∈ (0, T ) × Ω.
Here, for symmetric matrices B and C of same size, by "C B" we mean that C -B is positive semidefinite. The expression of the second order differential operator A corresponding to the dynamics (2.1) is, skipping the time and space arguments, for u : (0, T ) × Ω → R:

(2.3) Au := ru -b • ∇u -1 2 nσ i,j=1 κ ij σ j u xx σ i , where (2.4) σ j u xx σ i := nσ k, =1 σ kj ∂u 2 ∂x k ∂x σ i , r(x, t
) represents an interest rate, and u xx is the matrix of second derivatives in space of u. The associated backward PDE for a European option is of the form

(2.5) -u(t, x) + A(t, x)u(t, x) = f (t, x), (t, x) ∈ (0, T ) × Ω; u(x, T ) = u T (x), x ∈ Ω,
with u the notation for the time derivative of u, u T (x) payoff at final time (horizon)

T and the r.h.s. f (t, x) represents dividends (often equal to zero).

In case of an American option we obtain a variational inequality; for details we refer to Appendix D. since v ∈ D(Ω) there will be no contribution from the boundary. We obtain

(2.7) -1 2 Ω σ j u xx σ i vκ ij ρ = 3 p=0 a p ij (u, v), with (2.8) a 0 ij (u, v) := 1 2 Ω n k, =1 σ kj σ i ∂u ∂x k ∂v ∂x κ ij ρ = 1 2 Ω σ j [u]σ i [v]κ ij ρ, (2.9) a 1 ij (u, v) := 1 2 Ω n k, =1 σ kj σ i ∂u ∂x k ∂(κ ij ρ) ∂x v = 1 2 Ω σ j [u]σ i [κ ij ρ] v ρ ρ, (2.10) a 2 ij (u, v) := 1 2 Ω n k, =1 σ kj ∂(σ i ) ∂x ∂u ∂x k vκ ij ρ = 1 2 Ω σ j [u](div σ i )vκ ij ρ,
This manuscript is for review purposes only.

(2.11)

a 3 ij (u, v) := 1 2 Ω n k, =1 ∂(σ kj ) ∂x σ i ∂u ∂x k vκ ij ρ = 1 2 Ω n k=1 σ i [σ kj ] ∂u ∂x k vκ ij ρ.
Also, for the contributions of the first and zero order terms resp. we get (2.12)

a 4 (u, v) := - Ω b[u]vρ; a 5 (u, v) := Ω ruvρ.

Set

(2.13)

a p := nσ i,j=1
a p ij , p = 0, . . . , 3.

The bilinear form associated with the above PDE is

(2.14) a(u, v) := 5 p=0 a p (u, v).
From the previous discussion we deduce that Lemma 2.1. Let u ∈ H 2 oc (Ω) and v ∈ D(Ω). Then we have that

(2.15) a(u, v) = Ω A(t, x)u(x)v(x)ρ(x)dx.
2.1.3. The Gelfand triple. We can view a 0 as the principal term of the bilinear form a(u, v). Let σ denote the n × n σ matrix whose σ j are the columns. Then (2.16)

a 0 (u, v) = nσ i,j=1 Ω σ j [u]σ i [v]κ ij ρ = Ω ∇u σκσ ∇vρ.
Since κ 0, the above integrand is nonnegative when u = v; therefore, a 0 (u, u) ≥ 0.

When κ is the identity we have that a 0 (u, u) is equal to the seminorm a 00 (u, u), where (2.17)

a 00 (u, u) := Ω |σ ∇u| 2 ρ.
In the presence of correlations it is natural to assume that we have a coercivity of the same order. That is, we assume that (2.18) For some γ ∈ (0, 1]: σκσ γσσ , for all (t, x) ∈ (0, T ) × Ω. This manuscript is for review purposes only.

We need to choose a pair (V, H) of Hilbert spaces satisfying the Gelfand conditions for the variational setting of Appendix A, namely V densely and continuously embedded in H, a(•, •) continuous and semi-coercive over V . Additionally, the r.h.s.

and final condition of (2.5) should belong to L 2 (0, T ; V * ) and H resp. (and for the second parabolic estimate, to L 2 (0, T ; H) and V resp. ).

We do as follows: for some measurable function h : Ω → R + to be specified later we define

(2.21)

   H := {v ∈ L 0 (Ω); hv ∈ L 2,ρ (Ω)}, V := {v ∈ H; σ i [v] ∈ L 2,ρ (Ω), i = 1, . . . , n σ }, V := {closure of D(Ω) in V},
endowed with the natural norms,

(2.22) v H := hv ρ ; u 2 V := a 00 (u, u) + u 2 H .
We do not try to characterize the space V since this is problem dependent.

Obviously, a 0 (u, v) is a bilinear continuous form over V. We next need to choose h so that a(u, v) is a bilinear and semi-coercive continuous form, and u T ∈ H.

2.2. Continuity and semi-coercivity of the bilinear form over V. We will see that the analysis of a 0 to a 2 is relatively easy. It is less obvious to analyze the term (2.23)

a 34 (u, v) := a 3 (u, v) + a 4 (u, v).
Let qij (t, x) ∈ R n be the vector with kth component equal to

(2.24) qijk := κ ij σ i [σ kj ]. Set (2.25) q := nσ i,j=1 qij , q := q -b.
Then by (2.11)-(2.12), we have that

(2.26) a 34 (u, v) = Ω q[u]vρ.
We next need to assume that it is possible to choose

η k in L 0 ((0, T ) × Ω), for k = 1 to n σ , such that (2.27) q = nσ k=1 η k σ k .
Often the n × n σ matrix σ(t, x) has a.e. rank n. Then the above decomposition is possible. However, the choice for η is not necessarily unique. We will see in examples how to do it. Consider the following hypotheses:

h σ ≤ c σ h, where h σ := nσ i,j=1 |σ i [κ ij ρ]/ρ + κ ij div σ i | , a.e.
, for some c σ > 0, (2.28) h r ≤ c r h, where h r := |r| 1/2 , a.e., for some c r > 0, (2.29)

h η ≤ c η h, where h η := |η|, a.e., for some c η > 0. (2.30)
This manuscript is for review purposes only.

Remark 2.3. Let us set for any differentiable vector field

Z : Ω → R n (2.31) G ρ (Z) := div Z + Z[ρ] ρ .
Since κ ii = 1, (2.28) implies that

(2.32) |G ρ (σ i )| ≤ c σ h, i = 1; . . . , n σ . Remark 2.4. Since (2.33) σ i [κ ij ρ] = σ i [κ ij ]ρ + σ i [ρ]κ ij ,
and |κ ij | ≤ 1 a.e., a sufficient condition for (2.28) is that there exist a positive constants c σ such that

(2.34) h σ ≤ c σ h; h σ := nσ i,j=1 |σ i [κ ij ]| + nσ i=1 (|div σ i | + |σ i [ρ]/ρ|) .
We will see in section 4 how to choose the weight ρ so that |σ i [ρ]/ρ| can be easily estimated as a function of σ.

Lemma 2.5. Let (2.28)-(2.30) hold. Then the bilinear form a(u, v) is both (i) continuous over V , and (ii) semi-coercive, in the sense of (A.5).

Proof. (i)

We have that a 1 + a 2 is continuous, since by (2.9)-(2.10), (2.28) and the Cauchy-Schwarz inequality:

(2.35)

|a 1 (u, v) + a 2 (u, v)| ≤ nσ i,j=1 |a 1 ij (u, v) + a 2 ij (u, v)| ≤ nσ j=1 σ j [u] ρ nσ i=1 (σ i [κ ij ρ]/ρ + κ ij div σ i ) v ρ ≤ c σ n σ v H nσ j=1 σ j [u] ρ .
(ii) Also, a 34 is continuous, since by (2.27) and (2.30):

(2.36)

|a 34 (u, v)| ≤ nσ k=1 σ k [u] ρ η k v ρ ≤ c η v H nσ k=1 σ k [u] ρ . Set c := c σ n σ + c 2 η . By (2.35)-(2.36), we have that (2.37) |a 5 (u, v)| ≤ |r| 1/2 u 2,ρ |r| 1/2 v 2,ρ ≤ c 2 r u H v H , |a 1 (u, v) + a 2 (u, v) + a 34 (u, v)| ≤ ca 00 (u) 1/2 v H .
Since a 0 is obviously continuous, the continuity of a(u, v) follows.

(iii) Semi-coercivity. Using (2.37) and Young's inequality, we get that

(2.38) a(u, u) ≥ a 0 (u, u) -a 1 (u, u) + a 2 (u, u) + a 34 (u, u) -a 5 (u, u) ≥ γa 00 (u) -ca 00 (u) 1/2 u H -c r u 2 H ≥ 1 2 γa 00 (u) -1 2 c 2 γ + c r u 2 H ,
which means that a is semi-coercive.

This manuscript is for review purposes only.

The above consideration allow to derive well-posedness results for parabolic equations and parabolic variational inequalities.

Theorem 2.6. (i) Let (V, H) be given by (2.21), with h satisfying (2.28)-(2.30),

(f, u T ) ∈ L 2 (0, T ; V * )×H. Then equation (2.5) has a unique solution u in L 2 (0, T ; V ) with u ∈ L 2 (0, T ; V * ), and the mapping (f, u T ) → u is nondecreasing. (ii) If in addition the semi-symmetry condition (A.8) holds, then u in L ∞ (0, T ; V ) and u ∈ L 2 (0, T ; H).
Proof. This is a direct consequence of Propositions A.1, A.2 and C.1.

We next consider the case of parabolic variational inequalities associated with the set (2.39) (ii) Let in addition the semi-symmetry condition (A.8) be satisfied. Then u is the unique solution of the strong formulation (B.2), belongs to L ∞ (0, T ; V ), and u belongs to L 2 (0, T ; H).

K := {ψ ∈ V : ψ(x) ≥ Ψ(x) a.e. in
Proof. This follows from Propositions B.1 and C.2.

3. Variational analysis using the commutator analysis. In the following a commutator for first order differential operators is introduced, and calculus rules are derived.

3.1. Commutators. Let u : Ω → R be of class C 2 . Let Φ and Ψ be two vector fields over Ω, both of class C 1 . Recalling (1.11), we may define the commutator of the first-order differential operators associated with Φ and Ψ as

(3.1) [Φ, Ψ][u] := Φ[Ψ[u]] -Ψ[Φ[u]]. Note that (3.2) Φ[Ψ[u]] = n i=1 Φ i ∂(Ψu) ∂x i = n i=1 Φ i n k=1 ∂Ψ k ∂x i ∂u ∂x k + Ψ k ∂ 2 u ∂x k ∂x i .
So, the expression of the commutator is

(3.3) [Φ, Ψ] [u] = n i=1 Φ i n k=1 ∂Ψ k ∂x i ∂u ∂x k -Ψ i n k=1 ∂Φ k ∂x i ∂u ∂x k = n k=1 n i=1 Φ i ∂Ψ k ∂x i -Ψ i ∂Φ k ∂x i ∂u ∂x k .
It is another first-order differential operator associated with a vector field (which happens to be the Lie bracket of Φ and Ψ, see e.g. [START_REF] Aubin | A course in differential geometry[END_REF]).

This manuscript is for review purposes only.

Adjoint.

Remembering that H was defined in (2.21), given two vector fields Φ and Ψ over Ω, we define the spaces

V(Φ, Ψ) := {v ∈ H; Φ[v], Ψ[v] ∈ H} , (3.4) V (Φ, Ψ) := {closure of D(Ω) in V(Φ, Ψ)} . (3.5)
We define the adjoint Φ of Φ (view as an operator over say C ∞ (Ω, R), the latter being endowed with the scalar product of L 2,ρ (Ω)), by

(3.6) Φ [u], v ρ = u, Φ[v] ρ for all u, v ∈ D(Ω),
where •, • ρ denotes the scalar product in L 2,ρ (Ω). Thus, there holds the identity

(3.7) Ω Φ [u](x)v(x)ρ(x)dx = Ω u(x)Φ[v](x)ρ(x)dx for all u, v ∈ D(Ω). Furthermore, (3.8
)

Ω u n i=1 Φ i ∂v ∂x i ρdx = - n i=1 Ω v ∂ ∂x i (uρΦ i )dx = - n i=1 Ω v ∂ ∂x i (uΦ i ) + u ρ Φ i ∂ρ ∂x i ρdx.
Hence,

(3.9) Φ [u] = - n i=1 ∂ ∂x i (uΦ i ) -uΦ i ∂ρ ∂x i /ρ = -u div Φ -Φ[u] -uΦ[ρ]/ρ.
Remembering the definition of G ρ (Φ) in (2.31), we obtain that

(3.10) Φ[u] + Φ [u] + G ρ (Φ)u = 0.

Continuity of the bilinear form associated with the commutator.

Setting, for v and w in V (Φ, Ψ):

(3.11) ∆(u, v) := Ω [Φ, Ψ][u](x)v(x)ρ(x)dx, we have (3.12) ∆(u, v) = Ω (Φ[Ψ[u]]v -Ψ[Φ[u]]v)ρdx = Ω Ψ[u]Φ [v] -Φ[u]Ψ [v])ρdx = Ω (Φ[u]Ψ[v] -Ψ[u]Φ[v]) ρdx + Ω (Φ[u]G ρ (Ψ)v -Ψ[u]G ρ (Φ)v) ρdx.
Lemma 3.1. For ∆(•, •) to be a continuous bilinear form on V (Φ, Ψ), it suffices that, for some c ∆ > 0:

(3.13) |G ρ (Φ)| + |G ρ (Ψ)| ≤ c ∆ h a.e.,
and we have then:

(3.14) |∆(u, v)| ≤ Ψ[u] ρ Φ[v] ρ + c ∆ v H + Φ[u] ρ Ψ[v] ρ + c ∆ v H .
This manuscript is for review purposes only.

Proof. Apply the Cauchy Schwarz inequality to (3.12), and use (3.13) combined with the definition of the space H.

We apply the previous results with Φ := σ i , Ψ := σ j . Set for v, w in V :

(3.15) ∆ ij (u, v) := Ω [σ i , σ j ][u](x)v(x)ρ(x)dx, i, j = 1, . . . , n σ .
We recall that V was defined in (2.21).

Corollary 3.2. Let (2.28) hold. Then the ∆ ij (u, v), i, j = 1, . . . , n σ , are continuous bilinear forms over V .

Proof. Use remark 2.3 and conclude with lemma 3.1.

3.4.

Redefining the space H. In section 2.2 we have obtained the continuity and semi-coercivity of a by decomposing q, defined in (2.26), as a linear combination (2.27) of the σ i . We now take advantage of the previous computation of commutators and assume that, more generally, instead of (2.27), we can decompose q in the form

(3.16) q = nσ k=1 η k σ k + 1≤i<j≤nσ η ij [σ i , σ j ] a.e.
We assume that η and η are measurable functions over [0, T ] × Ω, that η is weakly differentiable, and that for some c η > 0:

(3.17)

h η ≤ c η h, where h η := |η | + N i,j=1 σ i [η ij ] a.e., η ∈ L ∞ (Ω). Lemma 3.
Ω σ k [u]η k vρ ≤ σ k [u] ρ σ k [u]η k v ρ ≤ σ k [u] ρ v H .
(ii) Setting w := η ij v and taking here (Φ, Ψ) = (σ i , σ j ), we get that

(3.19) Ω η ij [σ i , σ j )[u]vρ = ∆(u, w),
where ∆(•, •) was defined in (3.11). Combining with lemma 3.1, we obtain

(3.20) |∆ ij (u, v)| ≤ σ j [u] ρ σ i [w] ρ + c σ η ij ∞ v H + σ i [u] ρ σ j [w] ρ + c σ η ij ∞ v H . Since (3.21) σ i [η ij v] = η ij σ i [v] + σ i [η ij ]v,
This manuscript is for review purposes only.

by (3.17):

(3.22) σ i [w] ρ ≤ η ij ∞ σ i [v] ρ + σ i [η ij ]v ρ ≤ η ij ∞ σ i [v] ρ + c η v H .
Combining these inequalities, point (i) follows.

(ii) Use u = v in (3.21) and (3.12). We find after cancellation in (3.12) that

(3.23) ∆ ij (u, η ij u) = Ω u(σ i [u]σ j [η ij ] -σ j [u]σ i (η ij ))ρ + Ω (σ i [u]G ρ (σ j ) -σ j [u]G ρ (σ i )) η ij uρ.
By (3.17), an upper bound for the absolute value of the first integral is

(3.24) σ i [u] ρ + σ j [u] ρ hu ρ ≤ 2 u V u H .
With (2.28), we get an upper bound for the absolute value of the second integral in the same way, so, for any ε > 0:

(3.25) |∆ ij (u, η ij u)| ≤ 4 u V u H .
We finally have that for some c > 0

(3.26) a(u, u) ≥ a 0 (u, u) -c u V u H , ≥ a 0 (u, u) -1 2 u 2 V -1 2 c 2 u 2 H , = 1 2 u 2 V -1 2 (c 2 + 1) u 2 H .
The conclusion follows.

Remark 3.4. The statements analogous to theorems 2.6 and 2.7 hold, assuming now that h satisfies (2.28), (2.29), and (3.17) (instead of (2.28)-(2.30)). We remind that (I, J) is a partition of {0, . . . , N }, with 0 ∈ J and that Ω was defined in (1.8). , with index from 0 to N . Let G(γ , γ ) be the class of functions ϕ : Ω → R such that for some c > 0:

(4.1) |ϕ(x)| ≤ c Π k∈I (e γ k x k + e -γ k x k ) Π k∈J (x γ k k + x -γ k k
) .

We define G as the union of G(γ , γ ) for all nonnegative (γ , γ ). We call γ k and γ k the growth order of ϕ, w.r.t. x k , at -∞ and +∞ (resp. at zero and +∞).

Observe that the class G is stable by the operations of sum and product, and that if f , g belong to that class, so does h = f g, h having growth orders equal to the sum of the growth orders of f and g. For a ∈ R, we define (4.2) a + := max(0, a); a -:= max(0, -a); N (a) := (a 2 + 1)

1/2 ,
This manuscript is for review purposes only.

as well as

(4.3) ρ := ρ I ρ J ,
where

ρ I (x) := Π k∈I e -α k N (x + k )-α k N (x - k ) , (4.4) ρ J (x) := Π k∈J x α k k 1 + x α k +α k k , (4.5)
for some nonnegative constants α k , α k , to be specified later.

Lemma 4.2. Let ϕ ∈ G(γ , γ ). Then ϕ ∈ L 1,ρ (Ω) whenever ρ is as above, with α satisfying, for some positive ε and ε , for all k = 0 to N :

(4.6) α k = ε + γ k , α k = ε + γ k , k ∈ I, α k = (ε + γ k -1) + , α k = 1 + ε + γ k , k ∈ J.
In addition we can choose for k = 0 (if element of J):

(4.7) α 0 := (ε + γ 0 -1) + ; α 0 := 0 if ϕ(s, y) = 0 when s is far from 0,

α 0 := 0, α 0 := 1 + ε + γ 0 , if ϕ(s, y) = 0 when s is close to 0.
Proof. It is enough to prove (4.6), the proof of (4.7) is similar. We know that ϕ satisfy (4.1) for some c > 0 and γ. We need to check the finiteness of (4.8)

Ω Π k∈I (e γ k y k + e -γ k y k ) Π k∈J (y γ k k + y -γ k k ) ρ(s, y)d(s, y).
But the above integral is equal to the product p I p J with

p I := Π k∈I R (e γ k x k + e -γ k x k )e -α k N (x + k )-α k N (x - k ) dx k , (4.9) p J := Π k∈J R+ x α k +γ k k + x α k -γ k k 1 + x α k +α k k dx k . (4.10)
Using (4.6) we deduce that p I is finite since for instance (4.11)

R+ (e γ k x k + e -γ k x k )e -α k N (x + k )-α k N (x - k ) dx k ≤ 2 R+ e γ k x k e -(1+γ k )x k dx k = 2 R+ e -x k dx k = 2,
and p J is finite since (4.12)

p J = Π k∈J R+ x ε +γ k +γ k k + x ε -1 k 1 + x ε +ε +γ k +γ k k dx k < ∞.

The conclusion follows.

This manuscript is for review purposes only.

4.2. On the growth order of h. Set for all k (4.13)

α k := α k + α k .
Remember that we take ρ in the form (4.3)-(4.4).

Lemma 4.3. We have that:

(i) We have that

(4.14) ρ x k ρ ∞ ≤ α k , k ∈ I; x ρ ρ x k ∞ ≤ α k , k ∈ J.
(ii) Let h satisfying either (2.28)-(2.30) or (2.28)-(2.29), and (3.17). Then the growth order of h does not depend on the choice of the weighting function ρ.

Proof. (i) For k ∈ I this is an easy consequence of the fact that N (•) is non expansive. For k ∈ J, we have that

(4.15) x ρ ρ x k = x ρ α k x α k -1 (1 + x α k ) -x α k α k x α k -1 (1 + x α k ) 2 = α k -α k x α k 1 + x α k .
We easily conclude, discussing the sign of the numerator.

(ii) The dependence of h w.r.t. ρ is only through the last term in (2.28), namely,

i |σ i [ρ]/ρ. By (i) we have that (4.16) σ k i [ρ] ρ ≤ ρ x k ρ ∞ |σ k i | ≤ α k |σ k i |, k ∈ I, (4.17) σ k i [ρ] ρ ≤ x k ρ x k ρ ∞ σ k i x k ≤ α k σ k i x k , k ∈ J.
In both cases, the choice of α has no influence on the growth order of h.

European option.

In the case of a European option with payoff u T (x), we need to check that u T ∈ H, that is, ρ must satisfy (4.18)

Ω |u T (x)| 2 h(x) 2 ρ(x)dx < ∞.
In the framework of the semi-symmetry hypothesis (A.8), we need to check that u T ∈ V , which gives the additional condition

(4.19) nσ i=1 Ω |σ i [u T ](x)| 2 ρ(x)dx < ∞.
In practice the payoff depends only on s and this allows to simplify the analysis.

Applications using the commutator analysis. The commutator analysis

is applied to the general multiple factor model and estimates for the function h characterizing the space H (defined in (2.21)) are derived. The estimates are compared to the case when the commutator analysis is not applied. The resulting improvement wil be established in the next section.

This manuscript is for review purposes only.

Commutator and continuity analysis.

We analyze the general multiple factor model (1.4), which belongs to the class of models (2.1) with Ω ⊂ R 1+N , n σ = 2N , and for i = 1 to N :

(5.1)

σ i [v] = f i (y i )s βi v s ; σ N +i [v] = g i (y i )v i ,
with f i and g i of class C 1 over Ω. We need to compute the commutators of the firstorder differential operators associated with the σ i . The correlations will be denoted

(5.3) [Z, Z ][u] = ab x1 u x2 -ba x2 u x1 .
We obtain that

(5.4) [σ i , σ ][u] = (β -β i )f i (y i )f (y )s βi+β -1 u s , 1 ≤ i < ≤ N, (5.5)
[σ i , σ N +i ][u] = -s βi f i (y i )g i (y i )u s , i = 1, . . . , N, and
(5.6) [σ i , σ N + ][u] = [σ N +i , σ N + ][u] = 0, i = .
Also,

(5.7)

div σ i + σ i [ρ] ρ = f i (y i )s βi-1 (β i + s ρ s ρ ), div σ N +i + σ N +i [ρ] ρ = g i (y i ) + g i (y i ) ρ i ρ .
5.1.1. Computation of q. Remember the definitions of q, q and q in (2.24) and

(2.25), where δ ij denote the Kronecker operator. We obtain that, for 1 ≤ i, j, k ≤ N :

(5.8)

       qij0 = δ ij β j f 2 i (y i )s 2βi-1 ; qiik = 0; qi,N+j = 0; qN+i,j,0 = δ ij κi f (y i )g i (y i )s βi ; qN+i,j,k = 0; qN+i,N+j,k = δ ijk g i (y i )g i (y i ).
That means, we have for q = 2N i,j=1 qij and q = q -b that (5.9)

q0 = N i=1 β i f 2 i (y i )s 2βi-1 + κi f (y i )g i (y i )s βi ; q 0 = q0 -rs, qk = g k (y k )g k (y k ); q k = qk -θ k (µ k -y k ), k = 1, . . . , N.
This manuscript is for review purposes only.

Computation of η and η .

The coefficients η , η are solution of (3.16).

We can write η = η + η, where (5.10)

q = nσ i=1 η i σ i + 1≤i,j≤nσ η ij [σ i , σ j ], η ij = 0 if i = j. -b = nσ i=1 η i σ i + 1≤i,j≤nσ η ij [σ i , σ j ], η ij = 0 if i = j.
For k = 1 to N , this reduces to

(5.11) η N +k g k (y k ) = g k (y k )g k (y k ); η N +k g k (y k ) = -θ k (µ k -y k ).
So, we have that (5.12)

   η N +k = g k (y k ); η N +k = -θ k (µ k -y k ) g k (y k ) .
For the 0th component, (5.10) can be expressed as (5.13)

                     N k=1 -η k,N +k f k (y k )g k (y k )s β k -κk f k (y k )g k (y k )s β k + N k=1 η k f k (y k )s β k -β k f 2 k (y k )s 2β k -1 + N k=1 -η k,N +k f k (y k )g k (y k )s β k + η k f k (y k )s β k -rs = 0.
We choose to set each term in parenthesis in the first two lines above to zero. It

follows that η k,N +k = -κ k ∈ L ∞ (Ω), η k = β k f k (y k )s β k -1 . (5.14)
If N > 1 we (arbitrarily) choose then to set the last line to zero with (5.15) η k = η k = 0, k = 2, . . . , N.

It remains that

η 1 f 1 (y 1 )s β1 -η 1,N +1 f 1 (y 1 )g 1 (y 1 )s β1 = rs. (5.16)
Here, we can choose to take either η 1 = 0 or η 1,N +1 = 0. We obtain then two possibilities:

(5.17)

       (i) η 1 = 0 and η 1,N +1 = -rs 1-β1 f 1 (y 1 )g 1 (y 1 ) , (ii) η 1 = rs 1-β1 f 1 (y 1 ) and η 1,N +1 = 0.
This manuscript is for review purposes only.

Estimate of the h function.

We decide to choose case (i) in (5.17).

The function h needs to satisfy (2.28), (2.29), and (3.17) (instead of (2.30)). Instead of (2.28), we will rather check the stronger condition (2.34). We compute

h σ := N k=1 |f k (y k )|s β k |(κ k ) s | + | ρ s ρ | + |g k (y k )| |(κ k ) k | + | ρ k ρ | (5.18) + N k=1 β k |f k (y k )s β k -1 | + |g k (y k )| , h r := |r| 1 2 , (5.19) h η := ĥ η + h η , (5.20)
where we have ĥ

η := N k=1 β k |f k (y k )|s β k -1 + |g k (y k )| + f k (y k )|s β k ∂κ k ∂s + g k (y k ) ∂κ k ∂y k , (5.21) h η := N k=1 θ k (µ k -y k ) g k (y k ) + r f 1 (y 1 ) f 1 (y 1 )g 1 (y 1 ) + rg 1 (y 1 )s 1-β1 ∂ ∂y 1 1 f 1 (y 1 )g 1 (y 1 )
.

(5.22)

Remark 5.2. Had we chosen (ii) instead of (i) in (5.17), this would only change the expression of h η that would then be

(5.23) h η = N k=1 θ k (µ k -y k ) g k (y k ) + rs 1-β1 f 1 (y 1 ) .

Estimate of the h function without the commutator analysis.

The only change in the estimate of h will be the contribution of h η and h η . We have to satisfy (2.28)-(2.30). In addition, ignoring the commutator analysis, we would solve (5.13) with η = 0, meaning that we choose (5.24)

η k := β k f k (y k )s β k -1 + κk f k (y k )g k (y k ) f k (y k ) , k = 1, . . . , N,
and take η 1 out of (5.16). Then condition (3.17), with here η = 0, would give

(5.25) h ≥ c η h η , where h η := h η + h η , with
h η := N k=1 β k |f k (y k )|s β k -1 + |κ k | f k (y k )g k (y k ) f k (y k ) + |g k (y k )| , (5.26) h η := N k=1 θ k (µ k -y k ) g k (y k ) + rs 1-β1 f 1 (y 1 ) . (5.27)
We will see in applications that this is in general worse.

This manuscript is for review purposes only.

6. Application to stochastic volatility models. The results of Section 5 are specified for a subclass of the multiple factor model, in particular for the VAT and GMH models. We show that the commutator analysis allows to take smaller values for the function h (and consequently to include a larger class of payoff functions).

6.1. A useful subclass. Here we assume that (6.1)

|f k (y k )| = |y k | γ k ; |g k (y k )| = ν k |y k | 1-γ k ; β k ∈ (0, 1]; ν k > 0; γ k ∈ (0, ∞).
Furthermore, we assume κ to be constant and

(6.2) |f k (y k )g k (y k )| = const for all y k , k = 1, . . . , N.
Set (6.3)

c s := sρ s /ρ ∞ ; c k = ρ k /ρ ∞ if Ω k = R, 0 otherwise. c k = 0 if Ω k = R, y k ρ k /ρ ∞ otherwise.
We get, assuming that γ 1 = 0: (6.4)

h σ := N k=1 c s |y k | γ k s β k -1 + ν k c k |y k | 1-γ k +ν k c k |y k | -γ k + β k |y k | γ k s β k -1 + (1 -γ k )ν k |y k | -γ k , ĥ η := N k=1 β k |y k | γ k s β k -1 + (1 -γ k )ν k |y k | -γ k , (6.5) h η := N k=1 θ k |µ k -y k | ν k |y k | 1-γ k + r|y 1 | γ1 γ 1 ν 1 . (6.6)
Therefore when all y k ∈ R, we can choose h as (6.7)

h := 1 + N k=1 |y k | γ k (1 + s β k -1 ) + (1 -γ k )|y k | -γ k + |y k | γ k -1 + k∈I |y k | 1-γ k + k∈J |y k | -γ k .
Without the commutator analysis we would get

ĥη := N k=1 (β k |y k | γ k s β k -1 + ν k |κ k ||y k | -γ k + (1 -γ k )ν k |y k | -γ k ), (6.8) hη := N k=1 θ k |µ k -y k | ν k |y k | 1-γ k + rs 1-β1 |y 1 | -γ1 . (6.9)
This manuscript is for review purposes only.

Therefore we can choose (6.10)

h := h ; h := h + rs 1-β1 /|y 1 | γ1 + k ν k |κ k ||y k | -γ k .
So, we always have that h ≤ h , meaning that it is advantageous to use the commutator analysis, due to the term rs 1-β1 /|y 1 | γ1 above in particular. The last term in the above r.h.s. has as contribution only when γ k = 1 (since otherwise h includes a term of the same order).

Application to the VAT model. For the variant of the Achdou and

Tchou model with multiple factors (VAT), i.e. when γ k = 1, for k = 1 to N , we can take h equal to (6.11)

h T A := 1 + N k=1 |y k |(1 + s β k -1 ),
when the commutator analysis is used, and when it is not, take h equal to (6.12)

h T A := h T A + rs 1-β1 |y 1 | -1 + N k=1 ν k |κ k ||y k | -1 .
Remember that u T (s) = (s -K) + for a call option, and u T (s) = (K -s) + for a put option, both with strike K > 0.

Lemma 6.1. For the VAT model, using the commutator analysis, in case of a call (resp. put) option with strike K > 0, we can take ρ = ρ call , (resp. ρ = ρ put ), with (6.13)

ρ call (s, y) := (1 + s 3+ε ) -1 Π N k=1 e -εN (y k ) , ρ put (s, y) := s α P 1 + s α P Π N k=1 e -εN (y k ) ,
where

α P := ε + 2 N k=1 (1 -β k ) -1 + .
Proof. (i) In the case of a call option, we have that (6.14) 1 ≥ c 0 s β k -1 for c 0 > 0 small enough over the domain of integration, so that we can as well take

(6.15) h(s, y) = 1 + N k=1 |y k | ≤ Π N k=1 (1 + |y k |).
So, we need that ϕ(s, y) ∈ L 1,ρ (Ω), with

(6.16) ϕ(s, y) = h 2 (s, y)u 2 T (s) = (s -K) 2 + Π N k=1 (1 + |y k |) 2 .
By lemma 4.2, where here J = {0} and I = {1, . . . , N }, we may take resp.

(6.17)

γ 0 = 2, γ 0 = 0, γ k > 0, γ k > 0, k = 1, . . . , N,
and so we may choose for ε > 0 and ε > 0:

(6.18)

α 0 = 0, α 0 = 3 + ε , α k = ε , α k = ε , k = 1, . . . , N,
This manuscript is for review purposes only.

so that setting ε := ε + ε , we can take ρ = ρ call .

(ii) For a put option with strike K > 0, 1 ≤ c 0 s β k -1 for big enough c 0 > 0, over the domain of integration, so that we can as well take

(6.19) h(s, y) = 1 + N k=1 |y k |s β k -1 ≤ Π N k=1 (1 + |y k |s β k -1 ) 2 ≤ Π N k=1 s 2β k -2 (1 + |y k |) 2 and (6.20) ϕ(s, y) = h 2 (s, y)u 2 T (s) ≤ (K -s) 2 + Π N k=1 s 2β k -2 (1 + |y k |) 2 .
By lemma 4.2, in the case of a put option and since (K -s) 2 + is bounded, we can take γ k , γ k , α k , α k as before, for k = 1 to N , and (6.21)

γ 0 = 0, γ 0 = 2 N k=1 (1 -β k ), α 0 = ε + 2 N k=1 (1 -β k ) -1 + , α 0 = 0 the result follows.
Remark 6.2. If we do not use the commutator analysis, then we have a greater "h" function; we can check that our previous choice of ρ does not apply any more (so we should consider a smaller weight function, but we do not need to make it explicit).

And indeed, we have then a singularity when say y 1 is close to zero so that the previous choice of ρ makes the p integral undefined.

Application to the GMH model. For the generalized multiple factor

Heston model (GMH), i.e. when γ k = 1/2, k = 1 to N , we can take h equal to (6.22)

h H := 1 + N k=1 |y k | 1 2 (1 + s β k -1 ) + |y k | -1 2 ,
when the commutator analysis is used, and when it is not, take h equal to (6.23)

h H := h H + rs 1-β1 |y 1 | -1 2 .
Lemma 6.3. (i) For the GMH model, using the commutator analysis, in case of a call option with strike K, meaning that u T (s) = (s -K) + , we can take ρ = ρ call , with (6.24)

ρ call (s, y) := (1 + s ε +3 ) -1 Π N k=1 y ε k (1 + y ε+2 k ) -1 .
(ii) For a put option with strike K > 0, we can take ρ = ρ put , with

(6.25) ρ put (s, y) := Π N k=1 y ε k (1 + y ε+2 k ) -1 .
Proof. (i) For the call option, using (6.14) we see that we can as well take (6.26) h(s, y)

≤ 1 + N k=1 y 1/2 k + y -1/2 k ≤ (s -K) 2 + Π N k=1 (1 + y 1/2 k + y -1/2 k
).

So, we need that ϕ(s, y) ∈ L 1,ρ (Ω), with (6.27)

ϕ(s, y) = h 2 (s, y)u 2 T (s) = (s -K) 2 + Π N k=1 (1 + y 1/2 k + y -1/2 k
).

This manuscript is for review purposes only.

By lemma 4.2, where here J = {0, . . . , N }, we may take resp.

(6.28)

γ 0 = 2, γ 0 = 0, γ k = 1, γ k = 1, k = 1, . . . , N,
and so we may choose for ε > 0 and ε > 0:

(6.29)

α 0 = 0, α 0 = 3 + ε , α k = ε , α k = ε + 2, k = 1, . . . , N,
so that setting ε := ε + ε , we can take ρ = ρ call .

(ii) For a put option with strike K > 0,1 ≤ c 0 s β k -1 for big enough c 0 > 0, over the domain of integration, so that we can as well take (6.30) h(s, y)

= 1 + N k=1 |y k |s β k -1 ≤ Π N k=1 (1 + |y k |s β k -1 ) 2 ≤ Π N k=1 s 2β k -2 (1 + |y k |) 2 and (6.31) ϕ(s, y) = h 2 (s, y)u 2 T (s) ≤ (K -s) 2 + Π N k=1 s 2β k -2 (1 + |y k |) 2 .
By lemma 4.2, in the case of a put option and since (K -s) 2 + is bounded, we can take γ k , γ k , α k , α k as before, for k = 1 to N , and (6.32) γ 0 = 0, γ 0 = 0, α 0 = 0, α 0 = 0. the result follows.

Remark 6.4. If we do not use the commutator analysis, then, again, we have a greater "h" function; we can check that our previous choice of ρ does not apply any more (so we should consider a smaller weight function, but we do not need to make it explicit). And indeed, by the behaviour of the integral for large s the previous choice of ρ makes the p integral undefined.

and since u(T ) = u T we find that

(B.4)      T 0 -v(t) + A(t)u(t) -f (t), v -u(t) V ≥ 1 2 u(0) -v(0) 2 H -1 2 u(T ) -v(T ) 2 H for all v ∈ W (0, T ; K), u(T ) = u T .
It can be proved that the two formulation (B.2) and (B.4) are equivalent (they have the same set of solutions), and that they have at most one solution. The weak formulation is as follows: find u ∈ L 2 (0, T ; K) ∩ C(0, T ; H) such that (B.5)

     T 0 -v(t) + A(t)u(t) -f (t), v -u(t) V ≥ -1 2 u(T ) -v(T ) 2 H for all v ∈ L 2 (0, T ; K), u(T ) = u T .
Clearly a solution of the strong formulation (B.2) is solution of the weak one.

Proposition B.1 (Brézis [6]). The following holds:

(i) Let u T ∈ K and f ∈ L 2 (0, T ; V * ). Then the weak formulation (B.5) has a unique solution u and, for some c > 0, given v 0 ∈ K:

(B.6) u L ∞ (0,T ;H) + u L 2 (0,T ;V ) ≤ c( u T H + f L 2 (0,T ;V * ) + v 0 V ).
(ii) Let in addition the semi-symmetry hypothesis (A.8) hold, and let u T belong to K. Then u ∈ L ∞ (0, T ; V ), u ∈ L 2 (0, T ; H), and u is the unique solution of the original formulation (B.2). Furthermore, for some c > 0:

(B.7) u L ∞ (0,T ;V ) + u L 2 (0,T ;H) ≤ c( u T V + f L 2 (0,T ;H) ).

Appendix C. Monotonicity. Assume that H is an Hilbert lattice, i.e., is endowed with an order relation compatible with the vector space structure:

(C.1)

x 1 x 2 implies that γx 1 + x γx 2 + x, for all γ ≥ 0 and x ∈ H, such that the maxima and minima denoted by max(x 1 , x 2 ) and min(x 1 , x 2 ) are well defined, the operator max, min be continuous, with min(x 1 , x 2 ) = -max(-x 1 , -x 2 ).

Setting x + := max(x, 0) and x -:= -min(x, 0) we have that x = x + -x -. Assuming that the maximum of two elements of V belong to V we see that we have an induced lattice structure on V . The induced dual order over V * is as follows: for v * 1 and v * 2 in

V * , we say that v * 1 ≥ v * 2 if v * 1 -v * 2 , v V ≥ 0 whenever v ≥ 0.
Assume that we have the following extension of the integration by parts formula

(B.3): for all u, v in W (0, T ) and 0 ≤ t < t ≤ T , (C.2) 2 t t u(s), u + (s) V ds = u + (t ) 2 H -u + (t) 2 H .
and that

(C.3) A(t)u, u + V = A(t)u + , u + V . Proposition C.1. Let u i be solution of the parabolic equation (A.6) for (f, u T ) = (f i , u i T ), i = 1, 2. If f 1 ≥ f 2 and u 1 T ≥ u 2 T , then u 1 ≥ u 2 .
This manuscript is for review purposes only.

This type of result may be extended to the case of variational inequalities. If K and K are two subsets of V , we say that K dominates K if for any u ∈ K and u ∈ K , max(u, u ) ∈ K and min(u, u ) ∈ K .

Proposition C.2. Let u i be solution of the weak formulation (B.5) of the parabolic

variational inequality for (f, u T , K) = (f i , u i T , K i ), i = 1, 2. If f 1 ≥ f 2 , u 1 T ≥ u 2 T , and
K 1 dominates K 2 , then u 1 ≥ u 2 .
The monotonicity w.r.t. the convex K is due to Haugazeau [START_REF] Haugazeau | Sur des inéquations variationnelles[END_REF] (in an elliptic setting, but the result is easily extended to the parabolic one). See also Brézis [START_REF]Problèmes unilatéraux[END_REF].

Appendix D. Link with American options. An American option is the right to get a payoff Ψ(t, x) at any time t < T and u T at time T . We can motivate as follows the derivation of the associated variational inequalities. If the option can be exercized only at times t k = hk, with h = T /M and k = 0 to M (Bermudean option), then the same PDE as for the European option holds over (t k , t k+1 ), k = 0 to M -1. Denoting by ũk the solution of this PDE, we have that u(t k ) = max(Ψ, ũk ).

Assuming that A does not depend on time and that there is a flux f (t, x) of dividents, we compute the approximation u k of u(t k ) as follows. Discretizing the PDE with the implicit Euler scheme we obtain the continuation value ûk solution of

(D.1) ûk -u k+1 h + Aû k = f (t k , •), k = 0, . . . , M -1; u M = max(Ψ, 0), so that u k = u k+1 -hAû k + hf (t k , •), we find that (D.2) u k = max(û k , Ψ) = max(u k+1 -hAû k + hf (t k , •), Ψ),
which is equivalent to

(D.3) min(u k -Ψ, u k -u k+1 h + Aû k -f (t k , •)) = 0.
This suggest for the continuous time model and general operators A and r.h.s. f the following formulation (D.4) min(u(t, x)-Ψ(x), -u(t, x)+A(t, x)u(t, x)-f (t, x)) = 0, (t, x) ∈ (0, T )×Ω.

The above equation has a rigorous mathematical sense in the context of viscosity solution, see Barles [START_REF] Barles | Convergence of numerical schemes for degenerate parabolic equations arising in finance theory[END_REF]. However we rather need the variational formulation which can be derived as follows. Let v(x) satisfy v(x) ≥ Ψ(x) a.e., be smooth enough. Then

(D.5) Ω (-u(t, x) + A(t, x)u(t, x) -f (t, x))) (v(x) -u(t, x))dx = {u(t,x)=Ψ(x)} (-u(t, x) + A(t, x)u(t, x) -f (t, x))) (v(x) -u(t, x))dx + {u(t,x)>Ψ(x)} (-u(t, x) + A(t, x)u(t, x) -f (t, x))) (v(x) -u(t, x))dx.
The first integrand is nonnegative, being a product of nonnegative terms, and the second integrand is equal to 0 since by (D.3), -u(t, x) + A(t, x)u(t, x) -f (t, x)) = 0 a.e. when u(t, x) > Ψ(x). So we have that, for all v ≥ Ψ smooth enough:

(D.6) Ω (-u(t, x) + A(t, x)u(t, x) -f (t, x))) (v(x) -u(t, x))dx ≥ 0.
This manuscript is for review purposes only.

We see that this is of the same nature as a parabolic variational inequality, where K is the set of functions greater or equal to Ψ (in an appropriate Sobolev space).

Appendix E. Some one dimensional problems. It is not always easy to characterize the space V. Let us give a detailed analysis in a simple case.

E.1. The Black-Scholes setting. For the Black-Scholes model with zero interest rate (the extension to a constant nonzero interest rate is easy) and unit volatility coefficient, we have that Au = -1 2 x 2 u (x), with x ∈ (0, ∞). In the case of a put option: u T (x) = (K -x) + we may take H := L 2 (R + ). For v ∈ D(0, ∞) and u sufficiently smooth we have that -

1 2 ∞ 0 x 2 u (x)dx = a(u, v) with (E.1) a(u, v) := 1 2 ∞ 0 x 2 u (x)v (x)dx + ∞ 0 xu (x)v(x)dx.
This bilinear form a is continuous and semi coercive over the set

(E.2) V := {u ∈ H; xu (x) ∈ H}.
It is easily checked that ū(x) := x -1/3 /(1 + x) belongs to V . So, some elements of V are unbounded near zero.

We now claim that D(0, ∞) is a dense subset of V . First, it follows from a standard truncation argument and the dominated convergence theorem that V ∞ := V ∩ L ∞ (0, ∞) is a dense subset of V . Note that elements of V are continuous over (0, ∞). Given ε > 0 and u ∈ V ∞ , define

(E.3) u ε (x) :=    0 if x ∈ (0, ε), u(2ε)(x/ε -1) if x ∈ [ε, 2ε], u(2ε) if x > 2ε.
Obviously u ε ∈ V ∞ . By the dominated convergence theorem, u ε → u in H. Set for w ∈ V (E.4) Φ ε (w) := 2ε 0

x 2 w (x) 2 dx.

Since Φ ε is quadratic and v ε → u in H, we have that:

(E.5)

1 2 ∞ 0 x 2 (u ε -u ) 2 dx = 1 2 Φ ε (u ε -u) ≤ Φ ε (u ε ) + Φ ε (u).
Since u ∈ V , Φ ε (u) → 0 and

(E.6) Φ ε (u ε ) ≤ u 2 ∞ 2ε 0 ε -2 x 2 dx = O( u 2 ∞ ε).
So, the l.h.s. of (E.5) has limit 0 when ε ↓ 0. We have proved that the set V 0 of functions in V ∞ equal to zero near zero, is a dense subset of V . Now define for N > 0 (E. Again for the sake of simplicity we will take ρ(x) = 1, which is well-adapted in the case of a payoff with compact support in (0, ∞). For v ∈ D(0, ∞) and u sufficiently smooth we have that We easily deduce that the bilinear form a is continuous and semi coercive over V, when choosing (E.14)

H := {v ∈ L 2 (R + ); (x 1/2 + x -1/2 )v ∈ L 2 (R + )},
Note that then the integrals below are well defined and finite for any v ∈ V:

(E.15) ∞ 0 (x 1/2 v )(x -1/2 v) = ∞ 0 vv = 1 2 ∞ 0 (v 2 ) .
So w := v 2 is the primitive of an integrable function and therefore has a limit at zero.

Since v is continuous over (0, ∞) it follows that v has a limit at zero.

However if this limit is nonzero we get a contradiction with the condition that

x -1/2 v ∈ L 2 (R + ). So, every element of V has zero value at zero.

We now claim that D(0, ∞) is a dense subset of V. First, V ∞ := V ∩ L ∞ (0, ∞) is a dense subset of V. Note that elements of V are continuous over (0, ∞). Given ε > 0

This manuscript is for review purposes only. Since Φ ε is quadratic and u ε → u in H, we have that:

(E.17)

1 2 ∞ 0 x 2 (u ε -u ) 2 dx = 1 2 Φ ε (u ε -u) ≤ Φ ε (u ε ) + Φ ε (u).
Since u ∈ V, Φ ε (u) → 0 and

(E.18) Φ ε (u ε ) ≤ ε -2 u(2ε) 2 2ε 0 xdx = 2u(2ε) 2 → 0.
So, the l.h.s. of (E.17) has limit 0 when ε ↓ 0. We have proved that the set V 0 of functions in V ∞ equal to zero near zero, is a dense subset of V. Define ϕ N as in (E.7)

Given u ∈ V 0 , set u N := uϕ N . As before, u N → u in H, is u N = u ϕ N + uϕ N , xu ϕ N → xu in L 2 (R + ), and it remains to prove that xuϕ N → 0 in L 2 (R + ). But ϕ N is equal to 1/x over its support, so that when N ↑ ∞:

(E.19) x 1/2 uϕ N 2 L 2 (R+) = eN N x -1 u 2 (x)dx ≤ ∞ N u 2 (x)dx → 0.
The claim is proved.

  Ω}, where Ψ ∈ V . The strong and weak formulations of the parabolic variational inequality are defined in (B.2) and (B.5) resp. The abstract notion of monotonicity is discussed in appendix B. We denote by K the closure of K in V . Theorem 2.7. (i) Let the assumptions of theorem 2.6 hold, with u T ∈ K. Then the weak formulation (B.5) has a unique solution u in L 2 (0, T ; K) ∩ C(0, T ; H), and the mapping (f, u T ) → u is nondecreasing.

4 .

 4 The weight ρ. Classes of weighting functions characterized by their growth are introduced. A major result is the independence of the growth order of the function h on the choice of the weighting function ρ in the class under consideration.4.1. Classes of functions with given growth. In financial models we usually have nonnegative variables and the related functions have polynomial growth. Yet, after a logarithmic transformation, we get real variables whose related functions have exponential growth. This motivates the following definitions.

Definition 4 . 1 .

 41 Let γ and γ belong to R N +1 +

by ( 5 Remark 5 . 1 .

 551 .2) κk := κ k,N +k , k = 1, . . . , N. We use many times the following rule. For Ω ⊂ R n , where n = 1 + N , u ∈ H 1 (Ω), a, b ∈ L 0 , and vector fields Z[u] := au x1 and Z [u] := bu x2 , we have Z[Z [u]] = a(bu x2 ) x1 = ab x1 u x2 + abu x1x2 , so that

1 - 2 L 2 ( 2

 1222 log(x/N ) if x ∈ [N, eN ], 0 if x > eN .Given u ∈ V 0 , set u N := uϕ N . Then u N ∈ H and, by a dominated convergenceargument, u N → u in H. The weak derivative of u N is u N = u ϕ N + uϕ N . By aThis manuscript is for review purposes only.dominated convergence argument, xu ϕ N → xu in L 2 (R + ). It remains to prove that xuϕ N → 0 in L 2 (R + ). But ϕ N is equal to 1/x over its support, so that(E.8) xuϕ N (x)dx → 0 when N ↑ ∞.The claim is proved.E.2. The CIR setting. In the Cox-Ingersoll-Ross model[START_REF] Cox | A theory of the term structure of interest rates[END_REF] the stochastic process satisfies(E.9) ds(t) = θ(µ -s(t))dt + σ √ s dW (t), t ≥ 0We assume the coefficients θ, µ and σ to be constant and positive. The associated PDE is given by (E.10) Au := -θ(µ -x)u -1 2 xσ 2 u = 0 (x, t) ∈ R + × (0, T ), u(x, T ) = u T (x) x ∈ R + .

∞0uu

  Au(x)v(x)dx = a(u, v) with (E.11) a(u, v) := θ ∞ 0 (µ -x)u (x)v(x)dx + (x)v(x)dx.So one should take V of the form (E.12)V := {u ∈ H; √ xu (x) ∈ L 2 (R + )}.We next determine H by requiring that the bilinear form is continuous; by the Cauchy-(x)v(x)dx ≤ x 1/2 u 2 x -1/2 v 2 ; ∞ 0 xu (x)v(x)dx ≤ x 1/2 u 2 x 1/2 v 2 .

  and u ∈ V ∞ , define u ε (x) as in (E.3). Then u ε ∈ V ∞ . By the dominated convergence theorem, u ε → u in H. Set for w ∈ V (E.16) Φ ε (w) := 2ε 0 xw (x) 2 dx.

This manuscript is for review purposes only.

The first author was suported by the Laboratoire de Finance des Marchés de l'Energie, Paris, France. Both authors were supported by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program for optimization, operations research and their interactions with data sciences.

Appendix A. Regularity results by Lions and Magenes [START_REF] Lions | Non-homogeneous boundary value problems and applications[END_REF]Ch. 1].

Let H be a Hilbert space identified with its dual and scalar product denoted by (•, •). Let V be a Hilbert space, densely and continuously embedded in H, with duality product denoted by

and that for any u, v in W (0, T ), and 0 ≤ t < t ≤ T , the following integration by parts formula holds:

This manuscript is for review purposes only.

Let A(t) ∈ L ∞ (0, T ; L(V, V * )) satisfy the hypotheses of uniform continuity and semicoercivity, i.e., for some α > 0, λ ≥ 0, and c > 0: Proposition A.1 (first parabolic estimate). The parabolic equation (A.6) has a unique solution u ∈ W (0, T ), and for some c > 0 not depending on (f, u T ):

We next derive a stronger result with the hypothesis of semi-symmetry below:

is measurable with range in H, and for positive numbers α 0 , c A,1 :

Proposition A.2 (second parabolic estimate). Let (A.8) hold. Then the solution u ∈ W (0, T ) of (A.6) belongs to L ∞ (0, T ; V ), u belongs to L 2 (0, T ; H), and for some c > 0 not depending on (f, u T ):

Appendix B. Parabolic variational inequalities.

Let K ⊂ V be a non-empty, closed and convex set, K be the closure of K in H,

We consider parabolic variational inequalities as follows: find u ∈ W (0, T

H

This manuscript is for review purposes only.