Jabier Martinez
email: jabier.martinez@uni.lu

Tewfik Ziadi
email: tewfik.ziadi@lip6.fr

Raul Mazo
email: raul.mazo@univ-paris1.fr

Tegawendé F Bissyandé
email: tegawende.bissyande@uni.lu

Jacques Klein
email: jacques.klein@uni.lu

Yves Le Traon
email: yves.letraon@uni.lu

Feature Relations Graphs: A Visualisation Paradigm for Feature Constraints in Software Product Lines

Software Product Line Engineering is a mature approach enabling the derivation of product variants by assembling reusable assets. In this context, domain experts widely use Feature Models as the most accepted formalism for capturing commonality and variability in terms of features. Feature Models also describe the constraints in feature combinations. In industrial settings, domain experts often deal with Software Product Lines with high numbers of features and constraints. Furthermore, the set of features are often regrouped in different subsets that are overseen by different stakeholders in the process. Consequently, the management of the complexity of large Feature Models becomes challenging. In this paper we propose a dedicated interactive visualisation paradigm to help domain experts and stakeholders to manage the challenges in maintaining the constraints among features. We build Feature Relations Graphs (FRoGs) by mining existing product configurations. For each feature, we are able to display a FRoG which shows the impact, in terms of constraints, of the considered feature on all the other features. The objective is to help domain experts to 1) obtain a better understanding of feature constraints, 2) potentially refine the existing feature model by uncovering and formalizing missing constraints and 3) serve as a recommendation system, during the configuration of a new product, based on the tendencies found in existing configurations. The paper illustrates the visualisation paradigm with the industrial case study of Renault's Electric Parking System Software Product Line.

I. INTRODUCTION

Modern software development often leads to software product variants that share a set of commonalities and differ in a few variability points. There is thus today a momentum for Software Product Line Engineering (SPLE) [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF] as a suitable paradigm of software development for reducing both the maintenance effort and the time to market. In this context, practitioners and researchers alike, rely on Feature Models (FMs) [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF], [START_REF] Schobbens | Feature diagrams: A survey and a formal semantics[END_REF] as the main formalism for capturing commonality and variability of products in terms of features. A feature is defined as a prominent or distinctive and apparent aspect, quality, or characteristic of a system [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. A given FM describes the set of valid combinations of features, referred to as configurations, for the system. Visually, the FM is often represented in a diagram, as illustrated by Figure 1 regarding a Car FM. The hierarchy of features includes mandatory features (Gear, Car), optional features (DriveByWire, ForNorthAmerica), alternative features (Manual or Automatic), and other potential constraints such as feature implications (DriveByWire requires Automatic). Implications and mutual exclusions are referred to as hard constraints since no valid configuration can violate these constraints. However, there exists other constraints, known in the literature as soft constraints [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF], whose violations do not lead to incorrect configurations. Such constraints are used during the configuration process of a new product to provide suggestions in feature selections. In the Car example, based on domain expert knowledge, selecting the ForNorthAmerica feature could suggest the selection of Automatic gear.

Real-world SPLs yield FMs that can be large and complex with thousands of features and as many constraints. As an example, researchers have already reported the challenges of dealing with the 8000 features of the Linux kernel [START_REF] Sincero | Facing the linux 8000 feature nightmare[END_REF]. In general, FM constraints are initially formalized by the different stakeholders at the domain engineering step. However, the evolution of the SPL could require modifying or adding features and new hard and soft constraints could appear requiring a refinement of the existing FM. Such large FMs present many issues for human comprehension. Apart from that, with such numbers of features and constraints it is possible to have non formalized constraints. Non formalized constraints are those that exist implicitly but that are not explicitly defined in the FM. Consequently, non formalized constraints could be the cause of potential invalid derived products. Extracting algorithmically the constraints of the FM can be useful to formally analyse the SPL and ensure that it is consistent with actual (i.e., already instantiated) and future configurations. Mining non formalized FM constraints from existing configurations is known however to be a challenging endeavour in the community of SPLE. A large body of literature is dedicated Fig. 1: Example of Car Feature Model. Credits to Czarnecki et al. [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF] to this issue. Most approaches [START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF], [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF], [START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF], [START_REF] Lora-Michiels | A method based on association rules to construct product line models[END_REF], [START_REF] She | Reverse engineering feature models[END_REF], [START_REF] Yoshimura | A method to identify feature constraints based on feature selections mining[END_REF] target hard constraints, while others also propose algorithms to extract soft constraints [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF]. Once constraints are mined, they must be confirmed by the different stakeholders. Unfortunately, from the domain expert perspective, enumerating and displaying hundreds of constraints will inevitably lead to a tedious investigation analysis. A promising alternative would be to provide a visualisation paradigm that is more intuitive than a textual listing, and also provides free exploration.

Visualization and interactive techniques are widely accepted to reduce the complexity of comprehension tasks [START_REF]Readings in Information Visualization: Using Vision to Think[END_REF]. We contribute in this paper with a new visualization paradigm for feature constraints, i.e., relations. We present our approach for building Feature Relations Graphs (FRoGs), and we present experimental results in an industrial case study.

A FRoG representation targets different stakeholders (e.g., domain experts, product developers, and users) and different usage scenarios (design analysis, documentation, and recommendation).

The main contributions of this paper are:

• We propose a new visualization paradigm to intuitively represent the relations among features in an SPL. • We propose an approach for mining constraints from existing configurations to feed our visualization tool. • We demonstrate the usability of our tool in different usage scenarios, based on a real-world dataset from a major manufacturer. The remainder of this paper is structured as follows: Section II presents the background of managing constraints in SPLE to motivate our work. Section III formalizes the data abstractions and describes our proposed visualization paradigm. Section IV presents the case study. In Section V we discuss related work and Section VI concludes and presents future work.

II. BACKGROUND AND MOTIVATIONS

In practice, as discussed in the literature [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF], [START_REF] Schobbens | Feature diagrams: A survey and a formal semantics[END_REF], a FM may contain hard constraints that express strong dependencies between features. Following the Car example, we cannot have the DriveByWire feature without the Automatic gear feature. The explicit formalization of such constraints assures the assembling of valid feature combinations that will violate neither structural nor semantic dependencies of the product variant that has to be created. Therefore a given FM describes the set of valid combinations of features. Each combination, referred to as configuration corresponds to a specific product. Table I shows all the possible valid configurations of the Car example. Although Gear and Car, as shown in Figure 1, are also features of the Car example FM, they are not in Table I because they are mandatory features that do not represent variation points for the SPL.

FMs could be expressed as propositional formulas as presented in [START_REF] Batory | Feature models, grammars, and propositional formulas[END_REF], [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. The "inclusion" implication constraints are expressed with the requires statement and "exclusion" constructions are expressed with the excludes statement:

• requires: Example: A ⇒ B. Feature A requires the presence of feature B. • excludes: Example: A ⇒ ¬B. Feature A excludes the presence of feature B. In the illustrative FM of Figure 1, a mutual exclusion (Automatic ⇒ ¬M anual, M anual ⇒ ¬Automatic) is formalized through the Alternative construction. However, a domain expert can also add hard constraints explicitly between any features in the FM hierarchy as for example DriveByW ire ⇒ Automatic. Notice also that, because of logic inference rules, we can have hard constraints that are not explicitly formalized but that exist because of the other formalized constraints. This relation type between features is called inferred constraint. For example DriveByW ire ⇒ ¬M anual is an inferred constraint.

The presence of two features in a given product configuration can also be qualified in terms of suitability. Such relations between features have also been explored in the literature. Bühne et al. [START_REF] Bühne | Modeling dependencies between variation points in use case diagrams[END_REF] refer to them as hints and hinders relations. In the Pure::Variants commercial tool [START_REF] Beuche | Modeling and building software product lines with pure::variants[END_REF], the terms encourage and discourage are used in reference to the constraints in such relations. Czarnecki et al. [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF] formally refer to them as two particular types of soft constraints, in the sense that their violation does not give raise to incorrect configurations. They exist with the objective of alerting the user, providing suggestions during the configuration process [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF] or as a way to capture domain knowledge related to these trends. We will use the notation below for soft constraints:

• encourages: Example: sof t(A ⇒ B). Feature A encourages the presence of feature B. • discourages: Example: sof t(A ⇒ ¬B). Feature A discourages the presence of feature B. This way, a domain expert of the Car example could explicitly formalize the soft constraint sof t(F orN orthAmerica ⇒ Automatic) mentioned before to capture this SPL domain knowledge.

In addition to features, constraints and configurations, the FM has the particularity to be addressed by different stakeholders at the same time. Indeed, and as mentioned by Yu et al. [START_REF] Yu | Configuring features with stakeholder goals[END_REF], variability in FMs arises from different stakeholders goals. Each stakeholder can thus be interested in a partial view of the variability included in a FM. In other words, each stakeholder has its own stakeholder perspective. For instance, features concerning the type of Gear in the Car example is mainly useful for final customers to choose their cars. However, DriveByWire is more the concern of engineers during the construction of the cars, while the ForNorthAmerica feature can be related to commercials and sales analysts. Each stakeholder perspective cannot ignore the impact of other features from other stakeholders perspectives. Consequently, fluent communication means should exist to reason about these feature relations that involves different stakeholders, called inter-stakeholder perspectives constraints hereafter.

As reported by [START_REF] Nestor | Applying visualisation techniques in software product lines[END_REF], "the use of visualisation techniques in Software Product Line can radically help stakeholders in supporting essential work tasks and in enhancing their understanding of large and complex product lines". In this paper, we face the visualisation of feature constraints using an innovative visualisation paradigm for the SPL community called FRoGs. FRoGs has three objectives:

1) Domain experts can rely on a FRoG for a better understanding of relations among features. Potentially, it could help refining an existing FM by formalizing hard and soft constraints. 2) A FRoG can also be used to document, at the domain level, each feature. Thus, stakeholders can visualize, in an interactive way, the relations among the features he/she is responsible for and others. 3) Finally, the representations of FRoGs can be used to improve recommendation systems during product configuration. Indeed a FRoG can better visually "explain" why two features should be selected together in comparison with another pair of features.

III. FROM CONFIGURATIONS TO FROGS

Before presenting the visualisation decisions, in subsection A we present the data abstractions used to build the FRoG visualisation. Then, in subsection B we present how this data is displayed to fulfil the FRoGs objectives and the existing interaction functionalities.

A. SPL data abstraction for FRoGs

A configuration is defined as a set of selected features

c i = {f 1 , f 2 , .., f n }. Let V C = {c 1 , c 2 , .
., c m } be the set of all the possible valid configurations for a given FM. The number of valid configurations could be up to 2 n so there is a combinatorial explosion of valid feature combinations. SPLs normally have a subset of configurations from where the actual product variants are derived. Let EC ⊆ V C be the set of existing configurations for an SPL. Our approach has the assumption that ECs are valid. Also, if duplicated configurations exist, our approach does not take them into account. Indeed, one configuration represents one product variant independently of the amount of units of the product variant that were derived. In the Car example, Table I presents the V C set. Let us consider that EC contains all V C excluding the last configuration Conf6. In this case EC is expressed as:

Given this definition of EC, we can reason on the feature relations in this set. Let EC f i = {c ∈ EC : f i ∈ c} be the subset of existing configurations that contain the feature f i . For example, the set of existing configurations that have the Manual feature is defined as EC f1 = {c 2 , c 4 }. With this definition of EC f i , we can calculate the proportion of the apparition of a feature given the apparition of another feature. Following existing notation [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF] we will call this operation f i givenf j . Equation 1 presents how this proportion is calculated. The formula is similar to the conditional probability formula but we use the term proportion instead of probability since probability is a hypothetical property while proportions summarize observations as it is the case when mining existing configurations.

f i givenf j = |EC f i EC f j | |EC f j | (1)
In the Car example, the proportion of Automatic given DriveByWire (f 2 givenf 3 ) is 1 as when we have DriveByWire in the EC, we always have Automatic. In the same way, Manual given Automatic (f 1 givenf 2 ) is 0 as when we have Automatic we never have Manual. With the same formula, the proportion of Automatic given ForNorthAmerica (f 2 givenf 4 ) is 0.67. These proportions, that are continuous values from 0 to 1, are mapped to the different potential hard and soft constraints in the following way:

requires (f i ⇒ f j ) when f j givenf i = 1 excludes (f i ⇒ ¬f j ) when f j givenf i = 0 encourages (sof t(f i ⇒ f j )) when enc threshold <= f j givenf i < 1 discourages (sof t(f i ⇒ ¬f j )) when 0 < f j givenf i <= dis threshold
The thresholds enc threshold and dis threshold are defined and adjusted by domain experts based on their experience. These thresholds are also discussed and set by domain experts in the case reported at [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF].

Regarding the stakeholder perspectives, each of them consists in the subset of features that are "owned" by a stakeholder. These subsets must be disjoint in the current version.

Finally, we define a confidence metric of the validity of the mined hard or soft constraints. The confidence metric is only applicable for relations that are not explicitly formalized in the FM. We consider that the ones already formalized are correct until modified or removed. In the case of non formalized hard constraints, the confidence metric, represents the probability of finding one configuration that violates this hard constraint.

If we have a constraint, for example f i ⇒ f j , the confidence of f j givenf i is calculated as the percentage of the possible valid configurations containing f i that exists in EC. Let V C f i = {c ∈ V C : f i ∈ c} be the subset of the valid configurations that contains the feature f i . Equation 2shows how the confidence metric, that only depends on f i , is calculated. The confidence will be increased when new configurations containing f i are created reaching 1 when

EC fi = V C fi . Conf idence(f i ) = |EC f i | |V C f i | (2)
In practice, the creation of the set V C f i is not needed to compute its cardinality. Calculating the number of valid configurations is a well known problem solved by existing FM automated analysis approaches [START_REF] Benavides | Automated reasoning on feature models[END_REF] where the idea is to calculate the cardinality of |V C f i | reasoning on the formalized constraints.

B. FRoGs: Feature Relations Graphs

Our visualisation paradigm, called FRoGs, has as objective to visualise the constraints (relations) between features based on the analysis of current configurations. Each FRoG is associated with a specific feature to show how this feature is related, in term of hard and soft constraints, to the other features. A FRoG is presented as a circle where the considered feature is displayed in the center 1 . This feature in the center will be called f c hereafter . All the rest of features that represent variation points of the FM are displayed around f c with a constant separation of 2π |f eatures|-1 . This separation allows to distribute uniformly all the features around the circle. These features are ordered by stakeholder perspectives so we will have circular sectors for each of the stakeholder perspectives.

Before going into the details of the visualisation, Figure 2 shows the FRoG of the Manual feature of the Car example. We can see Manual as f c in the center and the rest of the features separated with a constant angle. We can see also the sectors of the different stakeholders mentioned in the introduction. 1 FRoGs acronym is inspired by the metaphor that FRoG graphs have water lily pond plant shapes and that the domain expert could navigate from one to another Fig. 2: FRoG for the Manual feature of the Car example 1) FRoG's zones: Each FRoG displays five zones each of them associated with a specific color and related to a specific type of constraints. Figure 3 shows these zones and how the distance between the f c and the boundary of the circle is calculated according to the f i givenf c operation.

• Requires Zone. The Requires zone is reserved to the value 1 and it is the closest to f c . Features in the Requires zone are "glued" to f c meaning that if we have f c then in all EC we have f i . The Requires Zone and the Excludes zone are reserved to only one value and their size fits exactly with the diameter of the f i nodes. The Requires zone is displayed with the green color. • Excludes Zone. This zone, displayed with the red color, is in the extreme of the circle and therefore is the farthest from the f c to illustrate that f c and f i were not together in any configuration. • Encourages Zone. This zone includes all f i that are potentially encouraged by the presence of f c . The color is a pale green meaning that it is close to the Requires zone but without reaching it. The Encourages zone fades to white in the Independent Zone at the distance defined by the enc threshold . • Discourages Zone. This zone includes all f i that are potentially discouraged by the presence of f c . The color is orange meaning that it is close to the Exclude zone but without reaching it. The Discourage zone fades to white in the Independent Zone at the distance defined by the dis threshold . • Independent Zone. This zone, located between the enc threshold and the dis threshold , is displayed with the white color containing the features that are not impacted by the presence of f c . In the FRoG of Figure 2 we can see how both Automatic and DriveByWire are in the Excludes zone and ForNorthAmerica (with a f i givenf c of 0.5) is located exactly in the middle between the Requires and Excludes zones corresponding to the Independent zone.

The usage of colors in visualisation is an important design decision [START_REF] Silva | Using color in visualization: A survey[END_REF]. FRoG zones depends to univariate data (f i givenf c ). This data has continuous values but, as we have shown, these values are mapped to zones in a discrete fashion. Therefore, we have defined boundaries and we associate one color to each of the zones following the color scheme shown in Figure 3.

The green of the Requires zone contrasts heavily with the red of the Excludes zone. The separation principle, that claims Fig. 3: FRoG's zones that close values must be represented by colors perceived to be closer, is respected with the green and the pale green for the Requires and Encourages zones as well as with the red and the orange colors for the Excludes and Discourage zones. The color scheme used in FRoG's zones can be seen as a diverging color scheme given that it illustrates the progression from a central point.

Colder colors are perceived to be lower than warmer colors as in the case of heat maps. This is respected in FRoGs taking into account that the distance from f c to the Requires zone is lower than the higher distance to the Excludes zone. In addition, as it happens with the traffic lights metaphor shared by most of the cultural contexts, the red color for the Excludes zone has a connotation of interdiction while the green of the Requires zone has a connotation of being positive.

The size of the Requires and Excludes zones fits exactly with the size of a f i node while the other zone sizes depend on the percentage defined in the enc threshold and dis threshold . The fade from the Encourages and Discourages zones is very small in size and it is aimed only to create a visual effect that these boundaries are not as restrictive as the hard constraints boundaries represented with a black line. For example, a feature f i with a formalized excludes hard constraint cannot appear in the discourages zone because otherwise it was not a hard constraint. On the contrary, one feature f i that has not a hard constraint could "move" between the Encourages, Independent and Discourages zone over time because of the addition of new configurations.

2) Formalized and non formalized constraints: A FRoG displays the mined constraints by analysing the EC. However, some of them (or all in an optimistic case) are normally already defined in the FM. In the FRoG visualisation, for these already formalized constraints we add a circle in the node of f i with the color of the corresponding constraint's type as shown in Figure 4. For example, M anual ⇒ ¬Automatic is an already formalized constraint and Figure 2 shows this notation on the Automatic node with the red color as it is an Excludes constraint.

Notice that, if we have formalized soft constraints, it could happen that the mining process on EC may situate f i in a FRoG zone that does not correspond to the defined soft constraint. This could alert the user about a general violation of the formalized soft constraint.

Figure 2 shows the FRoG legend at the right side of the image. In this legend, the "Relation types" category shows the notation for other types of feature relations apart from the Formalized relation. We use the grey color in the figures but Formalized Requires constraint Formalized Excludes constraint Formalized Encourages constraint Formalized Discourages constraint Fig. 4: Formalized constraints notation it will be the color of the different constraints and, in any case, grey color. An inferred constraint, as explained before, is a constraint that is not formalized in the FM but that exists because of logical rules. Figure 2 shows an example of it in the DriveByWire node. We use the triangle to differentiate it from the circle of the formalized constraints. The triangle metaphor contrasts with the circle and it has the connotation of an arrowhead representing the existence of a rule of inference. If it is neither a formalized nor inferred constraint, we will refer to it as an undefined relation independently of the zone where the f i is placed. Undefined relations do not contain any symbol inside the f i node.

3) Stakeholder Perspectives: Each stakeholder perspective has an associated color that is used in the circular sectors of the FRoG. The f c node has the color of the stakeholder perspective it belongs to, and also, this circular sector has a slightly bigger radius. Figure 2 shows how the Manual feature has the Customer color and that the Customer sector has bigger radius.

The stakeholder perspectives colors could be changed by users but default colors are provided. Stakeholder perspectives are nominal data and we used a qualitative color scale that does not imply order. Figure 5 shows the used color scheme. In the rejected alternatives section III-E2, it is discussed why only grey, purple and blue variations are present in this default color scheme. Fig. 5: Default color scheme for the nominal data of stakeholder perspectives 4) Displaying the Confidence: The confidence is displayed outside of the circle as a percentage accompanied by a pie chart visualizing this percentage. In Figure 2 we can see in the bottom-right side a Confidence of 100% and complete black circle. As another example Figure 6 shows the visualisation of the confidence with a value of 5%.

C. Interaction possibilities

FRoGs was implemented as a visualisation tool allowing free exploration. The navigation and filter capabilities are discussed in the next paragraphs. To illustrate these interaction possibilities, Figure 6 shows a screen-shot of FRoGs visualisation tool at which we added dashed sections to differentiate the different parts. The "Name of the FM" part just shows the name of the FM of the SPL while the "Feature List" part contains all the variable features of this FM. The "FRoG" part shows the FRoG of the selected feature with the "Confidence" and "Legend" sub parts. Finally, the "Actions" part activates different interaction capabilities.

1) Navigation: On the left side of Figure 6 we can see the "Feature List" part. A bold font and an arrow is used to distinguish the selected feature. We can click in any feature or use the keyboard to change the displayed FRoG. We can also click in any node of the graph to navigate to the FRoG of the selected feature. 2) Filters: Filters can be applied simultaneously to hide feature nodes of stakeholder perspectives, relation types or FRoG zones. FRoG users should click on the "Show Options" button of the "Actions" part to have access to these functionalities. By clicking this button, checkboxes will appear on the FRoG legend to activate or deactivate the filters as shown in Figure 7. The button "Show Options" text changes to "Hide Options" to hide these functionalities and come back to the purely visualisation operations.

Different filter combinations could fulfil different objectives of FRoGs usage as for example:

• Documenting constraints: We focus on constraints by hiding all features on the Independent zone. • Discovery of non formalized constraints: We focus on potential constraints by hiding all features on the Independent zone and those constraints that are already formalized or inferred. • Intra-stakeholder perspectives constraints: We hide all the features that do not correspond to a given stakeholder perspective.

• Inter-stakeholder perspectives constraints: We hide all the features that do not correspond to a given set of stakeholder perspectives. 3) Adjusting encourages and discourages thresholds: By clicking in the "Show Options", apart from the filtering checkboxes, the legend of the zones is transformed in a range slider. Figure 6 shows the initial appearance of the legend of the zones at the bottom of the "Frog Legend" part, and Figure 7 shows the legend of the zones enriched with the Fig. 7: Filtering options and slider for adjusting encourages and discourages thresholds slider functionality and with a textual representation of the selected percentages. Using this slider, the enc threshold and dis threshold could be adjusted at will. Interacting with the slider provides automatic feedback in the FRoG by changing the size of the zone. If filters are applied to the feature nodes, these filters have also effect so hidden nodes could appear or disappear while interacting with the slider.

4) Save as image: Another interaction capability of the visualisation tool is a button to save the current FRoG (filtered or not filtered) and the legend to an image file. This functionality is available in the "Actions" part of Figure 6. The "Name of the FM", "Actions" and "Feature List" parts are not appearing in the saved image and therefore it can be used directly for documentation or to illustrate some phenomena in feature relations.

D. Time response

FRoGs was implemented with Processing 2.0 [START_REF] Colubri | Introducing processing 2.0[END_REF] and we achieve complete visual continuity. f i givenf j is an algorithm with order O(m) where m is the number of existing configurations. Therefore, displaying a FRoG is O(nm) being n the number of features. The number of possible valid configurations is precomputed before starting the visualisation. The needed set of input files for FRoG are exported using the SPL tool Feature IDE [START_REF] Thüm | FeatureIDE: An extensible framework for feature-oriented software development[END_REF] and the mapping from stakeholder perspectives to features are defined in another configuration file.

E. Rejected alternatives 1) Colors of Requires and Excludes zones:

In the beginning we used pale green and pale red for the Requires and Excludes zones but users reported that they will prefer more intense green and red colors for these zones to catch more attention on hard constraints.

2) Default colors for stakeholder perspectives: Qualitative scales for nominal data are publicly available as for example the color scheme provided by ColorBrewer 2.0 [START_REF] Colorbrewer | Colorbrewer2, color advice for cartography[END_REF] shown in Figure 8. We started using this color scheme but users complained about the similarities between some of the colors of the stakeholder perspectives' sectors and the red of the Excludes zone. For instance, the fourth color of Figure 8 was a cause of confusion. We decided to exclude those colors that were similar to red, orange as well as similar to green and pale green. 3) Relation types: The current version of FRoGs only has the possibility to see the impact of the presence of f c in the presence of the other features f i . In order to display other phenomena in the relations of a given feature f c , FRoGs implementation was flexible to show the impact of the presence or absence of f c in the presence or absence of other features f i . It was also available to show the impact of the presence or absence of the rest of the features f i in relation with f c . These aspects give raise to eight possible FRoGs for a given f c from which Figure 9 shows four of them that could be obtained from a given f c . The other four combinations could also be displayed even if they are the "inverse" of one of these four types because of the following property of the f i givenf j operation: f i givenf c = 1-(¬f i )givenf c . Notice that the direction of the arrows from f c to f i changes in types one and two, and three and four. To obtain the distances in the cases that we want to show the impact of other features on f c , it is enough to inverse the f i givenf j operation: For type one is f i givenf c while for type two is f c givenf i .

This functionality in the options of the visualisation tool gave raise to many confusion in the users. It is not easy to think about presence and absence of features in combination with the direction of the arrows. Our case study did not need these kinds of relation visualisation for documentation nor for constraint discovery so we decided to remove it for easing FRoGs usage until we prove its usefulness in some scenario. Current version of FRoGs visualisation corresponds to the first type of Figure 9 as shown for example in Figure 2.

IV. CASE STUDY AND DISCUSSIONS

In the previous sections we illustrated FRoGs on the Car example. In this section we present FRoGs evaluation on an industrial case study in the automotive industry concerning the Renault's Electric Parking Brake (EPB) SPL [START_REF] Dumitrescu | Bridging the gap between product lines and systems engineering: An experience in variability management for automotive model based systems engineering[END_REF], [START_REF] Mazo | Recommendation heuristics for improving product line configuration processes[END_REF]. First we describe the case study and then we discuss the results.

A. Case Study: Electric Parking Brake

The EPB system is a variation of the classical, purely mechanical, parking brake, which ensures vehicle immobilization when the driver brings the vehicle to a full stop and leaves the vehicle. The case study is focused on the variability in the BOM (Bill of Materials) related to the logical/physical components of the EPB. Figure 10 presents the FM specified by domain experts. This FM contains 20 variable features and 32 hard constraints. In concrete, the Alternative constructions between features define 24 hard constraints and 8 are expressed as logical expressions. The possible valid configurations of this FM are 2976 while the existing configurations that were provided are 200.

The variability in this SPL is described by Renault according to six stakeholder perspectives that represent different subdomains of the EPB's variability. These stakeholder perspectives are Customer, Environment, Functions, Design, Behavior and Components. We present here a brief description of these perspectives and their associated features. a) Customer: Customer visible variability is handled by the product division. For customers, the parking brake proposes three types of services: The manual brake is controlled by the driver either through the classical lever or a switch; the automatic brake is a system that may enable or disable the brake itself depending on an automatic analysis of the situation; the assisted brake comes with extra functions which aid the driver in other situations such as assistance when starting the car on a slope. The features concerned by this perspective are thus PBSManual, PBSAutomatic and PBSAssisted. f) Components: The variability in the EPB also concerns the physical architecture/components. This consists in the presence of different means of applying the brake force: electric actuators mounted on the calipers or single DC motor and puller cable much like the traditional mechanical parking brake. Also the type of sensors available may vary depending on the configuration and needs. This perspective thus includes the following features: DCMotor, PairEActuator, TiltSensor, EffortSensor, ClutchPosition, DoorPosition, and VSpeed.

B. Results: FRoGs of the Case Study

From the 200 existing configurations of the EPB case study we obtained 20 FRoGs, one per feature. Figure 6 shows these features in the "Feature List" part. Table II shows the information that can be visualised on the FRoG of each feature. For each FRoG's central feature, the table shows the number of constraints that can be identified by analysing the different zones. Regarding the soft constraints, the values used for enc thershold and dis thershold are 25% and 75% respectively. Figure 6 shows the PBSManual FRoG, that corresponds to the second element in Table II, where we can see that it displays 2 hard constraints, 1 inferred, and 4 potential soft constraints.

Before experimenting with domain experts, we manually checked the correctness of the visualised information. Concretely, we checked manually that the formalized hard and inferred constraints of the FM appear in the displayed FRoGs. We discuss now some analysis that domain experts made using FRoGs and how it helps in the comprehension of feature relations in the EPB SPL. For instance, analysing the FRoG associated with the EffortSensor feature (see Figure 11), it is observed that it has no hard constraints to any other features. That means that it has no hard impact on the presence or absence of any feature. However, the feature PullerCable (see Figure 12) has a great impact on other features as the PullerCable FRoG shows seven features on the Excludes and Requires zones.

No undefined hard constraints were found neither in the Excludes nor Requires zones in EPB's FRoGs. However, thanks to FRoGs, as shown in Table II, 55 potential soft constraints are displayed. By visualising this, domain experts are able to think about two possibilities: a) whether it is an actual soft constraint that should be formalized or b) FRoG displayed a fact based on the existing configurations but it is not an actual soft constraint. The exercise also enables to think about the thresholds for the Encourages and Discourages zones.

The FRoGs for the EPB's FM also represented a visualisation paradigm to understand the relations between stakeholder perspectives. From the 47 hard or inferred constraints, 20 of them are hard constraints that relate features belonging to Fig. 11: FRoG of EffortSensor feature without filters showing that it does not representatively affect other features Fig. 12: FRoG of PullerCable feature with a filter hiding Independent zone features to illustrate great impact on other features different stakeholder perspectives. Figure 12 shows 4 interstakeholder perspectives hard constraints: TemporaryMonitor, PermanentMonitor, DCMotor and PairEActuator. In addition, in the case of soft constraints, the 55 soft constraints are between inter-stakeholder perspectives. Figure 11 shows 4 of them: PullerCable, ElectricActuator, PermanentMonitor and PBSAutomatic.

V. RELATED WORK

As presented above, the FM is classically visualised as a tree structure consisting of features. Constraints between these features are displayed using the Alternative and the Or variability notation. Constraints (e.g.; requires, excludes) can also be explicitly formalized textually (Figure 10) as logical expressions or graphically (Figure 1) as arrows between features [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF], [START_REF] Schobbens | Feature diagrams: A survey and a formal semantics[END_REF]. As discussed in this paper, real-world SPLs yield FMs that can be large and complex with many constraints. Hence, it is difficult to use this representation to help domain experts to understand relations between features. In recent years, the use of visualisation techniques in the SPL community has received a lot of attention proposing new alternatives to visualise FMs. Trinidad et al. [START_REF] Trinidad | Threedimensional feature diagrams visualization[END_REF] proposed the cone tree visualisation paradigm introducing a 3D representation of FMs. However, this visualisation is only proposed to represent the hierarchical information included in large FM and the authors do not consider constraint visualisation.

SPL visualisation related work mainly consider the use of visualisation techniques to help domain experts for product configuration. Product configuration is the process that consists in selecting, from the FM, the list of features that will be included in the target configuration. Visualisation is often combined with interactive techniques to support product configuration. A survey on the use of visualisation techniques for product configuration is presented in [START_REF] Pleuss | Visualization techniques for application in interactive product configuration[END_REF]. Nestor et al. [START_REF] Nestor | Applying visualisation techniques in software product lines[END_REF] propose a tool called VISIT-FC (Visual and Interactive Tool for Feature Configuration) that introduces visualisation techniques to address product configuration. For constraint visualisation, this tool only uses arcs between features. Constraints are also visualised as arcs in the S2T2 visualisation tool [START_REF] Pleuss | Visualization of variability and configuration options[END_REF].

[4] also discuss product configuration but without considering constraint visualisation. In [START_REF] Lopez-Herrejon | Towards interactive visualization support for pairwise testing software product lines[END_REF], the authors propose the use of visualisation techniques to display features for pairwise testing but constraints are not visualised. On the contrary, we propose FRoGS as a new formalism to visualise constraints between features. Instead of classical representations where constraints are integrated in FMs and often visualised as arcs between features, FRoGs display the constraints focusing on relations of each feature with the rest of the features. This allows to study the impact of each feature on the rest of the FM. At our best knowledge FRoGs represent the first work in this direction.

In Section III, we presented our approach to extract constraints and build FRoGs from existing configurations. Extracting constraints from sets of configuration has received a lot of attentions in the context of reverse engineering of feature models [START_REF] Fenske | A taxonomy of software product line reengineering[END_REF]. Many papers [START_REF] Czarnecki | Sample spaces and feature models: There and back again[END_REF], [START_REF] Davril | Feature model extraction from large collections of informal product descriptions[END_REF], [START_REF] Haslinger | On extracting feature models from sets of valid feature combinations[END_REF], [START_REF] Lopez-Herrejon | Reverse engineering feature models with evolutionary algorithms: An exploratory study[END_REF], [START_REF] Lora-Michiels | A method based on association rules to construct product line models[END_REF], [START_REF] She | Reverse engineering feature models[END_REF], [START_REF] Yoshimura | A method to identify feature constraints based on feature selections mining[END_REF] in this context propose algorithms to extract constraints from existing configurations. However, all these algorithms only extract constraints without proposing any visualisation mechanisms. Our main objective by introducing FRoGs is not to propose a new extraction algorithm but to contribute a formalism to visualise the mined constraints. Thus, FRoGs can be used as a front-end to visualise constraints using any algorithm.

FRoGs visualisation can be categorized as a radial ego network representation. The ego represents the focal node of the graph. This approach has been used mainly in social network analysis. In software engineering, ego networks has been proposed to visualise how the modification of a given component could demand the evolution of the other components [START_REF] D'ambros | The evolution radar: Visualizing integrated logical coupling information[END_REF] based on the version control system information. FRoGs use ego network representations but it is designed to deal with the specificities of feature relations in SPLE.

VI. CONCLUSION & FUTURE WORK

Feature constraints are the core of Feature Models and identifying and maintaining them is challenging in Software Product Line engineering. This paper proposes a new paradigm called FRoGs to help domain experts to visualise in an interactive way the feature relations mined from existing configurations. This can help to potentially refine an existing feature model by formalizing new hard and soft constraints. In addition, FRoGs can be used to document, at the domain level, each feature by displaying its relations among the rest of features. We demonstrate in this paper the usability of FRoGs on a real-world case study from a major manufacturer.

Our future work has two main directions: 1) Regarding to visualisation, FRoGs can be improved to consider the time dimension. Indeed, the time dimension in the creation of each existing configuration could help users to understand the dynamicity on feature relations and reason about feature obsolescence or usage over time. 2) Independently from the visualisation aspect, we aim to improve the way that FRoGs are built by providing heuristics for default values for the encourage and discourages thresholds.

Fig. 6 :

 6 Fig. 6: Screenshot of FRoGs visualisation tool focusing on the PBSAutomatic feature of the Electric Parking Brake SPL

Fig. 8 :

 8 Fig. 8: Rejected default color scheme for the nominal data of stakeholder perspectives

  How the presence of fc affects the presence of others How the presence of others affects the presence of fc How the absence of fc affects the presence of others How the absence of others affects the presence of fc

Fig. 9 :

 9 Fig. 9: Different relations regarding presence or absence of features, and the direction of the relation regarding the FRoG central feature

Fig. 10 :

 10 Fig. 10: Electric Parking Brake system Feature Model for physical and logical components

TABLE I :

 I Valid Configurations for the Car example.

	Manual	Automatic	DriveByWire	ForNorthAmerica
	f 1	f 2	f 3	f 4
	Conf 1
	Conf 2
	Conf 3
	Conf 4
	Conf 5
	Conf 6

TABLE II :

 II Number of the identified constraints using FRoGs

	FRoG central feature	Hard	Inferred	Soft
	PBSManual	2	0	2
	PBSAutomatic	2	1	4
	PBSAssistance	2	1	3
	ClutchPedal	1	1	4
	GBAutomatic	2	0	4
	GBManual	1	0	4
	AuxiliaryBrakeRelease	0	0	4
	PullerCable	5	2	0
	ElectricActuator	5	2	0
	Calipser	4	1	0
	Traditional	4	2	0
	TemporaryMonitor	1	2	2
	PermanentMonitor	1	1	1
	DCMotor	1	1	3
	PairEActuator	1	1	3
	TiltSensor	0	0	5
	EffortSensor	0	0	4
	ClutchPosition	0	0	4
	DoorPosition	0	0	4
	VSpeed	0	0	4
	Total	32	15	55
	Average	1.6	0.75	2.75
	Standard Deviation	1.67	0.79	1.68

EC = { c 1 = { f 2 , f 4 }, c 2 = { f 1 , }, c 3 = { f 2 , }, c 4 = { f 1 , f 4 }, c 5 = { f 2 , f 3 , f 4 }}

AKNOWLEDGMENTS

We would like to thank the Renault company for providing the information for the case study and participating in the improvement of the visualisation. The present work is supported by the Fonds National de la Recherche (FNR), Luxembourg, under the project MODEL C12/IS/3977071 and the AFR grant agreement 7898764. The work of Tewfik Ziadi was also supported by the University of Luxembourg as a visiting researcher.


Ping Yin

Jacques Liandrat
email: jliandrat@centrale-marseille.fr

Coupling wavelets/vaguelets and smooth fictitious domain methods for elliptic problems; the univariate case

Keywords: smooth fictitious domain method, multiscale approximation, error estimate, elliptic problem

Coupling wavelets/vaguelets and smooth fictitious domain methods for elliptic problems: the univariate case

Ping Yin,

Introduction

This paper is devoted to the numerical approximation of partial differential equations solutions posed on a non trivial domain. The general situation and notations, ǔ for the solution, ω for the domain and γ for its boundary are shown in figures 1 and 2. It is well known that for variational formulations, the main difficulty lies in the construction of functional bases living on the domain ω. For a time-dependent domain the difficulty reappears at each time step.

To circumvent this difficulty, fictitious domain methods ( [START_REF] Haslinger | Fictitious domain methods with distributed Lagrange multipliers. part i: application to the solution of elliptic state problems[END_REF], [START_REF] Angot | A penalization method to take into account obstacles in incompressible viscous flows[END_REF] among many other references) have been introduced, leading to the definition of a new problem posed on a larger but simpler domain Ω ⊃ ω, called the fictitious domain, such that its solution u restricted to ω matches with the solution ǔ eventually when some so-called penalization parameter goes to zero . We summarize in the following the main difficulties encountered when one implements a variational approximation of fictitious domain methods:

1. Since the initial equation defined on ω is used to derive the new problem on the larger domain Ω, its coefficients have to be extended. The choice of the extension is important since the regularity and eventually the support of the extended coefficients play a key role in the properties of the new equation and the numerical method used to approximate its solution. [START_REF] Angot | A penalization method to take into account obstacles in incompressible viscous flows[END_REF]. In what will be called classical fictitious domain methods, the initial boundary condition is enforced on γ. This enforcing induces a lack of regularity of the solution in the vicinity of the domain where it is applied that weakens the convergence speed of the method [START_REF] Haslinger | Projected Schur complement method for solving non-symmetric systems arising from a smooth fictitious domain approach[END_REF]. 3. Due to the presence of discontinuous coefficients or to the involvement of trace operators, ill conditioning is a standard property of numerical systems involved in fictitious domain methods. 4. So called inf/sup conditions [START_REF] Evans | A note on the existence of a solution to a problem of Stefan[END_REF] are usually associated to the weak formulations of fictitious domain methods that constrain the spaces of approximation involved in the implementation.

In this paper, we propose some answers to the above difficulties using two ingredients, the smooth fictitious domain method introduced in [START_REF] Haslinger | Projected Schur complement method for solving non-symmetric systems arising from a smooth fictitious domain approach[END_REF] and a multiscale approximation of wavelet type [START_REF] Daubechies | Ten lectures on wavelets[END_REF]. On one hand, we will show that the smooth fictitious domain method shifts the lack of regularity of the solution from the initial boundary to a new control boundary allowing an optimal convergence rate on the initial domain. On the other hand, we will show that the multiscale approach provides suitable answers to various open questions such as the extension procedure [START_REF] Haslinger | Fictitious domain methods with distributed Lagrange multipliers. part i: application to the solution of elliptic state problems[END_REF], the ill conditioning [START_REF] Haslinger | Projected Schur complement method for solving non-symmetric systems arising from a smooth fictitious domain approach[END_REF] and the local refinement demand associated to point [START_REF] Evans | A note on the existence of a solution to a problem of Stefan[END_REF].

The paper is organized as follows:

In section 2, we present preliminary results on wavelet approximation. The smooth fictitious domain method is presented in section 3. Then, the details of our method coupling smooth fictitious domain method and wavelet approximation is described in section 4. In section 5, we describe the numerical implementation of our method and present detailed numerical results for univariate elliptic problems in section 6. Conclusion follows in section 7.

Preliminary results on wavelet approximation

We refer to [START_REF] Meyer | Ondelettes et Opérateurs I: Ondelettes[END_REF] for a general introduction on wavelets and the notations used in the sequel. In the univariate situation, a sequence of nested approximation spaces {V j } j∈Z with additional conditions is used to build a multiresolution analysis of L2 (R) or eventually of the Sobolev spaces H s (R), s ∈ R.

The function φ such that the set 2 {φ j,k , j, k ∈ Z} is an Hilbertian basis of V j is called the scaling function. The orthogonal projection on V j is called P j . The detail spaces between two successive approximation spaces are denoted by W j , i.e., V j+1 = V j W j . All is designed such that W j = span{ψ j,k , k ∈ Z} where the function ψ is called the wavelet.

Two properties of a multi-resolution analysis will play a key role in the following; the regularity and the order that are related to the scaling function's smoothness and the polynomial reproduction quality of the spaces V j . We will refer to them again when describing the smoothness of the functions in V j and the approximation quality of space V j , that lead to so called Jackson and Bernstein inequalities.

We will use two constructions of wavelet bases of L 2 (R) leading to the Daubechies wavelets [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF] and to the spline3 wavelets [START_REF] Meyer | Ondelettes et Opérateurs I: Ondelettes[END_REF].

Periodized multi-resolutions, multivariate multi-resolution analysis obtained by tensorial product and adaptation to compact support wavelet construction to the interval will also be used.

We are now ready to give the Jackson and Bernstein inequalities and their corollaries [START_REF] Cohen | Wavelets methods in numerical analysis, handbook of numerical analysis[END_REF].

Theorem 1. (Jackson inequality)

Let {V j } j∈Z be the approximation spaces of a multi-resolution analysis of order n;

Let Ω ⊂ R d , if f ∈ H s (Ω), 0 < s ≤ n, then f -P j f L 2 (Ω) ≤ C J,φ Ω 2 -js f H s (Ω) ,
where the constant C J,φ Ω depends only on the chosen multi-resolution analysis( the function φ Ω stands for the scaling function on the domain Ω).

Corollary 2. Let 0 < s < t ≤ n and n be the order of the multi-resolution analysis. If f ∈ H t (Ω), then the following estimate holds

f -P j f H s (Ω) 2 -j(t-s) f H t (Ω) ,
here A B means that there exists a constant c independent of A and B such that A ≤ cB.

Theorem 3. (Bernstein inequality)

If f ∈ V j , then one has

f H s (Ω) ≤ C B,φ Ω 2 sj f L 2 (Ω) , 0 < s ≤ m,
where m is the multi-resolution analysis regularity. The constant C B,φ Ω depends only on the chosen multi-resolution analysis.

Corollary 4. Let 0 < s < t ≤ m, m be the multi-resolution analysis' regularity and n be the order of the multi-resolution analysis. If s ≤ n and

f ∈ V j , then f H t (Ω) 2 (t-s)j f H s (Ω) .
3. Smooth fictitious domain method; formulation and existence results

General formulation

We consider first the different formulations of a general problem in two dimensions even if, from section 3.2 we focus on the univariate case. We consider a standard elliptic boundary-value problem defined on a bounded, open domain ω ⊂ R 2 equipped with Dirichlet boundary condition on its boundary γ supposed to be Lipschitz continuous. It reads:

-∆ǔ + ν ǔ = f in ω, ǔ = g on γ, (1)
where f ∈ L 2 (ω) and g ∈ H 1/2 (γ) are given functions and ν is a positive constant. Its variational form is derived as Find ǔ ∈ H 1 (ω), such that ǔ = g on γ and

a ω (ǔ, v) = ( f , v) L 2 (ω) ∀v ∈ H 1 0 (ω), (2)
where the bilinear operator a ω (•,

•) that maps H 1 (ω) × H 1 (ω) to R is defined as a ω (w, v) = ω (∇w∇v + νwv)dx. (3)
Fictitious domain methods substitute (2) by a new problem defined on a simpler domain Ω ⊃ ω such that, by restriction to ω and eventually extension to the limit of some parameter (this is the case in penalization methods [START_REF] Angot | A penalization method to take into account obstacles in incompressible viscous flows[END_REF]), one can recover the solution of the initial problem. Here the solution of the fictitious domain method is constrained to have its trace on γ satisfying in the weak sense the boundary condition of (2) using Lagrange multipliers.

In classical fictitious domain methods for Dirichlet boundary conditions, the Lagrange multipliers belong then to H -1 2 (γ) as introduced in [START_REF] Haslinger | Fictitious domain methods with distributed Lagrange multipliers. part i: application to the solution of elliptic state problems[END_REF]. Using H 1 p (Ω) a suitable subspace of H 1 (Ω) we get:

       Find u ∈ H 1 p (Ω), λ ∈ H -1 2 (γ), such that a Ω (u, v)+ < T γ v, λ > γ = (f, v), ∀v ∈ H 1 p (Ω), < T γ u, µ > γ =< g, µ > γ , ∀µ ∈ H -1 2 (γ), (4)
where < •, • > γ denotes the duality pairing between H 1 2 (γ) and H -1 2 (γ), a Ω (•, •) has the same expression as (3) substituting ω by Ω, the operator T γ represents the trace operator from H 1 (Ω) to H 1 2 (γ) and f is an extension of f defined on Ω. In our univariate applications, H 1 p (Ω) will be the subspace of periodic functions of H 1 [0, 1].

The following remarks are required:

Remark 3.1.

• This saddle point problem involves clearly an extension of the right-hand side term f which is denoted by f . Without entering here into the details of the analysis we expect that the regularity of this extension constrains the regularity of the solution u and therefore the convergence speed of any numerical method involved for the numerical approximation of (4). The effective construction of an extension raises various difficulties. Some of them will be addressed in section 5.2.3.

• It is well known ( [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF]) that, the solution of (4) suffers from a lack of regularity along the boundary γ as soon as the Lagrange multiplier λ is non zero.

To circumvent the second point, the so called smooth fictitious domain method has been introduced in [START_REF] Haslinger | Projected Schur complement method for solving non-symmetric systems arising from a smooth fictitious domain approach[END_REF]. In this method, the Lagrange multipliers used to enforce the boundary condition live on a control boundary Γ = γ surrounding the domain ω and defining the control domain Ξ (shown in figure 1). More precisely, the smooth fictitious domain formulation reads:

       Find u ∈ H 1 p (Ω), λ ∈ H -1 2 (Γ), such that a Ω (u, v)+ < T Γ v, λ > Γ = (f, v), ∀v ∈ H 1 p (Ω), < T γ u, µ > γ =< g, µ > γ , ∀µ ∈ H -1 2 (γ), (5)
where T Γ stands for the trace operator from 5) has a solution (u, λ), it is easy to check that (u, λ) satisfies, in the weak sense, the following equations and boundary conditions:

H 1 p (Ω) to H 1 2 (Γ) and < •, • > Γ is the pairing between H 1 2 (Γ) and its dual space H -1 2 (Γ). If (
       -△u + νu = f in Ξ ∪ (Ω\Ξ), u = g on γ, λ = -[ ∂u ∂n ] Γ on Γ, ( 6
)
where n is the outward unit normal to Γ and [.] Γ denotes the normal jump across Γ. The restriction of u on ω therefore satisfies (1) in the weak sense.

Concerning the regularity of u, the last equation of ( 6) shows that u is globally constrained in the space H 3 2 -ǫ (Ω) as soon as the Lagrange multipliers λ is non zero. However, on Ξ, according to [START_REF] Meyer | Ondelettes et Opérateurs I: Ondelettes[END_REF], u ∈ H m+2 (Ξ) as soon as f ∈ H m (Ξ). One should notice that this situation depends directly on the smoothness of the extension of f in Ω \ω. Moreover, equation ( 5) provides a smooth extension of the solution of (1) on Ξ. This solution is smoother than the restriction to Ξ of the solution of the classical fictitious domain method (4) that indeed belongs to H 3 2 -ǫ (Ξ) due to the discontinuity of ∂u ∂n on γ. Therefore, one can expect that locally faster convergence of the numerical methods can be reached (see the next sections).

This advantage of the smooth fictitious domain method is however not given for free: indeed, it appears that there does not exist solution (u,

λ) ∈ H 1 (Ω)×H -1 2 (Γ) for arbitrary (f, g) ∈ L 2 (Ω)×H 1 2 (
γ). Indeed, if this was the case, classical interior estimates for elliptic equations show that u ∈ H 2 (O) for any open subset of O ⊂ Ξ and ,among them, for any subset containing ω. Therefore , according to the trace theorem on the interior of O, the trace of u on γ belongs to H 3 2 (γ). This is not compatible with the initial hypothesis g ∈ H 1 2 (γ). J.Haslinger and co-authors [START_REF] Haslinger | Projected Schur complement method for solving non-symmetric systems arising from a smooth fictitious domain approach[END_REF] indeed pointed out that the problem ( 5) is related to the controllability of the initial problem. A classical result of control theory asserts that the system controllability is only approximative, that means that the smooth fictitious domain method resulting problem has a solution only when g belongs to a dense subset of H 1 2 (γ). As it is shown in the next section the situation is simpler in the univariate case.

Specific analysis for the univariate case

We analyze the univariate version of problem ( 5) in the framework of existence of solution for generalized saddle point problem [START_REF] Nicolaides | Existence,uniqueness and approximation for generalized saddle point problems[END_REF]. 2, the formulation ( 5) is specified as follows:

Assuming that Ω = [0, 1], ω =]a, b[, Ξ =]a ′ , b ′ [ with 0 < a ′ < a < b < b ′ < 1 as shown in figure
Figure 2: Geometry in 1D      Find u ∈ H 1 p [0, 1], λ = (λ 1 , λ 2 ) ∈ R 2 , such that a Ω (u, v) + λ 1 v(a ′ ) + λ 2 v(b ′ ) = (f, v), ∀v ∈ H 1 p [0, 1], u(a) = g(a), u(b) = g(b). (7)
For convenience in the sequel, we note

L σ 1 = {u ∈ H 1 p (Ω) such that u| ∂ω = σ, i.e, u(a) = σ(a), u(b) = σ(b)}, L σ 2 = {u ∈ H 1 p (Ω) such that u| ∂Ξ = σ, i.e, u(a ′ ) = σ(a ′ ), u(b ′ ) = σ(b ′ )}. (8)
By Proposition 7.1.4 [START_REF] Quarteroni | Numerical approximation of partial differential equations[END_REF], it is well-known that problem (7) can be written as :

Find u ∈ L g 1 , such that a Ω (u, v) = (f, v), ∀v ∈ L 0 2 . ( 9
)
Existence and uniqueness of the solution of (9) depends on the existence of a positive constant δ such that sup

v∈L 0 2 a Ω (u, v) v H 1 p (Ω) ≥ δ u H 1 p (Ω) , ∀u ∈ L 0 1 . ( 10
)
Remark 3.2. In the classical fictitious domain method, the equation equivalent to [START_REF] Nicolaides | Existence,uniqueness and approximation for generalized saddle point problems[END_REF] is obtained inserting L 0 1 = L 0 2 . Since a Ω is coercive the condition is trivially satisfied.

Without loss of generality, we focus on a simplified version of [START_REF] Nicolaides | Existence,uniqueness and approximation for generalized saddle point problems[END_REF]

in- volving H 1 r = {u ∈ H 1 [0, 1]|u(1) = 0}, H 1 l = {u ∈ H 1 [0, 1]|u(0) = 0} and a Ω (u, v) = (u, v) H 1 (Ω)
. We then have the following lemma: Lemma 5. For any u ∈ H 1 r , there exists a positive constant c such that

sup v∈H 1 l (u, v) H 1 (Ω) v H 1 (Ω) ≥ c u H 1 (Ω) , ∀u ∈ H 1 r . (11)
Proof: By Lax-Milgram theorem, there exists a unique element

T u ∈ H 1 l such that (T u, v) H 1 (Ω) = (u, v) H 1 (Ω) , ∀v ∈ H 1 l . ( 12
) Moreover, T u -u satisfies      -(T u -u) ′′ + (T u -u) = 0, (T u -u)(0) = -u(0), (T u -u) ′ (1) = 0. (13)
A direct calculation gives T u = u + Ae x + Be -x , with A = -u(0) 1+e 2 and B = -u(0)e 2 1+e 2 , moreover,

T u 2 H 1 = u 2 H 1 - e 2 -1 e 2 + 1 (u(0)) 2 . ( 14
)
Since

1 0 u ′ (x)dx = -u(0), we have |u(0)| ≤ u H 1 . Using this inequality in (14), T u H 1 (Ω) ≥ c u H 1 (Ω) , (15)
with c = 2 e 2 +1 . Finally, sup v∈H 1 l (u, v) H 1 (Ω) v H 1 (Ω) ≥ (u, T u) H 1 (Ω) T u H 1 (Ω) ≥ c u H 1 (Ω) ,
that concludes the proof.

Following [START_REF] Nicolaides | Existence,uniqueness and approximation for generalized saddle point problems[END_REF], lemma 5 leads to the following theorem: Theorem 6. In the univariate situation, there exists a unique solution to [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF] and the initial problem has exact controllability.

Wavelet approximation

Following [START_REF] Baccou | Definition and analysis of a wavelet/fictitious domain solver for the 2d-heat equation on a general domain[END_REF], we choose a Petrov-Galerkin and a wavelet-vaguelet method to discretize [START_REF] Daubechies | Ten lectures on wavelets[END_REF]. We denote by {U Ω j } j∈Z a m ≥ 1 regular and n ≥ 1 order orthogonal multi-resolution of H 1 p [0, 1], the subset of H 1 [0, 1] of periodic elements. We define V Ω j = (-△ + νI) -1 U Ω j , j ∈ Z. The family {V Ω j } j∈Z is a bi-orthogonal multi-resolution spanned by vaguelets that inherits the important properties of classical multi-resolution by keeping the vanishing moments and decrease property of its natural bases, as seen in [START_REF] Ponenti | Algorithmes en ondelettes pour la résolution d'equations aux dérivées partielles[END_REF]. Similarly,

Q Γ j ′ (resp. Q γ j ′′ ) is a m ′ ≥ 1(resp. m ′′ ≥ 1) regular and n ′ ≥ 1 order(resp. n ′′ ≥ 1) orthogonal multi-resolution of H -1/2 (Γ)(resp. H -1/2 (γ)).
The discretized problem then reads:

     Find u j ∈ U Ω j , λ j ′ ∈ Q Γ j ′ , such that a Ω (u j , v j )+ < T Γ v j , λ j ′ > Γ = (f, v j ) ∀v j ∈ V Ω j , < T γ u j , µ j ′′ > γ =< g, µ j ′′ > γ ∀µ j ′′ ∈ Q γ j ′′ . (16)
The existence of a unique solution (u j , λ j ′ ) to ( 16) is here taken for granted.

It will be proved in Section 5.3, Remark 5.1.

Global error estimate

According to [START_REF] Baccou | Definition and analysis of a wavelet/fictitious domain solver for the 2d-heat equation on a general domain[END_REF], the approximation error uu j satisfies the following global error estimate:

If u ∈ H s (Ω), 0 < s ≤ n, λ ∈ H s ′ (Γ), 0 < s ′ ≤ n ′ , then u -u j H 1 (Ω) 2 -j(s-1) u H s (Ω) + 2 -j ′ s ′ λ H s ′ (Γ) (17)
and

u -u j L 2 (Ω) 2 -js u H s (Ω) + 2 -j ′ s ′ λ H s ′ (Γ) . (18)

Interior error estimate

The above estimates involve the full space Ω and are therefore called global estimates. In our approach involving Lagrange multipliers on the control boundary Γ, as well as in the classical fictitious domain method where the Lagrange multipliers have support on γ, the regularity of the solution u is limited to H if f ∈ H m (O). In the smooth fictitious domain method this is true for any open subset of Ξ. This local high regularity of the solution suggests that one can get for compact support approximation methods a better local rate of convergence of the approximation. Indeed, it has been shown by S.Bertoluzza [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF] that a Galerkin method based on compactly supported wavelets satisfies the general assumptions, related to the discretization spaces, sufficient to ensure some so called interior error estimate as derived in [START_REF] Nitsche | Interior estimates for Ritz-Galerkin methods[END_REF].

The proof involves two key ingredients: the compact support property of the involved wavelet basis and the multi-resolution regularity and order under which the Jackson and Bernstein type inequalities and norm equivalences follow. In our case, due to the implementation of a Petrov Galerkin method and since the operator -△ + νI is non-homogeneous, the basis of the discretization space V Ω h is not compactly supported and any interior error estimate can not be reached by a direct generalization of [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF].

However, we will be able to derive an error estimate comparable to the one in [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF] using two steps: first, modifying the right-hand side term of (1), we will show that the solution ǔ is also solution of another problem involving a homogeneous operator. A Petrov Galerkin method involving compactly supported bases and the generalization of the results of [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF] can be derived, leading to lemma 7; second, the comparison of the approximated solutions for the two problems allows to derive a new result (theorem 10). This result involves the distance between the initial boundary and the control boundary, a parameter that indeed appears naturally in our numerical results (see section 6).

Step 1: New problem and corresponding interior estimate Starting from the extension of (1) on [0, 1], we first consider the following problem:

   - ∂ 2 ∂x 2 ū = f , in [0, 1], ū(a) = g(a), ū(b) = g(b), (19)
where the right-hand side term is defined through its Fourier transform4 as fk = 4π 2 ξ 2 fk ν+4π 2 k 2 .

Applying the smooth fictitious domain method to [START_REF] Yin | On a wavelet/smooth fictitious domain method for the approximation of the Stefan problem[END_REF] with Ξ =]a ′ , b ′ [⊃ ]a, b[ leads to the following problem:

     Find ū ∈ H 1 p [0, 1], λ = ( λ1 , λ2 ) ∈ R 2 , such that a 1 (ū, v) + λ1 v(a ′ ) + λ2 v(b ′ ) = ( f , v), ∀v ∈ H 1 p [0, 1], ū(a) = g(a), ū(b) = g(b), (20)
where

a 1 (ū, v) = 1 0 ∂ ū ∂x ∂ v ∂x dx. We introduce U [0,1] j = span{φ j 0 ,k , ψ l,k , k ∈ Z, j 0 ≤ l < j},
where we assume that all the functions φ j 0 ,k , ψ l,k satisfy a dilation-translationcompact-support condition that reads: there exists a constant N such that for any k ∈ Z

suppφ j 0 ,k ⊂ [(k -N)2 -j 0 , (k + N)2 -j 0 ], suppψ l,k ⊂ [(k -N)2 -l , (k + N)2 -l ].
This condition is satisfied as soon as these functions are obtained by dilations and translations of compactly supported functions φ and ψ. Moreover we assume that the spaces {U [0,1] j } j∈Z constitute a multi-resolution analysis f L 2 [0, 1] of regularity m and order n.

Following the implementation of the Petrov-Galerkin method [START_REF] Baccou | Definition and analysis of a wavelet/fictitious domain solver for the 2d-heat equation on a general domain[END_REF] leads to consider the function ϕ defined by φ(ξ) = sin 2 (2πξ) φ(ξ) as well as the functions θl,k (x) = (-

∂ 2 ∂x 2 ) -1 ψ l,k , θj 0 ,k (x) = (- ∂ 2 ∂x 2 ) -1 ϕ j 0 ,k , that generate the space V [0,1] j = span{ θj 0 ,k , θl,k , k ∈ Z, j 0 ≤ l < j}.
Therefore the discretization form of (20) reads:

       Find ūj ∈ U [0,1] j , λj = ( λj,1 , λj,2 ) ∈ R 2 , such that a 1 (ū j , vj ) + λj,1 vj (a ′ ) + λj,2 vj (b ′ ) = ( f , vj ), ∀v j ∈ V [0,1] j , ūj (a) = g(a), ūj (b) = g(b), (21)
Note that, as mentioned in [START_REF] Lazaar | Wavelet algorithms for numerical resolution of partial differential equations[END_REF], the two spaces U [0,1] j and V [0,1] j are both generated by compactly supported bases of wavelets or vaguelets.

We then have the following Lemma:

Lemma 7. Let ω 0 ⊂ ω 1 ⊂ [0, 1], ū ∈ H l p [0, 1], ūh ∈ U [0,1] j
and p be a nonnegative integer, arbitrary but fixed. The approximation space V [0,1] j is constructed as previously. Then there exists j, for all j 0 > j, we have

ū -ūh s,ω 0 2 -j(l-s) ū l,ω 1 + ū -ūh -p,ω 1 , 1 ≤ l ≤ n, s = 0, 1,
where n denotes the order of the multi-resolution analysis U [0,1] j .

Proof:

The proof mimics the ones of Theorem 5.1 [START_REF] Nitsche | Interior estimates for Ritz-Galerkin methods[END_REF] and Theorem 2.1 [START_REF] Bertoluzza | Interior estimates for the wavelet Galerkin method[END_REF]. The essential ingredients are the compact support property of the bases of U [0,1] j and V [0,1] j and the fact that the spaces V [0,1] j are generated by vaguelets and therefore inherits the essential properties of a classical multi-resolution analysis which ensure that the Jackson estimate, Bernstein estimate and norm equivalence hold.

Step 2: Comparison of the two approximate solutions We recall that the weak formulation of problem (1) is

     Find u ∈ H 1 p [0, 1], λ = (λ 1 , λ 2 ) ∈ R 2 , such that a 2 (u, v) + λ 1 v(a ′ ) + λ 2 v(b ′ ) = (f, v), ∀v ∈ H 1 p [0, 1], u(a) = g(a), u(b) = g(b), (22)
where a 2 (u, v) = 1 0 (νuv + ∂u ∂x ∂v ∂x )dx. As above we introduce

θ l,k (x) = (- ∂ 2 ∂x 2 + νI) -1 ψ l,k (x), ϑ j 0 ,k (x) = (- ∂ 2 ∂x 2 + νI) -1 ϕ j 0 ,k (x)
, and the approximation space

V [0,1] j = span{ϑ j 0 ,k , 0 ≤ k ≤ 2 j 0 -1, θ l,k , j 0 ≤ l ≤ j -1, 0 ≤ k ≤ 2 l -1}.
The discrete form of ( 22) is now

       Find u j ∈ U [0,1] j , λ j = (λ j,1 , λ j,2 ) ∈ R 2 , such that a 2 (u j , v j ) + λ j,1 v j (a ′ ) + λ j,2 v j (b ′ ) = (f, v j ), ∀v j ∈ V [0,1] j , u j (a) = g(a), u j (b) = g(b). (23)
The comparison of u j , the solution of (23) and ūj , the solution of (21) will provide the expected result. First, we recall from [START_REF] Meyer | Ondelettes et Opérateurs I: Ondelettes[END_REF] the following Lemma about the decay of the functions θ l,k (x) and ϑ j 0 ,k (x). Lemma 8. ( [START_REF] Meyer | Ondelettes et Opérateurs I: Ondelettes[END_REF]) With θ l,k and ϑ j 0 ,k previously defined, the following inequalities hold for any q ≥ n where n is the order of the multi-resolution:

|2 2l θ l,k (x)| 2 l/2 (1 + 2 l |x -k|) q , |2 2j 0 ϑ j 0 ,k (x)| 2 j 0 /2 (1 + 2 j 0 |x -k|) q .
We have also the following inequality: Lemma 9. Let u, ū, ϕ be defined as previously, then

0≤k≤2 j 0 -1 |(u -ū, φ j 0 ,k )| 2 0≤k≤2 j 0 -1 |(u -ū, ϕ j 0 ,k )| 2 .

Proof:

The definition of ϕ j 0 ,k implies that we have

k (u -ū, ϕ j 0 ,k )φ j 0 ,k = - 1 4 k (u -ū, φ j 0 ,k+2 -2φ j 0 ,k + φ j 0 ,k-2 )φ j 0 ,k = - 1 4 k (u -ū, φ j 0 ,k )(φ j 0 ,k+2 -2φ j 0 ,k + φ j 0 ,k-2 ) = k (u -ū, φ j 0 ,k )ϕ j 0 ,k = d 2 dx 2 k (u -ū, φ j 0 ,k )̥ j 0 ,k where d 2 dx 2 ̥ j 0 ,k = ϕ j 0 ,k and ̥j 0 ,k (ξ) = -φj 0 ,k (ξ)sin 2 (2πξ/2 j 0 ) (2πξ) 2 . Let us note f 0 = k∈Z (u -ū, φ j 0 ,k )̥ j 0 ,k and f 1 = d dx f 0 . Then, d dx f 1 = k (u -ū, ϕ j 0 ,k )φ j 0 ,k . Applying Poincaré inequality leads to k |(u-ū, φ j 0 ,k )| 2 f 0 2 L 2 [0,1] f 1 2 L 2 [0,1] df 1 dx 2 L 2 [0,1] k |(u-ū, ϕ j 0 ,k )| 2
using the fact that {̥ j 0 ,k } k is a Riesz basis (theorem 2.2 [START_REF] Ponenti | Algorithmes en ondelettes pour la résolution d'equations aux dérivées partielles[END_REF]) and that {φ j 0 ,k } k is an orthonormal basis, that concludes the proof.

We are now ready to give the main theorem of this section concerning the interior error estimate.

Theorem 10. Let us consider U [0,1] j , V [0,1] j and V [0,1] j constructed as previ- ously and Ξ =]a ′ , b ′ [⊂ [0, 1], ω 0 =]a 0 , b 0 [⊂ Ξ, ω 0 ⊂ ω 1 ⊂ [0, 1]. Let us assume that the multi-resolution {U [0,1] j
} j∈Z is of order n and that p is a nonnegative integer, arbitrary but fixed. If ū ∈ H l p [0, 1] and u ∈ H 1 p [0, 1], then there exists j such that for all j 0 > j, for all q ≥ n u

-u h 1,ω 0 2 -j(l-1) ū l,ω 1 + ū -ūh -p,ω 1 + 2 -qj 0 d -q , ( 24
)
where d = min{|a ′ -a 0 |, |b ′ -b 0 |}, l ≤ n.

Proof:

We use the triangle inequality to get

u -u h 1,ω 0 ≤ u -ū 1,ω 0 + ū -ūh 1,ω 0 + ūh -u h 1,ω 0 .
Then by the norm equivalence for wavelet decomposition [START_REF] Cohen | Wavelets methods in numerical analysis, handbook of numerical analysis[END_REF], we have the upper bound of u -ū 1,ω 0 ,

u -ū 1,ω 0 ( k |(u -ū, φ j 0 ,k )| 2 + l≥j 0 k 2 2l |(u -ū, ψ l,k )| 2 ) 1/2 ( k | -λ 1 ϑ j 0 ,k (a ′ ) -λ 2 ϑ j 0 ,k (b ′ ) + λ1 θj 0 ,k (a ′ ) + λ2 θj 0 ,k (b ′ )| 2 + l≥j 0 k 2 2l | -λ 1 θ l,k (a ′ ) -λ 2 θ l,k (b ′ ) + λ1 θl,k (a ′ ) + λ2 θl,k (b ′ )| 2 ) 1/2 ,
where the second inequality is deduced from ( 22), [START_REF] Cohen | Wavelets on the interval and fast wavelet transforms[END_REF] and Lemma 9. Note that since φ j 0 ,k and ψ l,k are compactly supported, the number of terms appearing in the sum is finite. When the coarsest approximation level j 0 is large enough, θj 0 ,k (a ′ ), θj 0 ,k (b ′ ), θl,k (a ′ ) and θl,k (b ′ ) are equal to 0 as d > 0.

For the point values of functions ϑ j 0 ,k and θ l,k at a ′ and b ′ , we use lemma 8 to get

u -ū 1,ω 0 ( k | 2 j 0 /2 2 4j 0 d 2 | 2 + l≥j 0 k 2 2l | 2 l/2 2 (n+2)l d n | 2 ) 1/2 2 -qj 0 d -q .
We use the same method to get the upper bound of the term ūhu h 1,ω 0 .

Combined together with lemma 7, we have

u -u h 1,ω 0 2 -j(l-1) ū l,ω 1 + ū -ūh -p,ω 1 + 2 -qj 0 d -q ,
that concludes the proof.

Following the same track we get also

u -u h 0,ω 0 2 -jl ū l,ω 1 + ū -ūh -p,ω 1 + 2 -j 0 (1+q) d -q .
Remark 4.1.

• A consequence of (24) is that the distance between the control boundary and original boundary influences the error estimate. However, when the parameter p and q are chosen large enough, the last two terms on the right-hand side of (24) become negligible. This leads to an optimal convergence rate.

• For the bivariate case, the track of the above proof can not be followed.

Indeed point values are replaced by trace and scalar product on the control boundary. The generalization of theorem 10 to bivariate situations is still an open question.

Numerical implementation

Approximation spaces

In this section, we describe the approximation spaces used in our univariate simulations with Ω = [0, 1], ω =]a, b[ and Ξ =]a ′ , b ′ [.

Multi-resolution of H 1

p [0, 1] Spline multi-resolution has been used for the approximation of H 1 p [0, 1]. We refer to [START_REF] Perrier | La décomposition en ondelettes périodiques, un outil pour l'analyse de champs inhomogènes. théorie et algorithmes[END_REF] for the construction of orthonormal splines wavelets of order m. Explicit expressions for φ(ω), ψ(ω) are provided including there expansion in terms of translated versions of the basic spline function B m (x). 5

Approximation of operators 5.2.1. Elliptic operator

In addition to the initial basis of H 1 p [0, 1], the Petrov-Galerkin method involves the bi-orthogonal bases constructed applying the operator (νI -∂ 2 ∂x 2 ) as explained in the previous section. These bases are explicitly constructed using the Fourier transform.

Trace operator

The value of a basic spline function B m (x) on any point of its compact support can be reached explicitly thanks to the classical relation recalled in footnote 5. Since, moreover spline scaling functions φ j k and wavelets ψ j k are explicitly known in terms of the basic spline function, the computation of their value at any position and therefore of their trace is a simple and fast routine.

It has been shown in [START_REF] Chiavassa | A fully adaptive wavelet algorithm for parabolic partial differential equations[END_REF] that, up to any precision, there exists an index r such that the space V j+r contains the bi-orthogonal functions θ j k . Therefore, their trace can also be evaluated fast.

Extension operator

The numerical construction of an efficient extension operator from a set of functions defined on ω to a suitable set of functions defined on Ω ⊃ ω is constrained by different requirements. More precisely, if we denote this extension operator

E Ω ω : f ∈ F (ω) → f = E Ω ω ( f ) ∈ F (Ω) with f |ω = f , these constraints are:
1. The smoothness of f must be of same order as the smoothness of f , 2. The support of f must be as small as possible,

5    B 1 (x) = χ [0,1] , B m (x) = x m -1 B m-1 (x) + m -x m -1 B m-1 (x -1).
3. The decomposition of f on a suitable basis of F (Ω) must be obtained fast from the decomposition of f on a suitable basis of F (Ω).

The importance of the smoothness requirement has been emphasized earlier. Constraints 2. and 3. are directly linked to the efficiency of the numerical implementation. An extension operator satisfying 1. and eventually 2. in specific situations, using Fourier expansion has been proposed in [START_REF] Elghaoui | A spectral embedding method applied to the advection-diffusion equation[END_REF]. In [START_REF] Yin | On a wavelet/smooth fictitious domain method for the approximation of the Stefan problem[END_REF], a new extension operator based on compactly supported basis of a multi-resolution analysis on the interval [START_REF] Cohen | Wavelets on the interval and fast wavelet transforms[END_REF] has been derived. We provide the sketch of this extension in the sequel of the subsection for the univariate situation and

ω =]a, b[⊂ Ω = [0, 1].
Up to some rescaling and interpolation, the extension problem in our approximation framework consists in the following question: Knowing the expansion of a function f in a finite number of elements of a compactly supported wavelet basis of L 2 [0, 1], is it possible to construct a compactly supported function f e and, more precisely its expansion in a finite number of elements of a compactly supported Daubechies wavelet basis of L 2 (R) such that the restriction of f e on [0, 1] coincides with f .

Coming back to the construction of compactly supported wavelet bases on the interval defined in [START_REF] Bertoluzza | Wavelets on ]0,1[ at large scales[END_REF], it turns out that for scale parameter j ≥ 0 in the case of Daubechies wavelet basis, the scaling functions generating the approximation space V [0,1] j can be written explicitly as:

φ[0,1] j,k = N +2 j m=-N η j,k m φ j,m | [0,1] , (25)
where the coefficients η j,k m are given in the construction. Clearly, removing the restriction to [0, 1] in the right-hand side term of (25) provides a compactly supported function of the space V R j coinciding with φ[0,1] j,k on [0, 1]. In the sequel, we illustrate a comparison between this extension procedure, called MRA method, and another one, called spectral method, described in [START_REF] Elghaoui | A spectral embedding method applied to the advection-diffusion equation[END_REF] and using Fourier approximation. In figure 3, the two extensions are constructed starting from the samplings at rate h = 2 -6 of the restriction of the function f (x) = sin(2πx) on ]a, b[=]0, 0.5[. The main difference between these two methods lies in the unknown parameters computed: the unknown grid point values in the spectral method and the scaling coefficient in MRA method. We denote f s resp. f M the extension obtained by spectral and MRA method respectively. The function f s is of period 1 on R. Due to the com-pact support of Daubechies wavelet, f M is moreover compactly supported. More precisely, in our case with N = 10, suppf M ⊂ [-0.3125, 0.8125].

Numerical system and resolution

Let us define u j = 2 j -1 k=0 (U j ) k φ j k , Λ j ′ = (λ 1 , λ 2 ). The matrix form of (16) reads:

     Find U j ∈ R 2 j , Λ j ′ ∈ R 2 , such that I C D 0 U j Λ j ′ = F j G j (26) with (F j ) k = 1 0 f (x)θ j k (x)dx, C =      θ j 0 (a ′ ) θ j 0 (b ′ ) θ j 1 (a ′ ) θ j 1 (b ′ ) . . . . . . θ j 2 j -1 (a ′ ) θ j 2 j -1 (b ′ )      , D = φ j 0 (a) φ j 1 (a) • • • φ j 2 j -1 (a) φ j 0 (b) φ j 1 (b) • • • φ j 2 j -1 (b)
, and G j = u(a) u(b) .

Resolving this system (26) using Uzawa algorithm reads,

     Find U j ∈ R 2 j , Λ j ′ ∈ R 2 , such that (DC) t DCΛ j ′ = (DC) t DF j -(DC) t G j , U j = F j -CΛ j ′ .
The next theorem provides bounds for the condition number of (DC) t DC proving that this system is well-conditioned.

Theorem 11. The matrix (DC) t (DC) satisfies the following estimate:

∃0 < K 1 , K 2 < +∞ such that for all w = (w 1 , w 2 ) ∈ R 2 K 1 (w, w) l 2 ≤ ((DC) t (DC)w, w) ≤ K 2 (w, w) l 2 .
and therefore, for all j, cond 2 ((DC) t (DC)) ≤ K 2 K 1 . Proof: It mimics the proof of theorem 3.1 in [START_REF] Baccou | Definition and analysis of a wavelet/fictitious domain solver for the 2d-heat equation on a general domain[END_REF] with an embedding theorem in 1D [START_REF] Quarteroni | Numerical approximation of partial differential equations[END_REF]. See [START_REF] Yin | On a wavelet/smooth fictitious domain method for the approximation of the Stefan problem[END_REF] for details.

Remark 5.1. A direct consequence of Theorem 11 is that (DC) t (DC) is positive definite. Therefore system (26) is invertible and the problem ( 16) has a unique solution.

Numerical results

Comparison between smooth and classical multi-resolution-fictitious domain methods

We consider problem (1) with the following choices: ν = 1 4π 2 , ω =]0.2, 0.5[, ǔ = 4x 2 sin(2πx) and therefore f = (-△ + νI)ǔ and ǧ = ǔ| γ . The fictitious domain is Ω =]0, 1[ and the control domain is Ξ =]0.1, 0.7[. Splines of order 4 and scale j = 8 are used. Figure 4 shows the numerical results obtained using the smooth (SFDM) and classical (CFDM) fictitious domain methods. Figure 5 shows the error versus j in semi-logarithmic scale for different source 20 term extensions f . For the classical methods the rate is limited by -3 2 . For the smooth method a high convergence rate is reached, exceeding the result proven in our interior error estimate; it corresponds to a super convergence phenomena for multi-resolution methods that has already been observed, for instance in [START_REF] Chiavassa | A fully adaptive wavelet algorithm for parabolic partial differential equations[END_REF]. Note that, as expected, the smoothness of the extension plays an important role in the error decay.

Condition number

The condition numbers of the iterative matrix (DC) t (DC) for different values of the scale j is given in Table 1. As expected, they are numerically independent of the scale. 6 shows the error in L 2 (ω) versus j in semi-logarithmic scale for different Ξ when f is a constant or C ∞ extension. As expected, the smoother is f , the faster is the decay of the error.

Conclusions

In this paper, we proposed and analyzed a new method which combines multi-resolution approximation and smooth fictitious domain method for elliptic problems. A full analysis has been performed in the univariate situation: proof of the existence and uniqueness of the solution and its approximation, definition and estimates of global and interior errors. A complete numerical method involving extension operator approximation has been provided. Compared to a classical fictitious domain method, a higher convergence rate is proved and various numerical advantages are exhibited on different tests. In multidmension, the smooth fictitious domain method is well posed only for specific boundary conditions belonging to a dense subset of H 1 2 (γ) and the analysis of section 3 can not be generalized. However, our experience is that numerical approximation can be generalized in multidimension and our conjecture is that the convergence follows our results proved in the univariate case, including interior estimates; various numerical results can be found in ( [START_REF] Yin | On a wavelet/smooth fictitious domain method for the approximation of the Stefan problem[END_REF]).

Figure 1 :

 1 Figure 1: Geometry: ω is the original domain, γ is its boundary. Γ is the control boundary in the smooth fictitious domain method; Ξ ⊃ ω is bounded by Γ. The fictitious domain is called Ω.

Figure 3 :

 3 Figure 3: Function f on initial domain ω, denoted by solid line, and extended functions using spectral and MRA methods. The sampling points belong to the set I= {(x i , f (x i ))|x i ∈ [0, 0.5], x i = ih, h = 1/2 6 }(on the left of the vertical line). The dashed line represents the extended function f s obtained using the spectral method with p = 1, corresponding to a minimization procedure in H 2 [0, 1]. The dash-dotted line is the extended function f M using the MRA method with N = 10; f M ∈ C 2 [0, 1].

Figure 4 :

 4 Figure 4: Numerical solution reached using classical (CFDM), denoted by dotted line, and smooth (SFDM) multi-resolution fictitious domain methods, denoted by solid line, using a constant extension compared to exact solution(denoted by dashed line). The solid vertical bounds the original domain while the dashed one bounds the control domain Ξ.

Figure 5 :

 5 Figure 5: Error ||u -u j || in norm L 2 (ω) and H 1 (ω) versus j in semi-logarithmic scale. The circles stand for SFDM while cross stand for CFDM. The solid (L 2 (ω)) and dashed (H 1 (ω)) lines are the least square fits. On the left figure, the slopes from upper to bottom are -1.1045,-1.0431,-3.8677,-3.1136 while they are -1.1677,-1.1062,-6.1177,-5.8137 on the right figure.

6. 1 . 2 .

 12 Influence of the distance between ω and Ξ on the error rate To evaluate the effect of the distance d between the boundary of ω and these of Ξ on the error rate, we consider Problem (1) with ν = 1 64π 2 and an exact solution ǔ = x 4 -2x 3 + 12x 2x + 1 on ω =]0.4, 0.5[, f = (-△ + νI)ǔ, ǧ = ǔ| γ . Three different control domain are used, Ξ =]0.3, 0.6[, Ξ =]0.2, 0.7[ and Ξ =]0.1, 0.8[ corresponding to d = 0.1, 0.2 and d = 0.3.

Figure

  22

Figure 6 :

 6 Figure 6: The error in norm L 2 (ω) versus scale j with different Ξ in semi-logarithmic scale. We use circle, square, pentagram to denote the error using Ξ =]0.3, 0.6[, Ξ = ]0.2, 0.7[, Ξ =]0.1, 0.8[ respectively. The solid, dash-dotted, dotted lines stands for their corresponding least square fits. On the left figure, the solid, dash-dotted, dotted line are of slope -5.2453, -5.4576, -6.2575. On the right figure, the solid, dash-dotted, dotted lines are of slope -5.7449, -10.0684, -10.6624.

Table 1 :

 1 condition number of matrix (DC) t DC

	j	cond 2 (DC) t DC
	5	4.8525
	6	4.8494
	7	4.8496
	8	4.8496
		21

For any f ∈ L 2 (R) we note f jk (x) = 2 j/2 f (2 j x -k) its dilated (2 j ) and translated (k2 -j ) version

For any segmentation (x k ) 0≤k≤M , x 0 < x 1 < ... < x M , splines of order m ≥ 2 are C m-1 functions f such that, for each k, f | [x k ,x k+1 ] is a polynomial of degree m -2.

-ǫ , for all ǫ > 0 as soon as the Lagrange multipliers are non zero. However, on any open set O with no intersection with the boundary where the normal derivative gets a jump, it is a classical result that u ∈ H m+2 (O)

for all f ∈ L 2 (]0, 1[) its Fourier transform is defined as for all k ∈ Z, fk =1 0 f (x)e -i2πkx dx; for all f ∈ L 2 (R), f (ξ) = R f (x)e -iξx dx.

Acknowledgments: Thanks are due to A. Benhabdalla and F. Boyer from I2M-UMR 7373 (France) for fruitful discussions on the control interpretation of the smooth fictitious domain method.

(Jacques Liandrat) 1 This work is supported by National Natural Science Foundation of China (No.11226307, 61100034), the Fundamental Research Funds for the Central universities (No.JUSRP 11213)