Renaud Blanch

Rémy Dautriche

Gilles Bisson

Paolo Cignoni

Michael Garland

Alark Joshi

Jarke J Van Wijk

Dieter Schmalstieg

Alexander Lex

Marc Streit

Justin Talbot

Pat Hanrahan

Chi-Wing Fu

Andrew Hanson

Frank Van Ham

Fernanda B Viégas

Martin Wattenberg

Robert Kosara

Remco Chang

William Ribarsky

Ming Dong

Jing Hua

Xianfeng Gu

Arie Kaufman

Klaus Mueller

Patric Ljung

Anders Persson

Claes Lundström

Anders Ynnerman

Timo Ropinski

Klaus Hinrichs

Zhicheng Liu

John Stasko

Bohyoung Kim

Jinwook Seo

Bongshin Lee

George Robertson

Danyel Fisher

Tim Dwyer

Petra Isenberg

Sheelagh Carpendale

Christopher Collins

Anastasia Bezerianos

Jean-Daniel Fekete

Nathalie Henry

Riche Michael

J Mcguffin

Maneesh Agrawala

Jeffrey Heer

Michael Bostock

Melanie Tory Ivan

Viola Bart

Haar Romeny

Anna Vilanova

Marcel Breeuwer

Dendrogramix: a Hybrid Tree-Matrix Visualization Technique to Support Interactive Exploration of Dendrograms

Keywords: Agglomerative hierarchical clustering, dendrogram, Dendrogramix, hybrid visualization, interaction H.5.2 [Information Interfaces and Presentation (e.g., HCI)]: User Interfaces-GUI; I.3.6 [Computer Graphics]: Methodology and Techniques -Interaction techniques

Clustering is often a first step when trying to make sense of a large data set. A wide family of cluster analysis algorithms, namely hierarchical clustering algorithms, does not provide a partition of the data set but a hierarchy of clusters organized in a binary tree, known as a dendrogram. The dendrogram has a classical nodelink representation used by experts for various tasks like: to decide which subtrees are actual clusters (e.g., by cutting the dendrogram at a given depth); to give those clusters a name by inspecting their content; etc. We present Dendrogramix, a hybrid tree-matrix interactive visualization of dendrograms that superimposes the relationship between individual objects on to the hierarchy of clusters. Dendrogramix enables users to do tasks which involve both clusters and individual objects that are impracticable with the classical representation, like: to explain why a particular objects belongs to a particular cluster; to elicit and understand uncommon patterns (e.g., objects that could have been classified in a totally different cluster); etc. Those sensemaking tasks are supported by a consistent set of interaction techniques that facilitates the exploration of large clustering results.

INTRODUCTION

Agglomerative hierarchical clustering (AHC) [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF] is often used to group items into clusters as soon as a similarity metric enables the pairwise comparison of items. AHC is widely used because it is easy for users to figure out how the classification is built, but also * e-mail: renaud.blanch@imag.fr † e-mail: remy.dautriche@imag.fr ‡ e-mail: gilles.bisson@imag.fr because they can choose the number of clusters after the classification has been made. The understanding that users can get of AHC relies heavily on the canonical visualization of the cluster hierarchy resulting from an AHC: the dendrogram (e.g., Figure 2.b).

The dendrogram provides a visualization of the binary tree of the clusters built by the AHC (given by its node-link structure), but also an information about the homogeneity of each cluster (given by the height of the internal nodes). This visual encoding of the cluster's homogeneity helps the user to choose a level at which to cut the hierarchy in order to produce a final partition into actual clusters.

If the dendrogram visualization allows to compare clusters -by their homogeneity (their height), but also by their cardinality (their width)-, the dendrogram discards completely the original information on items, and thus does not allow any comparison involving them. Without this information in the dendrogram, it is not possible to answer some kind of questions, like: why did a specific item ended in a specific cluster, is it because it is very similar to a single other item of the cluster, or is it because it is not very dissimilar with any other member of the cluster?

In this paper, we introduce an alternative to dendrogram, namely Dendrogramix, which provides, within the same screen real estate, a visualization of the hierarchy of clusters, of their homogeneity, but also of the similarity between items. This visualization comes with a set of carefully designed interaction techniques which allows users to explore the hierarchy of clusters in order to make sense of the result of the AHC. Figure 1 shows the Dendrogramix resulting from the AHC of authors from six past (2006-2011) InfoVis conferences 1 . The 143 authors (among 1142) that have published at least 3 papers (among 512) over this period are grouped according to the similarity of their set of co-authors 2 .

RELATED WORK

The clustering itself uses the well-known AHC method [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF]. Dendrogramix is not the first attempt at showing together the clustering result and the details about items, but previous works in this area all rely on the juxtaposition of two visualizations: the classical dendrogram and another visualization for the individual items. Dendrogramix is not a juxtaposition of two visualizations but rather a mix of two visualizations. It is thus more close to recent works in the InfoVis community about hybrid visualizations. The interaction techniques provided by our Dendrogramix are also comparable to recent works focused on the interaction with visualizations, especially interaction that exploit the structure of the data visualized to guide the user.

Hierarchical Clustering Visualization

Several visualization have been proposed to display the information about items together with the clustering result (see Wilkinson & Friendly survey [START_REF] Wilkinson | The history of the cluster heat map[END_REF] for a comprehensive overview of those techniques). The raw information on items can be shown with a heat map [START_REF] Sneath | The application of computers to taxonomy[END_REF] placed side by side with the dendrogram. Such visualizations have been improved with interactions and overview+detail view to cope with the scaling issues encountered when dealing with large data sets [START_REF] Chen | Constructing overview + detail dendrogram-matrix views[END_REF].

Another way to display information about items is to show their similarity matrix rather than their raw vectors, as proposed by Gower & Digby [START_REF] Gower | Expressing complex relationships in two dimensions[END_REF]. It has the advantage of saving space when the item vectors have more dimensions than the number of items, as the similarity matrix is square and symmetric. It has also the advantage of actually showing the similarity between items as seen by the system, rather than letting the user reconstruct it from the visual similarity of the row vectors from the heat map which can be misleading. For those reasons we have also chosen to use the similarity matrix as a starting point to provide information on items.

Our main contribution on the graphic representation is that the Dendrogramix embeds the information about items into the visualization of the tree representing the clustering result.

Hybrid Visualizations

Another way to cope with scaling issues is to use different representations for sub-parts of a data-set (e.g., node-link and treemap for trees, as in elastic hierarchies [START_REF] Zhao | Elastic hierarchies: Combining treemaps and node-link diagrams[END_REF], or node-link and adjacency matrix for graphs, as in MatLink [START_REF] Henry | MatLink: Enhanced matrix visualization for analyzing social networks[END_REF], NodeTrix [START_REF] Henry | NodeTrix: Hybrid representation for analyzing social networks[END_REF], or TreeMatrix [START_REF] Rufiange | TreeMatrix: A hybrid visualization of compound graphs[END_REF]). The choice for a specific representation for a part of the data can be made interactively by the user, as in NodeTrix, or take advantage of theoretical results about the space-efficiency of various representations (e.g, for trees [START_REF] Mcguffin | Quantifying the space-efficiency of 2D graphical representations of trees[END_REF]) to automatically switch from a representation to another at various levels of aggregation. Javed & Elmqvist proposed a design space of such composite visualizations and some guidelines to choose a relevant composition [START_REF] Javed | Exploring the design space of composite visualization[END_REF].

Such hybrid visualizations have been used to display large dendrograms. In Stacked Trees [START_REF] Bisson | Improving visualization of large hierarchical clustering[END_REF], the classical dendrogram visualization is used for the largest clusters, but above an homogeneity threshold the visualization switches to a stack of leaves rather than going on with the tree representation. This saves space at the expense of loosing structural information.

Our Dendrogramix is also hybrid but in a different way: it combines the visualizations of two different data sets that do not have the same structure: the input of the AHC -a matrix storing the items similarity-, and the output of the AHC -a binary tree depicting the clusters and their homogeneity.

Interaction Techniques

The interaction techniques designed to explore the Dendrogramix follow the principles of direct manipulation [START_REF] Shneiderman | Direct manipulation: A step beyond programming languages[END_REF], especially the fact that they should be rapid, reversible, and incremental. The main challenge here is that the data structures manipulated are inherently discrete. Making the interaction continuous requires the use of animated transitions controlled either by the system or by the user to switch between coherent states of the visualization. Zoomable Treemaps [START_REF] Blanch | Browsing zoomable treemaps: Structureaware multi-scale navigation techniques[END_REF] is a good example of previous work that provides a continuous interaction with the discrete data structure of a tree visualized as a treemap. We borrowed from Zoomable Treemaps the idea of using a crossing-based interaction [START_REF] Apitz | CrossY: a crossing-based drawing application[END_REF] to perform an advanced selection (of two clusters simultaneously in our case; of an arbitrary internal node of the treemap in their case). Most of the interaction techniques proposed by Dendrogramix fit in the framework of interactions with hierarchical aggregation proposed by Elmqvist & Fekete [START_REF] Elmqvist | Hierarchical aggregation for information visualization: Overview, techniques, and design guidelines[END_REF]. However, they do not consider interactions altering the layout (such as node reordering) in their framework.

DENDROGRAMIX

A Dendrogramix is an hybrid visualization that mixes the similarity matrix of items with the binary tree of clusters resulting from their AHC. We first describe how the visualization is built and what kind of observations can be made using it. We then describe the interaction techniques that allow its exploration.

Visualization

Figure 2.a shows the data set -five points of the plan-used below to illustrate how a Dendrogramix is built. Figure 2.b shows the result of an AHC of this data set using the Euclidean distance to measure the similarity between two points, and the minimum distance between the elements of two clusters to generalize this similarity measure to clusters (i.e., the single linkage method).

Construction

Using the tree of clusters and the similarity matrix as inputs, the Dendrogramix is built:

1. by encoding the similarity matrix using the size of the circular dots to denote similarity (large dots means similar items) -Figure 3.a;

2. by reordering the matrix with an order of the items given by a traversal of the leaves of the clusters tree -Figure 3.b;

3. by highlighting the boundaries of the clusters (which are contiguous because of the previous step), and by encoding their homogeneity using the level of gray of their background (black means an homogeneous cluster) -Figure 3.c; and 4. by keeping only an half of the matrix (since it is symmetrical, no information is lost), and by tilting it at 45 • to have the root of the tree at the top and its leaves at the bottom -Figure 3.d.

For the first step, the similarity is normalized, and the radius of the circular dots are equal to the square root of this normalized similarity, so that the area of the dots is proportional to the similarity.

For the second step, we use an optimal order for the leaves, i.e. an order that minimizes the sum of the distances between adjacent items. For the third step, the mapping between the cluster homogeneity and the gray scale is linear: black denotes a cluster as homogeneous as possible (consisting of identical items), and white denotes the less homogeneous cluster (the root cluster consisting of the whole set of items).

A B C D E

A B C D E B D E C A B D E C A B D E C A B D E C A (a) (b) (c) B D E C A B D E C A (d) (e)
For the last step, besides the half-matrix tilt, it is possible to apply a deformation that compresses the matrix. The farther from the diagonal a point is, the more compressed it is. This makes sense because, if the ordering of the leaves is good, then most of the information is concentrated near the diagonal of the matrix. This distortion thus allows to save space while keeping most of the information legible. This space can then be used in turn to show the labels of the items.

Design Rationale

Various choices led to the design presented above. First, the superimposition of the matrix and the tree has been chosen because it allows for a direct comparison of groups homogeneity and item similarity. We could have juxtaposed the similarity matrix to a classical dendrogram, but it would have used more space. Moreover, dendrograms are often juxtaposed with heat maps (that show the raw items' data). With the Dendrogramix, we keep this juxtaposition possible while also showing the similarities.

Once this choice is made, the retinal variables available to encode the items' similarities and the clusters' homogeneities are limited as the positions are already fixed by the tabular layout. The best remaining retinal variables (using Bertin's terminology) are thus size and value. Since the clusters' geometry is defined by their containment, we used their value to encode homogeneity. This makes it hard to do absolute judgments on homogeneity, but the most frequent task is to compare the homogeneity of one cluster to the homogeneity of its parent, and this task maps nicely to a relative judgment on the values (contrast) of two adjacent areas.

The size is then used to encode the similarity between items. As the homogeneity of a cluster is an aggregation of the similarities of its items, the two retinal variables correlate: the value of a cluster is directly linked to the sizes of the similarities. It is then easy to spot the abnormal similarities (large dots on a light background or missing dots on a dark background) that are worth investigating.

Interaction Techniques

Figure 1 shows a Dendrogramix that displays the AHC of 142 In-foVis authors. Figure 4 shows a close-up on a specific cluster. On this cluster we can make some observations that show how Dendrogramix is effective at helping understand the result of the AHC, and how it is linked to the raw data. The Dendrogramix is interactive: it comes with a coherent set of interaction techniques that allows making such observations through the data set exploration.

Sample Exploration

We can see that authors that work at the same place are effectively grouped together. The first cluster on the left is obviously a research group (the SciVis group at Linköping University). Then we have a larger cluster consisting of people from various groups (the Information Interfaces Group at Georgia Tech, the VibeVis group at Microsoft Research, the Aviz group at INRIA, etc.) that had links at that time through various collaborations.

We can see that those groups are linked by people that are prolific and collaborate a lot (e.g., Nathalie Henry Riche, Bongshin Lee or Michael McGuffin). Those "social" people that link smallest clusters are characterized by their long series of dots on their row/column of the similarity matrix. This kind of information would be totally lost if the clustering result were presented using a classical dendrogram.

The similarity information on items helps understand clusters at a finer level. The cluster on the right, consisting of three people (Maneesh Agrawala, Jeffrey Heer, and Michael Bostock), is very homogeneous. But its links to the other clusters are not: if the three of them are linked with George Robertson, the dots pattern also conveys the information that it is Jeffrey Heer who connects this cluster to the InfoVis authors community.

To draw such conclusions, some interactive exploration is needed. The interaction techniques used are described below.

Items Comparison

Hovering the visualization with the mouse cursor allows to get information about the items (Figure 5).

When hovering a label, the corresponding item is highlighted, as well as its row and column in the matrix (e.g., Figure 5.a shows the highlight of George Robertson). When an item is highlighted, its similarity with the other items is shown above the labels with a row of rectangles, their value giving the similarity.

When hovering the matrix, the position of the cursor designate two items (a row and a column). Their labels, as well as their rows and columns, are highlighted (e.g., Figure 5.b shows the simultaneous highlight of George Robertson and Jeffrey Heer). The row of rectangle between the matrix and the labels then shows the correlation of the two current items similarities. While hovering the matrix, the position of the cursor also designate a cluster: this cluster is linked to the pair of items highlighted because it is the most specific (smallest) cluster that contains both of them. We call this cluster the current cluster. The outline of this current cluster is highlighted, as well as the labels of the items it contains. It can then be manipulated as described below.

Cluster Aggregation

The clusters can be annotated: pressing the return key switches to the edition mode for the current cluster. The user can then give a label to this cluster. This label is displayed near the root of the cluster (Figure 6.a shows a cluster of 5 people labeled as "MSR").

If the user clicks, the current cluster is folded, and its label (if it has been given any) is used to display the cluster among the items (Figure 6.b). The columns and rows of the similarity matrix are then replaced with an aggregation: it shows the similarity of the cluster with the other items using the linkage method of the AHC. That is an interesting property of AHC for us: clusters are, by definition, aggregations of their content, and the linkage method gives us the pertinent function to aggregate the information of items similarity when considering clusters. Once folded, clusters act exactly as items: it is possible to compare an item to a folded cluster, or two folded clusters together. It is also of course possible to fold a cluster that contains an already-folded sub-cluster.

If the user clicks on a folded cluster, it unfolds to reveal the detail of its content. Those transitions are continuously animated so that the user is not disoriented.

Tree Reordering

A drag-and-drop interaction allows to reorder the items by moving the current cluster (Figure 7). Since the order of items should be compatible with a permutation of the hierarchy of clusters coming from the AHC, the drag-and-drop is constrained. When dragging the current cluster towards the right (resp. left) there is no problem as long as the cluster being dragged is the left (resp. right) child of its parent: swapping it with its sibling effectively moves it to the right (resp. left). But if the current cluster is the right (resp. left) child of its parent, the system has to look for its smallest ancestor that is a left (resp. right) children of its parent to be able to swap it in the appropriate direction. We provide a continuous control and feedback for an operation that is discrete in essence: the swapping of the two clusters. During the interaction (Figure 7.b and c), the position of the cluster being manipulated is constrained so that it stays within its parent and it does not overlap its sibling. Its movement has an inverted-V shape: it goes up towards the root of its parent; when it reaches this point, its brother pass below to the other side; and then it can go down to the other side. When the user ends the drag before reaching the new position, the movement is animated by the system: the cluster goes back to its starting point if it did not cross its sibling yet (Figure 7.b); or it goes on to the other side in the other case (Figure 7.c).

During the interaction and the animation, the dots giving the similarity and the labels are not draw because they rely on the order of the items, but this order is then ill-defined.

Clusters Bi-Manipulation

We provide an other way to reorder the tree: by specifying two clusters and then bringing them side by side. This interaction has been designed for a common use case: two similar clusters can be distant despite the optimal ordering. In this case, a rectangular pattern of dots can be seen away from the diagonal (Figure 8.a). The user can select the two corresponding clusters simultaneously using a crossing-based interaction (Figure 8.b): the smallest clusters including the projection of the cursor trace (in blue) on the rows and columns are selected (on the left, a cluster of three items is highlighted in red; on the right, a cluster of ten items is highlighted in green). The intersection of the two highlighted strips can then be dragged, and the projection of the cursor movements on the rows and columns control independently the two selected clusters (Figure 8.c). As during the simple drag, a continuous feedback is provided, and the similarity matrix and the labels are not displayed. The whole information is displayed anew upon the completion of the interaction (Figure 8.d).

Partition Selection

An additional visualization is juxtaposed on the top left corner of the Dendrogramix (Figure 9). It plots the relationship between the number of clusters and their homogeneity. This visualization is interactive, and it makes it possible for the user to select a partition of the items. By dragging the labels, the user can choose a number of clusters on the horizontal axis, or an homogeneity on the vertical axis. The resulting partition is shown by a thick border and highlighted by a halo which separates the clusters more homogeneous than the cut (below the border) from the clusters less homogeneous (above the border).

Implementation

The Dendrogramix prototype3 consists in less than 1500 lines of Python4 code: about 100 for allowing reading various kind of data; 150 for performing the clustering (including the optimal order implementation); 550 for handling the graphical output; 450 for handling the interaction; and 250 lines of various utility functions.

The AHC is performed using the scipy.cluster.hierarchy5 C extension for Python. The optimal order for the items is computed using the Bar-Jospeh et al. algorithm [START_REF] Bar-Joseph | K-ary clustering with optimal leaf ordering for gene expression data[END_REF] that finds an optimum in the set all the permutations of the binary tree. Despite the dynamic programming techniques used, its complexity remains cubic (e.g., finding an optimal order for the 142 InfoVis authors takes 1.22 seconds on a recent computer, whereas finding an optimal order for a sub-set of 91 of them takes only 0.31 seconds). Some remarks though: first, those values could be cut by an order of magnitude by implementing the algorithm in C rather than Python. Since the complexity of the AHC is also polynomial (at best quadratic), the optimal ordering just faces the same bottleneck as the clustering itself. Second, an optimal ordering is not mandatory to build the Dendrogramix. As with the classical dendrogram, any order of the leaves compatible with the traversal of the cluster tree can be used. Using an optimal order has the property of bringing the densest parts of the similarity matrix as close as possible to its diagonal, thus concentrating the information towards the bottom of the Dendrogramix.

For the interactive graphic rendering, our prototype takes advantage of the hardware acceleration provided by the GPU by using the OpenGL6 library. The interface with the windowing system is managed by the OpenGL Utility Toolkit (GLUT) 7 . The Python bindings to OpenGL and GLUT are provided by the PyOpenGL8 package. Those choices make our prototype portable.

We use various techniques in order to perform the rendering sufficiently fast to provide smooth animations and fluid interactions while using an interpreted language. First, we use the programmable pipeline of OpenGL to perform various costly operations. The circular dots are rendered using simple squares that are textured procedurally as antialiased circles by a fragment shader. The non-linear transformations of the matrix are performed by a vertex shader. This shader compresses the matrix by altering the ordinate of each vertex while preserving its abscissa using the following transformation:

y = α log 1 + y α (1)
where y (resp. y ) is the distance to the diagonal before (resp. after) the compression, and α a parameter that can be modified interactively by the user (the smaller is α, the more compressed is the matrix). The vertex shader also performs the folding of the matrix.

The main program shares with the shader an array of coefficients that stores for each item how much its parent clusters have been folded. The shader uses this information to alter the geometry of the Dendrogramix so that the width of the column and the height of the row corresponding to an item are scaled accordingly (e.g., if a cluster of five items is folded, each item is scaled down by a factor of 1/5, so that the folded cluster takes the same space as a single item).

The second technique we use is to cache various part of the rendering using OpenGL display lists. Those display lists are invalidated automatically by a state tracking mechanism. (e.g., the matrix is rendered in direct mode once at the beginning of the program and that rendering is reused as long as the leaves are not reordered). Using those techniques, we are able to render a Dendrogramix at more than 30 frames per second when necessary.

Finally, our prototype is also able to generate a static vector graphic output (in SVG format) suitable for integration with various graphical tools. Figure 1

EVALUATION

To evaluate the Dendrogramix visualization, we have conducted an experiment that compares it to the classical dendrogram. The experiment is a case study in which experts where shown a dataset related to their area of expertise and asked to think-aloud during their exploration of the dataset. We then used an insight-based evaluation method [START_REF] Saraiya | An insight-based methodology for evaluating bioinformatics visualizations[END_REF][START_REF] North | A comparison of benchmark task and insight evaluation methods for information visualization[END_REF] to quantify the performance of the two visualization techniques. We used this methodology because we knew that some specific tasks would not be possible at all with the classical visualization, and thus including those tasks in a controlled experiment would have made no sense, but excluding them would not have demonstrated the whole potential of Dendrogramix.

Data set

In this case study, users are a set of 6 senior researchers of a computer science research center that employ about 200 permanent researchers. They are either deputy director of the research center, or leading a research team of 6 to 12 permanent researchers (as team leaders, they are members of the scientific council of the research center). Those positions give to all of them a very good knowledge of the structure of the research center and of the research themes of the various research teams.

The data submitted to their assessment is a clustering of the permanent researchers of the research center (Figure 10). Those 189 researchers are each characterized by how many publications they have coauthored with each possible coauthor involved in a publication of the research center, i.e. a vector of length 2688 (the number of unique authors found in the research center bibliographical database). The distance used to compute the similarity between authors is the cosine distance. The generalization of this similarity to groups uses the average method.

The list of authors was deduplicated manually (112 duplicates where found amongst the 2800 names present in the database). The publication database included 3245 references for a four years period (2010-2013).

Visualizations

The resulting clustering was presented graphically using two techniques: the classical dendrogram (CD) and the Dendrogramix (DX). They both fitted on a 1920 × 1200, 23" Apple Cinema HD Display LCD screen. Figure 10 shows on the left the classical dendrogram and on the right the Dendrogramix visualization used (both rotated to better fit on the paper). The labels of the items are the names of the researchers followed by the names of their teams in capital letters. Those strings are obfuscated on Figure 10 for anonymization purpose, but they were displayed in clear for the case study.

The interaction techniques proposed with the visualizations were restricted to the bare minimum: the items were highlighted on hovering, and a search field allowed to enter a string in order to highlight all its occurrences in the items labels. That allowed the users to quickly find specific researchers or research teams. This lack of interaction is also deliberate to put the two techniques on par: classical dendrograms do not come with interactions and we did not want to favor our technique.

Protocol

The experiment consisted in three phases for each participant: first an introduction to the data set and the visualization techniques was made; then the participants were invited to explore the data and report their findings by thinking-aloud; and finally a quick wrap-up was conducted. The whole session lasted one hour.

The first phase lasted about 10 minutes during which the source of the data and the construction of the HCA was elicited. As they were all computer scientists, all participants were familiar to some extent with HCA and classical dendrograms.

In the second phase they used each of the visualization in turn during 20 minutes. They were instructed to first look at themselves; then at their team; then, at their will, at other teams or any other subject of interest to them. Half of the participants used CD first, then DX, whereas the other half used the two techniques in the other order. They reported their findings vocally and were encouraged to ask questions and formulate hypothesis. We took notes and recorded the audio of those interviews for further analysis and coding.

Finally, we asked them for their observations and comments about the two visualizations in a 10 minutes wrap-up session at the end of the interview.

Results

To analyze the results of this experiment, we used the insightbased methodology described by North, Saraiya et al. [START_REF] North | A comparison of benchmark task and insight evaluation methods for information visualization[END_REF]: we first counted the various insights found by the participants, then characterized them. The two main characteristics used are the category and the domain value, with definitions adapted from Saraiya, North et al. [START_REF] Saraiya | An insight-based methodology for evaluating bioinformatics visualizations[END_REF] (emphasized text below). We used 4 categories: overview (overall distributions of [researchers]), patterns (identification or comparison across data attributes), groups (identification or comparison of groups of [researchers]), and details (focused information about specific [researchers]). The domain value is rated between 1 and 5: trivial observations earn 1-2 points, insights about a particular [structure] earn an intermediate value of 3, and insights that confirm, deny, or create a hypothesis earn 4 or 5 points. The ratings have been established by asking the participants during the wrap-up session for the relative importances of their findings. All the participants gave an order mostly consistent with the other ones. The time spent was not considered as a characteristic since it was specified a priori (20 minutes per technique). column reports the count of insights that are common to both techniques. This gives the very first observation about the results: almost all the insights found with CD are also seen with DX. Since half of the participants were using CD first then DX, it means that for them, all the insights they found with CD were also observable with DX, and they found new ones with DX. On the other hand, participants that started with DX did not found any new insight when switching latter to CD. The second observation is about the values of insights: DX gave insights scoring 2.49 on average vs. 1.86 for CD. So DX not only gives more insights (1.8 times more) than CD, but those insights are of higher value. This difference in quality can be illustrated with examples of insights. Participants often started their investigations by looking-up their own name, then looking at their team, then looking for other structures. Thus, they generally started by insights on items, and then moved towards higher levels of details.

Details

Insights about details mainly occurred to participants looking up their own names. Most of those insights came while looking for the closest collaborators suggested by the clustering. Those insights are of low value: they are not surprising; but they gave participants trust in the visualizations. Other insights came after having investigated more high level structures and then coming back to individuals. They were less trivial, e.g., "the leader of this research group does not collaborate with any of the group researcher, is this deliberate?" This second type of insights was made only with DX.

Groups

Insights about groups were mainly observations about the structure of research teams. Using the search field, participants highlighted the members of teams they knew well (their own team and teams familiar to them). Various kind of structures are observed with both visualizations: a coherent team forming a unique cluster; teams clustered into 2 or more main groups; and teams with members disseminated in various other groups. People were sometime surprised by those findings, but found explanations to those structures (often linked to the history of the team).

Patterns

The patterns found are interesting: they are all insights about the relationship between researchers and groups of researchers. Such insights are found almost exclusively with DX.

A simple pattern is a group of 10 people from various teams clustered together mostly without any research interest in common. All participants noticed this group and found an explanation for it: it is the board of deputy directors of the research center. The co-publications linking them are the activity reports of the center that are included in the bibliographical database used for the visualizations. Moreover, many participants noticed that this group is also linked to researchers outside the group in a pattern that forms a "grid" as highlighted in blue on the Dendrogramix of Figure 10.

To appear in IEEE Transactions on Visualization and Computer Graphics (Proceedings of PacificVis 2015).

Those researchers are in fact team leaders (and, as such, co-authors of the activity reports), but are more tightly linked to their teams than the deputy directors since they still have a research activity.

Another frequent insight found is related to a "cross" pattern as highlighted in red on the Dendrogramix of Figure 10. That cross links two otherwise disjoint clusters. One occurrence of the pattern can be explained by the presence of two research engineers, each in one team, who link those teams because they work together on a research infrastructure used by both teams. The other occurrence has a similar explanation.

Other insights came after looking at the largest dots (or groups of dots) found far from the base of DX. They represent people that links two groups of researcher that are not otherwise connected (sometimes the two groups are sub-parts of a single research teams).

Overview

Few overview insights were given: they related mostly to the size of the research center, the number of teams and their relative sizes.

Discussion

As already stated, almost all insights found with CD were also found with DX. The two last lines of Table 1 show the superiority of DX over CD: DX gives more insights per unit of time (.54 vs. .30 insight per minute) but also provides better insights (2.49 vs. 1.86 points) resulting in a 2.41 higher "domain value throughput" (1.35 vs. .56 points per minute).

While overall superior, the Dendrogramix technique is especially good at showings patterns linking items to clusters they do not belong to. The classical dendrogram lacks this expressiveness: once an item is in a cluster, its links to other clusters are not considered.

However some limitations of this work should be acknowledged: the first one is that this technique is well suited only for a strict hierarchical clustering. The Dendrogramix relies on the tree structure for the visualization as well as for the interaction. It may not be possible to adapt this technique to other clustering methods in which clusters can overlap.

Finally, the methodology used for the evaluation could be disputed. We chose the insight-based methodology because the two techniques are not directly comparable: some tasks (e.g., items comparisons) can just not be performed with CD. We could have opted for a more controlled experiment, but to do so, we would have had to enhance the CD. One solution would have been to juxtapose the similarity matrix to the dendrogram, but this is not a viable option in a realistic scenario: the space next to the dendrogram is often reserved for a heat map displaying the raw items. The insight-based methodology allowed us to compare the techniques as they are.

CONCLUSION AND FUTURE WORK

We have introduced Dendrogramix, an interactive visualization that allows the presentation and the exploration of the result of an AHC. This visualization gives clues to the user about the way clusters have been generated and about the role of the particular items in this construction. The interaction techniques we have presented makes the exploration and the annotation of the tree of clusters possible, thus helping users make sense of them.

We plan to extend this work in two main directions. First, we would like to use Dendrogramix to provide a tool that would allow the comparison of different clustering algorithms. Indeed, the impact of the similarity metric and the linkage method used on the result of an AHC is difficult to grasp, but superimposing the input (the similarity matrix) and the output (the hierarchy of clusters), as the Dendrogramix does, helps to understand the clustering process. Displaying multiple Dendrogramix of the same data set clustered with different methods may help users gain a finer understanding of the various clustering techniques.

Second, we want to explore the use of Dendrogramix on the result of co-clustering algorithms. A possible way to do that would be to juxtapose 2 Dendrogramices with a heat map as it is often done for classical dendrograms: one on the top that would allow to reorder and fold the columns of the heat map, and one on the side that would allow to manipulate its rows. Those future works will be conducted in cooperation with machine learning specialists and experts from a domain using (co-)clustering algorithms heavily (namely proteomics) in order to evaluate formally the advantages of such extended visualizations. Initial feedbacks are very promising.

Figure 2 :

 2 Figure 2: Data set used for illustration purpose in Figure 3: (a) points of the plan; and (b) dendrogram of the data using Euclidean distance and single-linkage agglomerative hierarchical clustering.

Figure 3 :

 3 Figure 3: From similarity matrix to Dendrogramix: (a) graphic encoding of the similarity; (b) matrix reordered with an (optimal) order compatible with a traversal of the tree of clusters; (c) graphic encoding of clusters; (d) Dendrogramix compared to (e) classic dendrogram showing the same hierarchical clustering of the same data.

Figure 4 :

 4 Figure 4: Cluster detail, research groups are visible as homogeneous (dark) clusters, "social" people as having many dots connecting them to other people outside their research group.

Figure 5 :

 5 Figure 5: Items: (a) highlight; and (b) pairwise comparison.

Figure 6 :

 6 Figure 6: Cluster (a) labeling; and (b) folding.

Figure 7 :

 7 Figure 7: Cluster reordering using drag-and-drop: (a) initial state, (b-c) intermediate states, (d) final state with clusters swapped.

Figure 8 :

 8 Figure 8: Bringing two clusters side by side: (a-b) crossing-based bi-selection, and (c-d) bi-drag.

Figure 9 :

 9 Figure 9: Selection of a partition.

Figure 10 :

 10 Figure 10: Collaborations between 189 researchers visualized with: (left) a classical dendrogram (CD); and (right) a Dendrogramix (DX) with insights revealed by patterns highlighted in blue (top, "grid" pattern) and red (middle, "cross" patterns). The names of the researchers have been obfuscated and the figures rotated to better fit on the paper.

  is an example of such a vector graphics image, whereas the other Figures use screen captures of the raster graphics produced by OpenGL in order to show the feedback of the interaction techniques.

Table 1

 1

	gives an overview of the insights' counts and values
	broken-up by techniques (columns) and categories (lines). The last

Table 1 :

 1 Number of insights and their value per visualization technique, dendrogram (CD) and Dendrogramix (DX); and category.

The data set has been automatically extracted from on-line digital libraries, and manually curated for author deduplication.

[START_REF] Bar-Joseph | K-ary clustering with optimal leaf ordering for gene expression data[END_REF] In this example, the measure of similarity is the cosine similarity, and the distance between clusters uses the single-linkage method.

Dendrogramix, <http://iihm.imag.fr/blanch/projects/dendrogramix/>.

Python, <http://python.org/>.

SciPy library, <http://scipy.org/>.

OpenGL, <http://opengl.org/>.

GLUT, <http://www.opengl.org/resources/libraries/glut/>.

PyOpenGL, <http://pyopengl.sourceforge.net/>.

ACKNOWLEDGMENTS

Thanks to Michael McGuffin, Nathalie Henry-Riche, Jean-Daniel Fekete for early feedback. Many thanks to the various people cited in the examples without having been asked.


We have present a full Eulerian approach to deal with the aerodynamic performance and stability of a new designed airship. It consists first on setting the needed fluid solvers (Navier-Stokes equations coupled to a Spallart almaras turbulent model), then on a geometric representation through a level set method that separates each phase: external air, membrane and internal gaz. Finally, we extend this framework to embed a fluidmembrane model through interfacial forces. This model consists on implementing bending and inextensibility forces and adding them to the Navier-sotek equations. The framework was tested first in 3D to analyze the flow past a fixed airship and compute the aerodynamic forces. Then a fluid-membrane benchmark is used to validate the implementation. This work allows us to highlight several numerical challenges: first, the implementation of a high order derivative using smooth projection is needed to ensure free-oscillation forces, then the use of an unified compressible-incompressible solver to take into account the internal gaz of the the airship, finally, the analysis of the envelop proposed by Thales Alenia Space to deduce the physical parameters for our fluid-membrane model.

Introduction

The fluid-structure interaction problem is one of the most active areas of research in numerical simulation in the coming years. The immediate and potential applications include the vast majority of industrial, social and environmental domains. The simulation of fluid-structure interaction is made possible by the considerable progress of computer and technological resources but also by the maturity of the numerical methods for the study of complex physical systems involving laminar or turbulent fluids and rigid or flexible structures. There is a significant number of applications within this theme, particularly in the fields of civil engineering (bridges, towers), medicine (blood flow in the arteries) or aeronautics (flow around airships). In practice, different calculation codes are used to model this interaction, which must be both robust, accurate but also ensuring the conservation of energy and the data relating to the structure, the fluid and the interface resolution. The results of the numerical simulation, especially its stability and accuracy, depend strongly on the parameters, the physical characteristics of the model chosen, the methods and algorithms used.

The project SRATOBUS, the subject of this thesis, aim to study the stability of a new airship, operating at an altitude of about 20 kilometers (halfway between satellites and drones) that can be able to carry payloads up to 250 kg and provide 5 kW of power. It will cover a wide range of missions such as the surveillance of borders or high-value sites, , security (the fight against terrorism, drug trafficking, etc.), environmental monitoring (forest fires, soil erosion, pollution, etc.) and telecommunications (Internet. This airship, as shown in 1, is 100 meters long, 33 meters maximum diameter, and offer a lifespan in the stratosphere of five years. Recall that the subject of this thesis is to analyze the performance of each design and to study the performance of the airship in an extreme environment. Therefore, three main subjects will be treated along the PhD thesis:

• Aerodynamic: simulation of turbulent flows past different design and shapes of the airship • Aerothermal: simulation mainly of natural convection and temperature variations • Aeroelasticity: simulation of the fluid -envelope interaction In this report, we started to cover the first and the third points. Indeed, the turbulent flow past the airship will induce aerodynamic forces on the hull of the airship, which in return will or may deform its envelope. Such simulation is very challenging due to the difference in scale; the thickness of the envelope is around 5cm. Therefore, we start by setting the first 3D simulation of the flow past the new designed airship, proposed by Thales Alenia Space, then we highlight the advantages and perspectives of the existing fluid mechanics solvers, and finally we study the implementation of a new fluid-membrane numerical method. Inspired from biomechanics applications, we propose here to model an immersed membrane in an incompressible fluid through interfacial forces. Different experimental, numerical and theoretical studies were proposed on this subject [START_REF] Helfrich | Elastic properties of lipid bilayers: theory and possible experiments[END_REF][START_REF] Miao | Budding transitions of fluid-bilayer vesicles: The effect of area-difference elasticity[END_REF][START_REF] Seifert | Shape transformations of vesicles: Phase diagram for spontaneous-curvature and bilayer-coupling models[END_REF][START_REF] Abkarian | Tank treading and unbinding of deformable vesicles in shear flow: determination of the lift force[END_REF][START_REF] Haas | Deformation of giant lipid bilayer vesicles in shear flow[END_REF][START_REF] Kantsler | Transition to tumbling and two regimes of tumbling motion of a vesicle in shear flow[END_REF]. We mainly focused and implemented the orginal idea introduced first by [START_REF] Cottet | Approche eulérienne et méthodes level-set pour l'interaction fluide-structure[END_REF] and completed later by [START_REF] Salac | A level set projection model of lipid vesicles in general flows[END_REF][START_REF] Salac | Reynolds number effects on lipid vesicles[END_REF][START_REF] Doyeux | Simulation of two-fluid flows using a finite element/level set method. application to bubbles and vesicle dynamics[END_REF].

Governing equations

In this section, we briefly present the governing equations, namely the unsteady incompressible Navier-Stokes equations coupled to the Spalart-Allmaras turbulence model, and their discretization. We first recall the stabilized Finite Element scheme for the Navier-Stokes equations derived from a variational multiscale point of view where both the velocity and the pressure fields are decomposed into coarse and small scale [START_REF] Hachem | A three-field stabilized finite element method for fluid-structure interaction: elastic solid and rigid body limit[END_REF][START_REF] Hachem | Modeling of heat transfer and turbulent flows inside industrial furnaces[END_REF][START_REF] Brogniez | A high-order discontinuous galerkin method with lagrange multipliers for advection-diffusion problems[END_REF][START_REF] Jannoun | Anisotropic meshing with time-stepping control for unsteady convection-dominated problems[END_REF]. The static condensation for the small scale into the large scale will provide additional terms to the Galerkin formulation. These terms allow to cure the spurious oscillations in the convection-dominated regime and to deal with the pressure instability. Second, we recall the stabilized Finite Element scheme for the Spalart-Allmaras transport equation [START_REF] Spalart | A one equation turbulence model for aerodinamic flows[END_REF] derived simply from the Streamline Upwind Petrov-Galerkin (SUPG) method [START_REF] Brooks | Streamline upwind/petrov-galerkin formulations for convection dominated flows with particular emphasis on the incompressible navier-stokes equations[END_REF].

The Navier-Stokes equations

To fix notations, let Ω ⊂ R d be the fluid domain, where d is the space dimension, and ∂Ω its boundary. The strong form of the incompressible Navier Stokes equations reads:

ρ (∂ t v + v • ∇v) -∇ • σ = F ∇ • v = 0 ( 1
)
where t ∈ [0, T ] is the time, v(x, t) the velocity, p(x, t) the pressure and ρ the density.

F plays here an important role, taking into acocunt the forces of the membrane. Its expression will be detailed in section 3. The Cauchy stress tensor for a Newtonian fluid is given by:

σ = 2µ (v) -p I d , (2)
with I d the d-dimensional identity tensor and µ the dynamic viscosity.

The weak form of problem (1) combined with (2) is obtained by multiplication of a test function and integration by parts and reads, under the assumption of homogeneous Dirichlet boundary conditions:

     Find (v, p) ∈ V × Q such that: ρ [(∂ t v, w) + (v • ∇v, w)] + (2µ (v) : (w)) -(p, ∇ • w) = (f , w) , ∀w ∈ V (∇ • v, q) = 0, ∀q ∈ Q.
(3) where ρ and µ are the density and the dynamic viscosity, respectively. Based on a mesh K h of Ω made of N el elements K, the functional spaces for the velocity V and for the pressure Q are approximated by the finite dimensional spaces V h and Q h respectively. It is well known that the stability of this formulation requires an appropriate choice of the finite element spaces V h and Q h , that must to fulfil a compatibility condition [START_REF] Ern | Theory and practice of finite elements[END_REF]. Accordingly, the standard Galerkin method with the P1/P1 element (i.e. the same piecewise linear space for V h and Q h ) is not stable. Moreover, convection-dominant problems lead to numerical oscillations that pollute the solution. As menstioned previously, we use a Variational MultiScale method [START_REF] Hughes | Multiscale phenomena: Green's functions, the dirichlet-toneumann formulation, subgrid scale models, bubbles and the origins of stabilized methods[END_REF] which circumvents both problems through a Petrov-Galerkin approach. The basic idea is to consider that the unknowns can be split into two components, a coarse one and a fine one, corresponding to different scales or levels of resolution. First, we solve the fine scales in an approximate manner and then we replace their effect into the large-scale equation. We present the final obtained variational formulation of the method, and the reader is referred to [START_REF] Hachem | Stabilized finite element method for incompressible flows with high reynolds number[END_REF] for extensive details:

         ρ (∂ t v h , w h ) Ω + (ρv h • ∇v h , w h ) Ω -K∈T h (τ 1 R M , ρv h ∇w h ) K + (2µε ε ε(v h ) : ε ε ε(w h )) Ω -(p h , ∇ • w h ) Ω + K∈T h (τ 2 R C , ∇ • w h ) K = (f , w h ) Ω , ∀w h ∈ V h,0 (∇ • v h , q h ) Ω -K∈T h (τ 1 R M , ∇q h ) K = 0, ∀q h ∈ Q h ( 4
) where (•, •) Ω represents the scalar product on the whole domain omega while (•, •) K is the scalar product on Element K. The quantities τ 1 and τ 2 are stabilization parameters, R M and R C are the momentum and the continuity residuals (see [START_REF] Hachem | Stabilized finite element method for incompressible flows with high reynolds number[END_REF] for details).

The Spalart-Allmaras turbulence model (SA)

The range of velocity of the airship is between 20m/s and 50m/s. Based on the length of the airship, the Reynolds number may reach 10 7 . To solve accurately such high Reynolds number flows, it requires an extensive number of nodes, in particular at the boundary layers. This is not affordable using the existing resources. Therefore, as is the case in many industrial applications, we refer to the use of the Reynolds-Averaged Navier-Stokes (RANS) equations. They are obtained by applying a time-averaging procedure to the Navier-Stokes equations, which gives rise to an additional stress term (the Reynolds stress tensor) and a turbulent eddy viscosity µ t taking into account the effect of turbulent fluctuations on the averaged flow. Different turbulent model to compute the eddy viscosity µ t exists in the literature. We choose for this work the one-equation Spalart-Allmaras turbulence model because it is well adapted for external aerodynamic flows [START_REF] Spalart | A one equation turbulence model for aerodinamic flows[END_REF]. It represents the evolution of the kinematic eddy viscosity ν by a non linear advection-diffusionreaction type of equation.

The coupling with the Navier-Stokes equations (4) will be through the velocity field from one side and the eddy viscosity from the other side.

A stabilized Finite Element discretization of the Spallart-Allmaras model and a simple linearisation method were proposed in [START_REF] Khurram | Multiscale finite element method applied to the spalart-allmaras turbulence model for 3d detachededdy simulation[END_REF]. Therefore, we follow the same idea, and we write the variational formulation combined with a backward Euler time discretization:

νn+1 -νn ∆t + v n+1 - c b2 σ ∇ν n+1 • ∇ν n+1 convection - 1 σ ∇ • (ν + νn+1 )∇ν n+1 diffusion -c b1 (1 -f n+1 t2 ) Sn+1 + c w1 f n+1 w - c b1 κ 2 f n+1 t2 νn+1 d 2 νn+1 reaction = 0, ( 5
)
where νn stands for the value of ν at discrete time t n . The eddy viscosity can then be obtained from µ t = ρνf v1 , with f v1 a damping function, S the turbulent production, d is the shortest distance to the wall, and all the remaining terms are the model specified coefficients (see [START_REF] Spalart | A one equation turbulence model for aerodinamic flows[END_REF] for details).

Finally by applying a simpler Picard-like linearization [START_REF] Khurram | Multiscale finite element method applied to the spalart-allmaras turbulence model for 3d detachededdy simulation[END_REF] and the Streamline Upwind Petrov-Galerkin (SUPG) method, the final weak form of equation ( 5) reads:

νn+1,i+1 -νn ∆t , ω h Ω + v n+1 - c b2 σ ∇ν n+1,i • ∇ν n+1,i+1 h , ω h Ω - 1 σ (ν + νi h )∇ν n+1,i+1 h , ∇ω h Ω - c b1 (1 -f n+1 t2 ) Sn+1 h + c w1 f n+1 w - c b1 κ 2 f n+1 t2 νn+1,i h d 2 νn+1,i+1 h , ω h Ω + K R(ν n+1,i ), τ n+1,i 3 v n+1 h - c b2 σ ∇ν n+1,i h • ∇ω h K = 0, ∀ω h ∈ W h . ( 6
)
where R(ν) is the finite element residual of [START_REF] Haas | Deformation of giant lipid bilayer vesicles in shear flow[END_REF]. The stabilization parameter τ 3 , is computed within each element as:

τ 3 = c 2 h α c K + c 1 h 2 K α d + α r -1 (7)
where α c , α d and α r are respectively the convection, diffusion and reaction coefficients in Equation ( 6), h K is the element size, α c K a characteristic norm of the convection term and c 1 = 4, c 2 = 2 for linear elements.

Eulerian framework using a Level set method

The level set method [START_REF] Sethian | Analysis of flame propagation[END_REF][START_REF] Sethian | Level set methods and fast marching methods[END_REF][START_REF] Osher | Level set methods and dynamic implicit surfaces[END_REF] defines a signed distance function φ as follows:

φ(X) =      -dist(X, Γ) if X ∈ Ω 1 0 if X ∈ Γ dist(X, Γ) if X ∈ Ω 2 (8)
To restrict and sharpen the interface, we modify, filter and replace the level-set function as follows:

φ(X) =      2E/π for φ > E 2E π sin π 2E φ for |φ| < E -2E/π for φ < -E (9)
where E stands for the truncation thickness as shown in 2. Here, the membrane is denoted by Γ and thus decomposes the whole domain into two sub-domains Ω 1 and Ω 2 such that Ω = Ω 1 ∪ Ω 2 . Recall also that as a signed distance function, φ has the property |∇φ| = 1.

H ε (φ) =        0, φ ≤ -ε, 1 2 1 + φ ε + sin( πφ ε ) π , -ε ≤ φ ≤ ε, 1, φ ≥ ε, (10)
δ ε (φ) =      0, φ ≤ -ε, 1 2ε (1 + cos( πφ ε )), -ε ≤ φ ≤ ε, 0, φ ≥, (11)
Where ε a numerical parameter that defines the thickness of the interface and taken a value founded in the literature as (ε = 1.5h ) with h the mesh size. The Heaviside function is used to determine material values at each point in the domain. For example, let's take the density ( ρ 1 , ρ 2 ) and the viscosity (µ 1 , µ 2 ) respectively for (Ω 1 , Ω 2 ) :

ρ = ρ 1 + (ρ 2 -ρ 1 )H ε (φ) (12)
µ = µ 1 + (µ 2 -µ 1 )H ε (φ) (13)
Various geometric quantities such as the unit normal vector and curvature can be easily determined as :

n = ∇φ |∇φ| (14)
κ = ∇.n = ∇. ∇φ |∇φ| (15)
The function δ ε is used to define quantities having a non 0 value only at the interface (for example interfacial forces). A function F which needs to be distributed on the interface can be distributed on all the domain Ω. Its action is restricted to the interface thanks to the function δ ε :

Γ F Ω F δ ε (16)
The evolution of the level set function under the incompressible velocity field u can be modeled by a standard advection equation :

∂φ ∂t + u.∇φ = 0 (17)
Finally, to ensure the property of the distance function (|∇φ| = 1) , we solve the following classical Hamilton-Jacobi equation:

∂φ ∂τ + s(φ)(|∇φ| -1) = 0 φ(τ = 0, x) = φ(t, x) (18)
where s represents the signed function.

It is important to remind that the choice of using a fully Eulerian framework is important in the context of the Stratobus project. Indeed, not only it gives a simple access to heat transfer through convection and conduction, but also to fluid-solid interaction through turbulent flows and aerodynamic forces. Therefore, the use of the level set function that separates each subdomain is determining in our case and needs to be extended to the use of membrane interfaces. Finally, the use of anisotorpic mesh adaptation plays an important role [START_REF] Mesri | Hierarchical adaptive multi-mesh partitioning algorithm on heterogeneous systems[END_REF][START_REF] Mesri | Parallel adaptive mesh refinement for capturing front displacements: Application to thermal eor processes[END_REF][START_REF] Mesri | Automatic coarsening of three dimensional anisotropic unstructured meshes for multigrid applications[END_REF][START_REF] Mesri | Gestion et contrôle des maillages non structurés anisotropes: applications en aérodynamique[END_REF][START_REF] Mesri | On optimal simplicial 3d meshes for minimizing the hessian-based errors[END_REF][START_REF] Dervieux | Continuous mesh adaptation models for cfd[END_REF], both to capture accuratly the interface, to refine near high gradients of the velocity field and to render accurate boundary layers [?]. We will not treat this part in this report.

Membrane model

Inspired from biomechanics applications, we studied how to implement the additional forces to deal with the interaction between a fluid and an immersed vesicle. In the particular case of vesicle, it is shown in [START_REF] Cottet | Approche eulérienne et méthodes level-set pour l'interaction fluide-structure[END_REF] that we need to treat two main proprieties:

• Bending energy : to bend the membrane, a bending energy has to be considered • Local inextensibility : the perimeter of the membrane should be the same all the time.

Bending Force

Starting from the energy that costs to bend a membrane, Helfrich and Canham [START_REF] Canham | The minimum energy of bending as a possible explanation of the biconcave shape of the human red blood cell[END_REF] introduced the following expression:

E c = Γ k b 2 κ 2 (19)
With k b the bending modulus of the membrane and κ the curvature of the interface. The functional derivative of the expression [START_REF] Hachem | Stabilized finite element method for incompressible flows with high reynolds number[END_REF] as taken in [START_REF] Maitre | Comparison between advectedfield and level-set methods in the study of vesicle dynamics[END_REF] leads to the following bending force:

F c = κ b ∇. -κ 2 2 ∇φ |∇φ| + 1 |∇φ| I d - ∇φ ∇φ |∇φ| 2 ∇ {|∇φ| κ} δ ε ∇φ (20)
Where P = I d -∇φ ∇φ |∇φ| is the orthogonal projector (I is the identity tensor) that can be also rewritten with the normal unit vector as : P = I -n n.

Inextensibility Force

To complete this particular situation for a vesicle membrane, an inextensibility force must be computed. Many models have been established either through a Lagrange multiplier as in [START_REF] Biben | Tumbling of vesicles under shear flow within an advected-field approach[END_REF][START_REF] Laadhari | On the equilibrium equation for a generalized biological membrane energy by using a shape optimization approach[END_REF] or a direct elastic force as in [START_REF] Cottet | A level set method for fluid-structure interactions with immersed surfaces[END_REF][START_REF] Milcent | Une approche eulérienne du couplage fluide-structure, analyse mathématique et applications en biomécanique[END_REF]. This force derives from an elastic energy. It has shown in [START_REF] Cottet | A level set method for fluid-structure interactions with immersed surfaces[END_REF] that the elastic energy depends on the gradient modulus of φ. This latter can record an important information of the membrane which is the stretching (on the variation of the surface area). Indeed, a mathematical proof has been given, shown that when the membrane is stretched, the fluid tends to pull in the perpendicular direction of the stretching. These leads to a variation of |∇φ|. Figure 3 taken from [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] can explain in a simple manner the principle.

Figure 3: Principle of the inextensibility by elastic force [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] Thus the elastic energy is defined as :

E el = Ω E(|∇φ|)δ ε (21)
Differentiating the above energy gives the expression of the elastic force

F el = ∇E (|∇φ|) -∇. E (|∇φ|) ∇φ |∇φ| ∇φ |∇φ| δ ε (22)
Where E(|∇φ|) stands for a constitutive law for the membrane. Note that E(1) = 0 means there is no initial stretching. Taken the most of the time as a linear law E = Λ (|∇φ| -1), it was shown that E = Λ max (|∇φ| -1) is an appropriate choice avoiding numerical oscillations. Λ represents the stiffness of the membrane that has to be taken quite large enough to enforce constant area.

Two important points should be mentioned at the end of this section. The first one is that the bending force can introduce numerical problems. Indeed, the level set φ need to be derived four times since we have the divergence of the gradient of the divergence of the normal, where the normal itself is written as n = ∇φ |∇φ| . To overcome this problem, a state of the art on different techniques have been presented in the next section and will form the perspectives of this initial work. The second point is that, since the stretching is recorded in φ, one needs to keep the information of the ∇φ. As explained previously, the reinitialization resets ∇φ to 1, the stretching information will be then lost. Therefore, we need to account for this information through the resolution of the following advection equation with a source term that uses e = |∇φ| before the reinitialization step:

∂ t e + u.∇e = -e(n ⊗ n) : D(u) (23)

Discretization

The total force localized on the membrane needs now to be transformed to a volume force. Therefore, as mentioned before, we refer to the use of a Dirac function.

Thus, the variational formulation of each force that are added and implemented in the Navier-Stokes equations reads:

F c = Ω κ b ∇. -κ 2 2 ∇φ |∇φ| + 1 |∇φ| I d - ∇φ ⊗ ∇φ |∇φ| 2 ∇ {|∇φ| κ} δ ε ∇φ.v (24)
F el = Ω ∇E (|∇φ|) -∇. E (|∇φ|) ∇φ |∇φ| ∇φ |∇φ| δ ε • v (25)
The total force F can be written as

F = F c + F el .
4 Numerical experiments

Flow past a 3D airship

In the first numerical test case, the aim is to assess the capability of our numerical method to simulate the turbulent flow past a complex 3D geometry, namely the Stratobus. We seek also to evaluate the drag and lift forces using an inlet velocity of 25m/s, yielding a span-based Reynolds number of Re = 10 7 . The model is placed in a computational domain of length 50m and width 250m × 250m. Flat velocity and turbulent viscosity (ν = 3ν) profiles are prescribed at the inlet boundary, a pressure condition is imposed at the outlet, and slip conditions are used on the boundaries parallel to the flow. At the airship wall, no-slip boundary conditions for the velocity as well as homogeneous Dirichlet conditions for the turbulent viscosity ν are specified. Again, time marching is performed until the steady-state is reached. The non-dimensional time step is set to ∆t = 10 -3 . Figure 4 gives a general view of the computational domain.

Recall that the airship is simulated at zero angle of attack. The mesh is preadapted at the interface and consists of 1283925 elements and 228210 nodes. The expected pressure distribution is depicted also in Figure 4. The evolution in time of the velocity field until it reaches a steady-state is shown in Figure 5. We can clearly notice the flow detachement and the wake past the airship. Both the nacelle and the rear airfoils play also a role on the overall nature of the flow. Results obtained for the drag and the lift are presented in Figures 6 and7. Qualitatively, the result for the drag is in the expected range obtained in previous setup using different codes at Thales Alenia Space. This first framework is satisfying to proceed further experiments such as different angle of attacks for stability, aerothermal problem and aeroelasticity problem. Moreover, adaptive mesh refinement in 3D is needed to guarantee an accurate resolution of the boundary layer. Therefore, the work of [START_REF] Billon | Anisotropic boundary layer mesh generation for immersed complex geometries[END_REF] on anisotropic meshing for boundary layers will be used to pursue this analysis.

Fluid-membrane test case

To test the first implementation of the fluid-membrane model, we will study the test case proposed recently in [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] on the equilibrium shape of a membrane in a fluid at rest. Other PhD works have been solely concentrated to solve this problem [START_REF] Kaoui | Modélisation de vésicules en géométrie étendue et dans des systemes micro-fluidiques[END_REF][START_REF] Kaoui | Two-dimensional vesicle dynamics under shear flow: Effect of confinement[END_REF] using a Lattice Boltzmann method and the Boundary Integral Method.

The membrane, is placed in a fluid at rest in a shape which does not minimize the Helfrich energy. The bending force, expressed above with the geometric parameter of the membrane, causes the motion of the fluid until it reaches its equilibrium shape.

The final shape depends on a dimensionless parameter called the reduced area η. The latter is the ratio between the area of the vesicle and the area of a disk having the same perimeter :

η = 4πA p 2 er (26)
A is the area of the vesicle and p er its perimeter. This parameter allows us to determine how much the membrane can be deformed.

We show first in Figures 8 to 10 the level set function for the membrane, the obtained Dirac function and we compare it to the reference solution obtained by [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] at different time steps. In Figures 11 to 13 we highlight also the obtained bending and elastic forces at different time steps. We can clearly notice the concentration of these values at the interface, that once are inserted in the Navier-Stokes equations, will steer the velocity field to bend or stretch the membrane, which in return will advect the level set function. Moreover, we can notice the appearance of small perturbations at the last step which is due to the repetition of the projection operations. We discuss this matter in Section 5. Despite the numerical issues related to the recovery of high order derivatives, the results remain in good agreement highlighting the potential of the implemented method. Recall also that the numerical techniques used in this work are very different from those used to obtain the reference solution. Table 1 summarizes some of them.

Reference work [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] Present The following step will be naturally to test it in 3D using the hull of the airship while recovering the physical parameters of the envelope from Thales Alenia Space. Indeed, the envelope of the Stratobus may present similar behavior in bending but not in inexensibility. However, the implementation of additional forces in Navier-Stokes and the proposed global algorithm will not change. Moreover, the use of the new implemented unified compressible-incompressible solver in Cimlib (see [START_REF] Hachem | Unified adaptive variational multiscale method for two phase compressible-incompressible flows[END_REF]) will be crucial for the following simulation.

High order derivative by smooth projections

Different strategies are developed to be able to get a value of the derivatives of the curvature. We used in our case the L2 double projection. This is already included in our model and should work satisfactorily. However, for higher derivative, repeating this operation will induce small oscillations at the interface that increases in amplitude and lead to important oscillations (as seen in the curvature of figure 17(a)) making the derived field impossible to derive once again. In [START_REF] Laadhari | Modelisation numérique de la dynamique des globules rouges par la méthode des fonctions de niveau[END_REF], the authors worked on this subject and proposed a new high order derivative by smooth projection. The idea of the method is to add artificial diffusion to the projection to minimize the oscillations happening when deriving a variable discretized on a low order polynomial set. It adds a small term proportional to ∆g which smooths the oscillations and makes the obtained derivative possible to derive as shown in Figure

with ε 1 a sufficiently small parameter. To be precise, ∇gn is the classical product of the matrix ∇g and the vector n, thus it is a vector.

Figure 17: Comparaison between the previous projection and the new one [START_REF] Doyeux | Modelisation et simulation de systemes multi-fluides[END_REF] Again, this step is crucial to simulate accurate fluid-membrane interaction using a level set approach and will be the first subject of further investigations.

Conclusion

We have presented a full Eulerian approach to deal with the aerodynamic performance and stability of a new designed airship. It consists first on setting the needed fluid solvers (Navier-Stokes equations coupled to a Spallart almaras turbulent model), then on a geometric representation through a level set method that separates each phase: external air, membrane and internal gaz. Finally, we extended this framework to embed a fluid-membrane model through interfacial forces. This model consists on implementing bending and inextensibility forces and adding them to the Navier-sotek equations. The framework was tested first in 3D to analyze the flow past a fixed airship and compute the aerodynamic forces. Then a fluid-membrane benchmark was chosen to validate the implementation. This work allows us to highlight several numerical challenges: first, the implementation of a high order derivative using smooth projection is needed to ensure free-oscillation forces, then the use of an unified compressible-incompressible solver to take into account the internal gaz of the the airship, finally, the analysis of the envelop proposed by Thales Alenia Space to deduce the physical parameters for our fluid-membrane model.

Figure 1 :

 1 Figure 1: The airship Stratobus

Figure 2 :

 2 Figure 2: Sign of φ

Figure 4 :

 4 Figure 4: The immersed airship inside a wind channel (left) and the variation of the pressure field (right)

Figure 5 :

 5 Figure 5: Evolution in time for the velocity field

Figure 6 :

 6 Figure 6: The evolution of the drag coefficient

Figure 7 :

 7 Figure 7: The evolution of the lift coefficient

Figure 8 :

 8 Figure 8: Level set function, Dirac function and the reference solution for η = 1

Figure 9 : 9 Figure 10 :

 9910 Figure 9: Level set function, Dirac function and the reference solution for η = 0.9

Figure 11 :

 11 Figure 11: The bending and the elastic forces for η = 1

Figure 12 : 9 Figure 13 :

 12913 Figure 12: The bending and the elastic forces for η = 0.9

Figure 14 : 1 Figure 15 :

 14115 Figure 14: The pressure, velocity and the adapted mesh obtained for η = 1

Figure 16 :

 16 Figure 16: The pressure, velocity and the adapted mesh obtained for η = 0.77

  17(b). The continuous formulation of such a smoothed projection, after integrating by part is the following, for a given u ∈ H1 (Ω), find g ∈ [H 1 (Ω)] d ∩ [C 0 ] d so that ∀v ∈ [H 1 (Ω)]

Table 1 :

 1 Comparative table

	work