Bertolt Brecht and Walter Benjamin seem to have something quite different in mind in their use of the term montage in the above quotes. In the manifesto-like essay written in response to György Lukács as part of the 'Expressionism debate', carries out in the late thirties over the pages of Das Wort, Brecht lists montage alongside the inner monologue, as a narrative technique one should utilise in the composition of realistic works of art. 3 Benjamin, in contrast, pronounces montage as the literary method used for composing the Passagen-Werk. 4 He seems * This essay was developed as part of Material und Begriff. Arbeitsverfahren und theoretische Beziehungen Walter Benjamins, hosted by the Zentrum für Literatur-und Kulturforschung, Berlin. I would like to thank the organisers and participants for their illuminating comments and support. The key essay Lukács contributed to the debate was 'Es geht um des Realismus', published in Das Wort, Literarische Monatsschrift, Redaktion: Bertolt Brecht, Lion Feuchtwanger, Willi Bredel, Moskau: Jourgaz-Verlag, Heft 6, Juni 1938, pp. 112-138. For some general background on the debate see the introduction to 'Realism and Formalism' in Brecht, Bertolt, Tom Kuhn, Steve Giles, Laura J. R. Bradley. Brecht on Art and Politics. Brecht's Plays, Poetry, and Prose. London: Methuen, 2003, pp.205-212. 4 See Das Passagen-Werk GS. Bd. 5, pp.45-1060. The texts assembled in the Gessamelte Werke under the title Das Passagen-Werk were first published in 1982. They comprise of a study revolving around the Parisian 19 th century shopping Arcades Benjamin had worked on intermittently between 1927 and his death in 1940. The main section of the text is divided into alphabetically ordered 'convolutes', each loosely centred around a theme. The material consist in large part of quotations, and much of the critical literature written since its publication has engaged with the question of the completeness of the work; some, like Tiedemann, suggested the assembled materials are fragments of an unfinished work. Others whose view I share, such as Eiland and McLaughlin, suggest 'the research project had become an end to itself', in which Benjamin further extended his abundant use of citation and experimentation with short form already present in Ursprung des deutschen to be describing montage as a 'transparent' technique in which the author must merely display existing material, without its further transformation. This is the manner in which Adorno understood Benjamin's montage, describing it as simply denoting 'ohne Anführungszeichen zu zitieren'. 5 Adorno further explains that 'Benjamins Absicht war es, auf alle offenbare Auslegung zu verzichten und die Bedeutungen einzig durch schockhafte Montage des Materials hervortreten zu lassen'. 6 Benjamin intended meaning to emerge out of the assembly of quotations without mediating commentary, Adorno argues. The possibility of constructing a philosophical argument by merely juxtaposing material, without its conceptualisation and interpretation, is questionable, he adds. 7 Adorno critique of Benjamin's concept of montage relates to what he viewed as Brecht's influence on Benjamin's writing. In the following, I will interrogate the extent and manners in which Brecht's writing had in fact informed Benjamin's concept of montage. It will be argued that, contrarily to what has been suggested in the past, Benjamin had not appropriated the concept of montage from Brecht. 8 Furthermore, while in Brecht's work the role of montage as a theoretical concept is limited, it is a key philosophical concept in Benjamin's writing. Devoting attention to this seemingly marginal term in their writing, I will suggest, may shed new light on the intricate and widely studied intellectual relationship between Benjamin Brecht.

Benjamin's describes montage, in his seminal essay 'Der Autor als Produzent', as a two-staged process. 9 An interruption of an existing state of affairs, which enacts an arrest, is followed by an experimental reordering that transforms the function and value of the work as a whole. Teidemann and Buck-Morss both defended the function of montage in Benjamin's writing from Adorno's critique by arguing that Benjamin's viewed montage as including not quotations alone but mediating commentary as well. 10 I argue conversely that the two stages of Trauerspiels and Einbahnstraße. See Teidemann, Rolf. GS. Bd. 5, pp. 9-41.'Einleitung des Herausgebers ', and 'Translator's Forward' in Benjamin, Walter, Eiland, Howard, McLaughlin, Kevin and Rolf Tiedemann. The Arcades Project. Cambridge, Mass: Belknap Press, 1999, pp. ix-xiv, esp. As Buck-Morss writes: 'Benjamin's commentary, in which those facts were embedded, provided the rivets that allowed the fragments to cohere'. Despite some differences of perspective, I am indebted to her illuminating work on Benjamin's montage, and specifically her discerning both constructive and destructive dimensions in montage. See Buck-Morss, Susan. The Dialectics of Seeing. 1 st ed., London, MIT press, 1999, pp. 74-77, and Teidemann, Rolf. Ed. Bericht GS, Bd.5, p. 1073. the procedure of montage combined bring about an interpretative process, and this procedure, as Benjamin envisioned it, itself adopts the structure of commentary. 11 No additional explanation is necessary since the juxtaposition and rearrangement of elements -quotations in Passagen-Werk -is constructive of new meaning, much like meaning created by the juxtaposition of adjacent shots in a film. 12 The manner in which Adorno describes philosophy in 'Die Aktualität der Philosophie', which Benjamin (miss)quotes in a letter to Adorno from July 1931, is therefore applicable to Benjamin's concept of montage: 'Aufgabe der philosophie ist es nicht, verborgene und vorhandene Intentionen der Wirklichkeit zu erforschen, sondern die intentionlose Wirklichkeit zu deuten, indem sie kraft der konstruktion von Figuren, von Bildern aus den isolierten Elementen der Wirklichkeit die Fragen aufhebt, deren prägnante Fassung Aufgabe der Wissenschaft ist'. Adorno, Theodor W. Gesammelte Schriften in 20 Bänden -Band 1: Philosophische Frühschriften. Hrsg. von Rolf Tiedemann, Frankfurt am Main, Suhrkamp Verlag, 1973 p. 335. For Benjamin's letter, in which he replaces 'Aufgabe der philosophie' with 'Aufgabe der Wissenschaft' see Adorno, Theodor W., Benjamin, Walter, Lonitz. H. Briefe und Briefwechsel -Band 1, Briefwechsel 1928-1940, Frankfurt am Main, Suhrkamp Verlag, Zweite Auflage, 1995, letter from 17.7.1931, p. 18. 13 In the 'Erkenntniskritische Vorrede' to Ursprung des deutschen Trauerspiels The philosophical idea is described by Benjamin as produced by a kind of montage of extreme elements. See Ursprung des deutschen Trauerspiels, Benjamin, Walter, Rolf Tiedemann, Hermann Schweppenhäuser, Theodor W. Adorno, and Gershom Scholem. Gesammelte Schriften. Bd. 1 Teil 3: Abhandlungen [...] In 'Reduktion und Montage', Detlev Schöttker identifies montage in Benjamin's writing with construction, arguing for the link between Benjamin's interest in constructivist movements and his development of the concept of montage. This leads him to wonder why on one hand Benjamin positions 'construction' against 'epic theatre', while on the other using epic theatre as an example for the constructive procedure of montage. Schöttker explains this by suggesting that over the years Brecht appropriated the idea of historical construction from Benjamin, employing it in his own writing and, therefore, Benjamin later references to Brecht's work link epic theatre together with montage. While I agree there is a link between montage and constructivism in Benjamin's writing, and find Schöttker's observation of shifts over time in Brecht's approach to construction convincing, the apparent contradiction is avoided if one views montage as a complex, evolving concept in Benjamin's writing that includes moments of both construction and interruption. Global Benjamin: Internationaler Walter- Benjamin-Kongress 1992, Wilhelm Fink Verlag, München, 1999, bd.2, pp. 772-3. to the political function of the play as a whole. Benjamin's central argument in 'Der Autor' pertains to the role of the artwork within communist politics. He suggests that in order for an individual work to contribute to the political class struggle, revolutionising society's relations of production, it must perform a refunctioning [Umfunktionierung] of its apparatus of production. Writing about so-called 'revolutionary' themes in a manner that is not transformative of the text's means of production does not make for political literature, argues Benjamin against the New Objectivity movement. In other words, in order for an individual work to play a role within the political class struggle, revolutionising society's relations of production, it must alter its own manner of production. One method for achieving such an Umfunktionierung of the apparatus is by using the procedure of montage. This transformation consists of a shift in the relations between the artwork and reality. Unlike dramatic theatre, See GS Bd.2, p. 698. In 'Was ist das epische Theater? (1) it reads as following: 'Das primitivste Beispiel: eine Familienszene. Plötzlich tritt da ein Fremder ein. Die Frau war grade im Begriff, ein Kopfkissen zu ballen, um es nach der Tochter zu schleudern; der Vater im Begriff, das Fenster zu öffnen, um eine Schupo zu holen. In diesem Augenblick erscheint in der Tür der Fremde'; See GS Bd.2, p.522. of action reveals a formerly hidden aspect of the state of affairs between the family members. 20 Furthermore, in both versions of 'Was ist das epische Theater? Benjamin likens epic theatre to film; 'Das epische Theater rückt, den Bildern des Filmstreifens vergleichbar, in Stößen vor', he writes in the 1939 version. Since Benjamin describes Brecht's plays as formally resembling film and enacting the procedure of montage, the question begs whether the procedure in itself, as described by Benjamin, may be found within Brecht's theory and plays, and has merely been 'remounted' by Benjamin into his own work.

Ein Mensch wie ein Auto ummontiert

In the years preceding his writing 'Der Autor' in 1934, Benjamin read and responded enthusiastically to Brecht's Versuche 1-3 (1930), an edition containing plays and essays. 21 The term montage appears only once in this volume, in Brecht's 'Anmerkungen zur Oper Aufstieg und Fall der Stadt Mahagonny'. 22 First published in 1930 in the journal Musik und Gesellschaft, under the title 'Zur Sociologie der Oper -Anmerkungen zu Mahagonny', it was republished the same year in Versuche 2, and repeatedly revised and republished in successive years. 23 'Montage' is listed in one of the subsequently most quoted Brechtian texts: a table of two columns, the first entitled 'Dramatische Form des Theaters' and the second 'Epische Form des Theaters', opposite Wachstum ('growth', or 'progression') in the dramatic theatre column.

It should not, however be taken as the negation of 'Wachstum'; Brecht explains in a footnote that the terms in the table do not represent antitheses but rather 'shifts of accent'

[Akzentverschiebungen].24 Although Brecht does not comment on the table, the meaning of montage in this context may be deduced from the terms appearing above and below it in the table: 'Jede Szene für sich' opposite 'Eine Szene für die andere', 'in Kurven' opposite 20 'Der Autor als Produzent' GS Bd.2, p. 698. 21 See Benjamin's letter to Scholem from the 20 th July, 1931: '..these essays are the first -to be precise, of the poetic or literary essays -that I champion as a critic without (public) reservations. In another letter to Scholem from 17th April '31 he writes specifically of the Mahagonny Anmerkungen, describing it as 'a highly significant essay about opera'. The Correspondences of Walter Benjamin 1910-1940 ed. G. Scholem and T. Adornon, trans. Manfred R. Jacobson and Evelyn M. Jacobson, Chicago IL, University of Chicago press, 1994 p. 380, 377. 22 'Anmerkungen zur Oper Aufstieg und Fall der Stadt Mahagonny' Werke, Große kommentierte, Berliner und Frankfurter Ausgabe. in 30 Bänden (33 Teilbänden). Band 24: Schriften 4. Texte zu Stücken. Aufbau-Verlag Berlin und Weimar, 1991, pp.78-9. 23 For a documentation of the changes see Werke, Große kommentierte, Berliner und Frankfurter Ausgabe. in 30 Bänden (33 Teilbänden). Band 24: Schriften 4. Texte zu Stücken. Aufbau-Verlag Berlin und Weimar, 1991, pp. 476-78. in 'Der Autor', a term that is marginal at this stage within Brecht's theory, and defines it as epic theatre's primary artistic method; the technique par excellence for producing political works of art. 29 Further, in the Mahagonny Anmerkungen Brecht calls, as does Benjamin in 'Der Autor', for the transformation of the apparatus of the work of art, claiming the social function of artistic institutions must be altered from that of entertainment to that of education. 30 Yet Brecht does not suggest, as does Benjamin, that a transformation of the means of production may lead to a transformation of the social function of the artwork, or transcend the form-content distinction. On the contrary, Brecht argues that merely 'technologising' the form of opera is not enough. He criticises 'modish' avant-garde attempts to update opera and suggests, rather, that 'Wirkliche Neuerungen greifen die Basis an' -truly innovative opera must attack the 'base', rather than enacting superficial formal alteration. 31 The crux of Benjamin's argument, which brings together the method of production of the work and its revolutionary value as exemplified in the procedure of montage, thus differs from Brecht's position in the Mahagonny Anmerkungen. It is not until the late thirties, as part of the 'Expressionism Debate', that Brecht elaborates montage as a literary concept, utilising it to designate a disruptive technique that challenges the harmonious 'Bourgeoisie' structure of the text. 32 Benjamin's use of the term montage to denote an interruptive procedure in 'Der Autor' hence anticipates Brecht's comparable use of the term.

Krise und Kritik

In Konvolut N of the Passagen-Werk Benjamin describes montage as a constructive principle:

Ein zentrales Problem des historischen Materialismus, das endlich gesehen werden sollte: Ob das marxistische Verständnis der Geschichte unbedingt mit ihrer Anschaulichkeit erkauft werden muß? Oder: auf welchem Wege 29 'Montage' remains undeveloped as a theoretical term by Brecht at this stage despite his engagement with film and cinematic montage, which begun when he created Mysterien Eines Frisiersalons (Kupro-Film, 1923), and continued in the 30's with the production of Kuhle Wampe oder: Wem gehört die Welt? (Prometheus Film, 1932). Montage is defined quite differently here than in 'Der Autor', as a principle that can bring together 'graphicability' [Anschaulichkeit] on one hand, and the historical materialist approach to history on the other. Its method is described as that of construction using parts that are constructions, or assemblies, themselves [Konfektionierten]. That is, this construction of history is contingent upon a previous shattering of a whole (or a unified account of history) whose fragments are then reassembled. As demonstrated, montage as procedure includes a process of experimental arrangement [Versuchanordnung] following an interruption. The dialectic between the two apparently antithetic elements 'interruption' and 'arrangement', is comparable to that between 'destruction'[Destruktion] and construction in Benjamin's writing. 34 Yet when Benjamin describes montage as procedure, the interruption preconditions the arrangement of the interrupted components. Conversely, when he describes it as a principle, like in the above quote, he focuses on the constructive process while interruption, or suspension lie both in the past and the future to come. 35 This dissimilarity attests to a distinction between the function of montage in Benjamin's writing as procedure and as principle. The former interrupts, estranges, and rearranges; the latter constructs aggregates from disparate parts, that will one day be shattered once again into their bear elements. A further difference between the interruption-experimental arrangement binary on one hand, and destruction-construction on the other, is that the former implies, as demonstrated, the interruption of an existing state-of affairs, and the arrangement of its elements. In destruction, as described in the Passagen-Werk, the ancient state of affairs is entirely demolished. The arrest following destruction may be 33 'Passagen', GS Bd. 5 p.575. 34 See for example 'Für den materialistischen Historiker ist es wichtig, die Konstruktion eines historischen Sachverhalts aufs strengste von dem zu unterscheiden, was man gewöhnlich seine »Rekonstruktion« nennt. Die »Rekonstruktion« in der Einfühlung ist einschichtig. Die »Konstruktion« setzt die »Destruktion« voraus. ' Das Passagen-Werk, GS Bd.5, [N7,6] , p. 587.

35

See for example Benjamin's discussions of Messianic interruption, described as a 'weak Messianic force': '..das vor uns war, eine schwache messianische Kraft mitgegeben, an welche die Vergangenheit Anspruch hat' ''Über den Begriff der Gschichte' GS Bd. 1, p. 694. described as a full stop rather than a pause, and therefore construction starts anew, from tabula rasa. 36 Crisis and Critique [Krise und Kritik], the name selected for the journal Brecht and Benjamin planned to bring out together, alongside Bernard von Brentano, Herbert Ihring and others, echoes a similar dialectic between interruptive and constructive elements. 37 Here too, significantly, the moment of crisis precedes the act of critique. It is not the work of art in itself, but the crisis of the work that precondition the possibility of its critique. The title of the journal which would have been, had it materialised, Benjamin and Brecht's sole joint project, makes manifest the link between the literary crisis and the social and political crisis Benjamin and Brecht were living through in the 30's, and their attempt to critically react to this crisis. Yet 'crisis' was also used by the journal's conceivers to designate a positive, productive shock or interruption. According to a transcription of one of the planning sessions for 'Krise und Kritik', Brecht described Joyce and Döblin's writing as representing 'Versuche, aus der krise herauszukommen, sie sind aber, für sich betrachtet, auch noch selber Krise. 38 This implies the extreme situation of crisis may only be addressed through crisis; social crisis demands a complementary productive crisis in works of art. In the blueprint of their joint work, the manner in which Brecht's conceiving of crisis as productive shaped Benjamin's thinking is most visible. Here I agree with Noys, who describes how for Benjamin, Brecht's 'destructive character 'makes room' for a new form of production'. 39 It is not my intention to suggest that montage as principle and as procedure are strictly separate within Benjamin's thought, or that he consistently outlines the differences between them. And yet, highlighting the distinctions between these two aspects or functions of montage allows us to discern that while Brecht's theory and plays were significant for Benjamin in shaping his interruptive procedure of montage, they were less so in shaping montage as a philosophical principle of construction in the Passagen-Werk.

Conclusion

In 'Krisis Des Romans: Zu Döblins "Berlin Alexanderplatz"', published 1930, concomitantly with the planning of Krise und Kritik, Benjamin describes the governing stylistic principle [Stilprinzip] of Döblin's novel as montage; 'Die Montage sprengt den "Roman", sprengt ihn im Aufbau wie auch stilistisch'. 40 Benjamin argues montage is the reaction, by means of an interruptive style-principle, to the crisis of the novel that was caused by its being superseded by the epic. The crisis instigated by montage interrupts the traditional boundaries of the novel, experimentally reordering material of daily life ('Die Bibelverse, Statistiken, Schlagertexte'). 41 The author's interpretative voice is unnecessary in Döblin's novel, writes Benjamin, since the montage of quotidian life material speaks for itself. As in 'Der Autor' and the essays on epic theatre, Döblin's montage is associated with the epic form, which Benjamin interrogates closely in 'Der Erzähler. Betrachtungen zum Werk Nikolai Lesskows'. 42 Therein, he designates chronicle and history as two types of epic form. While the historian explains the happenings with which he engages, the chronicler simply displays them, without interpretation, as does Döblin in Berlin Alexanderplatz. Montage, as a literary and theatrical procedure or styleprinciple that belongs to epic form, may therefore be understood as one that merely exhibits the material that is interrupted and arranged, without adding explanation, allowing the juxtaposition between elements to perform an interpretative act. Montage as a philosophichistorical principle, on the other hand, includes interpretation, 'die es nicht mit einer genauen Verkettung von bestimmen Ereignissen, sondern mit der Art ihrer Einbettung in den großen unerforschlichen Weltlauf zu tun hat'. 43 In his critique of Benjamin's montage, Adorno conflated procedure and principle, understanding montage as the mere assembly of elements lacking additional interpretation. Adorno's critique of Benjamin's concept of montage is part and parcel of his more general criticism of Brecht's influence over the Passagen-Werk, from 40 'Krisis Des Romans: Zu Döblins "Berlin Alexanderplatz"'GS Bd.3, p. 232. 41 'Krisis Des Romans ',GS vol.3, p.233. 42 Benjamin, Walter, 'Der Erzähler. Betrachtungen zum Werk Nikolai Lesskows', Gesammelte Schriften, Frankfurt am Main, 1977, Bd. 2, pp. 438-465. I would like to thank Stephan Pabst for pointing out the relevance of this essay to the debate over the role of montage in Benjamin's writing. which he repeatedly warned Benjamin. 44 The case of montage serves as an example for Adorno's long-lasting impact on the reception of Benjamin and Brecht's intellectual exchange.

Adorno's overestimation of Brecht's influence on some aspects of Benjamin's writing resulted in blind spots that have been consolidated and remained un-interrogated despite the vast amount of scholarly work written on the topic. Drawing attention to the complex range of meanings and functions of montage in Benjamin's writing allows us to better perceive the manners in which Brecht indeed had shaped Benjamin's thought, and to trace the limits of the former's so called 'negative influence'.

44

See for example Adorno, Theodor W., Benjamin, Walter, Lonitz.H. Briefe und Briefwechsel, letter from 20.5.1935, p.112, and letter from 2-4, 5.8.1935, p.143.

  der Meine der Unfehlbarkeit die alleinseligmachende Art, ein Zimmer zu beschrieben, exkommuniziert nicht die Montage, setzt nicht den innern Monolog auf den Index! 1 Methode dieser Arbeit: literarische Montage. Ich habe nichts zu sagen. Nur zu zeigen. 2

1

  Brecht, Bertolt. ''Praktische zur Expressionismusdebatte', Gessamelte Werke in acht Bänden, Band 8, Schriften 2, Zur Literature und Kunst. Frankfurt am Main, Suhrkamp Verlag, 1967, p. 292. 2 Benjamin, Walter. 'Passagen', Gesammelte Schriften. Unter Mitwirkung von Theodor W. Adorno und Gershom Scholem hrsg. von Rolf Tiedemann und Hermann Schweppenhäuser, Bd. 5 [N1a, 8], p. 574.

  3

  Sparked by Adorno, the debate over the interpretative potential of montage bears implications regarding the status of the Passagen-Werk, as a work composed largely of quotations, within Benjamin's writing. Can a mere assembly of quotations, or materials, function as a philosophical work? In other words, what sort of operation may transform materials into concepts? Montage is one of Benjamin's responses to this question. The term appears repeatedly in the Passagen-Werk as well as in several other texts, at times, as above, used by Benjamin to describe the method of his own work. Although not named in these works, montage is present as both method and concept in Ursprung des deutschen Trauerspiels and Einbahnstraße. 13 Described as an artistic procedure [Verfahren] in 'Der Autor als Produzent', montage functions as a philosophical principle [Prinzip] in Konvolut N of the Passagen-Werk and 'Über den Begriff der Geschichte'. 14 The term thus oscillates in Benjamin's different works, between two apparently oppositional meanings. On one hand, the procedure of montage [das Verfahren der Montage] in 'Der Autor als Produzent' focuses on montage as a theatrical method which interrupts action. On the other, the principle 11 See GS, Bd. 5 p. 575 [N2, 6].

  12

  of montage[das Prinzip der Montage] in Das Passagen-Werk, describes montage as a philosophical principle of construction[Konstruktion].15 Both as procedure and as principle, montage may be defined as a dual-staged process including either interruption then arrangement, or destruction and construction. And yet, there is a shift of focus in Benjamin's different texts; in his essays discussing Brecht's epic theatre interruption is more dominant, while in the Passagen-Werk montage is conceived of primarily as a principle of construction.1. Montage as ProcedureIn 'Der Autor als Produzent', Benjamin describes the procedure of montage as one which Brecht borrowed from other art forms and incorporated in his epic theatre: Hier nimmt das epische Theater also -mit dem Prizip der Unterbrechung nämlich -wie Sie wohl sehen, ein Verfahren auf, das Ihnen in den lezten Jahren aus Film und Rundfunk, Presse und Photographie geläufig ist. Ich spreche vom Verfahren der Montage: das Montierte unterbricht ja den Zusammenhang, in welchen es montiert ist. Daß aber dieses Verfaren hier sein besonderes, ja hier vielleicht sein vollendetes Recht hat.' 16 A foreign element is mounted, or installed, in the procedure of montage into an assembly or context that make up an artwork, thereby disrupting the interrelations of its elements. Montage consists, therefore, of an interruption of relations. The songs interjecting in mid-action in Brecht's plays, for example, function as such disruptive elements. Benjamin describes Brecht's use of the procedure of montage as interruptive, in its creation of breaks in action, yet claims at the same time that it has a complete, or perfect right [vollendetes Recht]. This 'right' relates 15

  which produces a mimetic illusion based upon reality, epic theatre organises elements of reality itself in experimental arrangements[Versuchsanordnung]. The procedure of montage therefore first disrupts then arranges: the interruption of the former order brings about a new one through its 'organising function' [organisierende Funktion]. The reconfiguration of relations between elements within the artwork transforms the value of the artwork as a whole. Thus while the action within an epic play is interrupted, the play gains higher merit, as an artwork, than plays in which the action on stage creates an illusion of continuity.Benjamin describes two forms of relation-shifting. The first is between 'elements of reality' [Elemente des Wirklichen] within Brecht's plays, which are reordered in an experimental rearrangement. The second, between diverse artistic media used to compose an artwork, such as image and writing. He thus writes, for example, that photomontage refunctions the apparatus of photography through the use of captions: 'Was wir vom Photographen zu verlangen haben, das ist die Fähigkeit, seiner Aufnahme diejenige Beschriftung zu geben, die sie dem modischen Verschleiß entreißt und ihr den revolutionären Gebrauchswert verleiht'. 17 Montage as an interruptive procedure therefore transcends the form-content distinction through its altering, at the same time, the artwork's means of production and its political value. Diverging from the prevalent meaning of the term montage -which denotes assembly or mechanical construction -Benjamin's description of montage in 'Der Autor' focuses on the interruptive moment which enacts a break, or arrest, followed by a shifting of the relations between both elements within the work of art and elements composing the work of art. The reordering is an Umfunktionierung transformative of the function and value of the work as a whole.Although Benjamin links the Umfunktionierung of the apparatus to technological innovation, this does not necessarily imply the use of new media in 'Der Autor'. Benjamin is not suggesting revolutionary art as contingent upon the development of new technologies, although film will emerge as a privileged art-form in the Artwork essay. Rather, he suggests political art as one in which an interruption shifts and reconfigures the relations within the artwork. Technical progress as a foundation for political progress, as defined in this essay, must not, therefore, be confused with Benjamin's critique of historical progress in texts such as 'Über den Begriff der Geschichte'. Benjamin directly discusses Brecht's epic theatre in two versions of the essay 'Was ist das epische Theater?', the first written in 1931 and first published in 1966, and the second published anonymously in 1939 in Maß und Wert. 18 Therein, Benjamin describes the interruptive procedure that is designated in 'Der Autor' as montage, although he does not name it as such. He uses the self-same example he gives in 'Der Autor' for the procedure of montage; which reads as following: An einem Beispiel will ich Ihnen zeigen, wie Brechts Auffindung und Gestaltung des Gestischen nichts als eine Zurückverwandlung der in Funk und Film entscheidenden Methoden der Montage aus einem oft nur modischen Verfahren in ein menschliches Geschehen bedeutet. -Stellen Sie sich eine Familienszene vor: Die Frau ist gerade im Begriffe, ein Bronze zu ergreifen, um sie nach der Tochter zu schleudern; der Vater im Begriff, das Fenster zu öffnen, um Hilfe zu rufen. In diesem Augenblick tritt sin Fremder ein. 19 A family row is interrupted mid-action by the entrance of a stranger; a 'Tableau', or moment of arrest of action, ensues. The former network of relations -both between the different characters on stage, and between the audience and characters -is disrupted, and the suspension 18 See GS Bd.2, p. 1380 and p. 1386, in which Tiedmann and Schweppenhäuser note the objections to the 1939 version of the essay expressed by members of Brecht's circle, such as Margarete Steffin, if not directly by Brecht himself.

  19

  example, in 'Aus: Der Geist der Versuche': 'In all dem, dieser Montage, diesem inneren Monolog, dieser kritischen Stellung der nichtaristotelischen Dramatik zur Einfühlung, löste sich die große harmonische bürgerliche Erzählung und das Drama auf, die Kunstformen mischten sich'. Brecht, Bertolt Gessamelte Werke in acht Bänden, Schriften 2, Zur Literature und Kunst.Frankfurt am Main, Suhrkamp Verlag, 1967 p.320. es möglich ist, gesteigerte Anschaulichkeit mit der Durchführung der marxistischen Methode zu verbinden. Die erste Etappe dieses Weges wird sein, das Prinzip der Montage in die Geschichte zu übernehmen. Also die großen Konstruktionen aus kleinsten, scharf und schneidend konfektionierten Baugliedern zu errichten. 33

  xi.

	5	GS, Bd. 5, [N1, 10], p. 572.
	6	Adorno, Theodor. W., 'Charakteristik Walter Benjamins', Prismen: Kulturkritik Und Gesellschaft,
	Munich, Verlag GmbH & Co. KG, 1963, p. 244.
	7	Adorno, Theodor. W., Ibid.
	8	See for example Eiland and Jennings' description of 'Brecht's theory of montage' as 'important to
	Benjamin's practice as a writer' in Walter Benjamin: A Critical Life, Cambridge MA and London, UK, Belknap,
	Harvard, , 2014. p.323.
	9	'Der Autor als Produzent: Ansprache im Institut zum Studium des Fascismus in Paris am 27 April
	1934', GS Bd. 2, pp. 683-701.
	10

  . 7. Auflage. Suhrkamp-Taschenbuch Wissenschaft 931. Frankfurt am Main: Suhrkamp, 2015, p. 227. In Einbahnstraße Benjamin writes, for example, about children's play as the production of objects through bringing together disparate materials into new relations, see 'Baustelle' in Einbahnstraße, Benjamin, Walter, Rolf Tiedemann, Tillman Rexroth, Hermann Schweppenhäuser, Theodor W. Adorno, and Gershom Scholem. Gesammelte Schriften. Bd. 4 Teil 1: Kleine Prosa, Baudelaire-Übertragungen [...]. 4. Aufl. Frankfurt am Main: Suhrkamp, 2006, p.93. In Both works Benjamin experiments with montage-form: in the Trauerspiel book the main text is interspersed by lengthy quotations, while Einbahnstraße is composed of short-form Denkbilder (thought or thinking images).

14

Benjamin, Walter. 'Über den Begriff der Geschichte

'GS Bd.1pp. 691-704.

36

  Benjamin describes, in 'Erfahrung und Armut', Einstein, Descartes, Klee and Brecht among others, as "constructors" -artists and thinkers who created from scratch, starting their work by wiping the traditional slate clean. See 'Erfahrung und Armut', GS, Bd. 2, pp. 215-216. 37 For a detailed discussion of the Crisis and Critique project within the context of Benjamin and Brecht's friendship, and transcripts of the planning sessions of the journal, see Wizisla, Erdmut. 'Krise und Kritik', Benjamin Und Brecht : Die Geschichte Einer Freundschaft ; mit Einer Chronik Und Den Gespraechsprotokollen des Zeitschriftenprojekts "Krise und Kritik". 1st ed., Frankfurt am Main,Suhrkamp, 2004, pp. 115-163, 'Dokumente zum Zeitschriftenprojekt "Krise und Kritik"', pp. 291-327. 38 From the session of 26 November 1930 on Krise und Kritik, quoted inWizisla, Erdmut. Benjamin Und Brecht: Die Geschichte Einer Freundschaft, p. 315. Benjamin. The Organization of Destruction', 'Nihilism, Destruction, Negativity: Walter Benjamin and the 'Organization of Pessimism'. Workshop, Jan Van Eyck Academie, 2 December 2012, p.7.

39

Noys,

'Das Autor als Produzent'. GS vol. 2, p. 697-8.

'Das Autor als Produzent', GS vol.2 p. 693.

 Brecht, Bertolt. Anmerkungen zur Oper, p. 78.


Luca Cirrottola

Algiane Froehly

Parallel unstructured mesh adaptation using iterative remeshing and repartitioning

Keywords: parallel mesh adaptation, unstructured meshes, mesh migration, interface displacement, distributed memory environments adaptation de maillage parallèle, maillages non structurés, migration de maillage, déplacement d'interface, environnemments

Mesh adaptation has proven to be a powerful tool for increasing the accuracy of numerical simulations whenever the solution exhibits strong non-uniform features over the computational domain. Sequential remeshing currently represents a bottleneck for parallel solvers. To this aim, we present a parallel remeshing algorithm that enables the reuse of existing sequential remeshing libraries, a non-intrusive linkage with third-party solvers, and an efficient exploitation of distributed parallel environments. The numerical procedure is implemented in the open source ParMmg software package.

Introduction

Mesh adaptation is becoming an increasingly used tool for improving the accuracy of numerical solutions in computational solid mechanics (CSM) and computational fluid dynamics (CFD) 1 . The need to adapt along sharp solution patterns (such as wave fronts and shock waves in fluid flows, or crack growth in solid mechanics, for example) has risen the interest to include preferential directions for local mesh refinement, derefinement and optimization, commonly referred as anisotropic mesh adaptation.

Metric-based mesh adaptation (see for example [START_REF] Pascal | Mesh Generation: Application to Finite Elements[END_REF] [Dob05] [DF08] [START_REF] Frey | Anisotropic mesh adaptation for CFD computations[END_REF]) offers a general framework for both isotropic and anisotropic mesh adaptation. The target mesh edge sizes and directions are computed from the numerical solution and its derivative, and used to build a Riemaniann metric tensor which describes a transformed space where the mesh should have unit sizes in each direction. In this framework, classical mesh modification operations can be applied by simply re-evaluating edge lengths through the metric tensor. The problem of finding an error estimator to drive mesh adaptation thus becomes independent from that of adapting the mesh, once the error estimator is translated into a metric tensor, simplifying the development of general-purpose remeshing libraries.

Since most of CSM/CFD solvers nowadays work on parallel computers, sequential mesh adaptation constitutes a bottleneck in the numerical solution workflow [START_REF] Michael | Unstructured Grid Adaptation: Status, Potential Impacts, and Recommended Investments Towards CFD 2030[END_REF], impacting both the computational time and the problem size, since this latter is limited by the memory available on a single computing node. From a general viewpoint, parallel mesh adaptation presents further complications compared to the sequential case, as several computational steps need to be considered:

1. Mesh partitioning (can be provided by the CSM/CFD solver).

2. Parallel remeshing.

3. Mesh repartitioning -Load balancing.

Depending on the strategies, the last two stages can be repeated iteratively until a satisfying mesh quality is reached.

Parallel remeshing strategies can be classified in two main categories. The first class of techniques aims at parallelizing the mesh generation techniques. Once an initial mesh partitioning is provided, the main difficulty of these techniques resides in adapting on the partition interfaces, as a non-negligible amount of communication is needed to preserve mesh conformity on the interface (see for example [START_REF] José | The Dynamic Adaptation of Parallel Mesh-Based Computation[END_REF] [DCS99] [OBG00] [START_REF] Chrisochoides | Parallel Delaunay mesh generation kernel[END_REF]). A final load balancing step can be required in order to evenly distribute mesh entities over the processors before returning the adapted mesh to an external solver.

The second class aims at re-using existing sequential remeshers in a parallel framework. Once an initial mesh partitioning is established, mesh adaptation is forbidden on partition interfaces, in order to avoid race conditions and preserve mesh conformity, and adaptation is performed only in the partitions interior. The resulting mesh is then re-partitioned so to move the former partition interfaces, and remeshing is repeated in order to adapt on formerly forbidden zones. By iterating on these remeshing-repartitioning stages, a globally adapted mesh is obtained (see for example [START_REF] Flaherty | Parallel structures and dynamic load balancing for adaptive finite element computation[END_REF]

[CSF05] [Dig+17] [MDV11]).
The aim of the ParMmg software package is to build parallel mesh adaptation capabilities on top of the sequential open-source remesher Mmg [DDF14] [Mmg], while preserving the opensource spirit and the support for general-purpose applications through the library applicationprogramming interface (API). Therefore, in the following we will focus on the development of a parallel iterative remeshing algorithm allowing the re-use of existing sequential remeshers, coupled with a repartitioning algorithm capable of effectively move parallel interfaces.

Parallel iterative remeshing over constrained interfaces

The core idea of this family of method is to employ sequential remeshing techniques in the domains interior, while parallel interfaces are constrained (i.e. adaptation is forbidden on the interface), then the interface is moved by a repartitioning method, mesh migration is performed and the process is iterated until an overall good mesh quality is reached. The same idea has been already exploited in the context of parallel mesh generation [Löh13] [Löh14].

Sequential remeshing over constrained interfaces have been already exploited in a parallel iterative framework in [START_REF] Hammond | Mapping Unstructured Grid Computations to Massively Parallel Computers[END_REF] [She+95] [Ozt95] [START_REF] Flaherty | Parallel structures and dynamic load balancing for adaptive finite element computation[END_REF], where the interface is moved by an advancing front and mesh migration is performed by one layer of elements at a time. The interface is instead moved by several layers at a time in [START_REF] Cavallo | Parallel Unstructured Mesh Adaptation Method for Moving Body Applications[END_REF] [DR07] before performing mesh migration. In [START_REF] Digonnet | Massively parallel anisotropic mesh adaptation[END_REF], the mesh migration by advancing front presented in [START_REF] Coupez | Parallel meshing and remeshing[END_REF] is coupled with load balancing by processor pairing. In [LDP14] [Lac+17] remeshing by means of Mmg is iteratively performed on parts of the mesh that need remeshing after they have been identified and partitioned through Scotch. In [START_REF] Alauzet | On the Use of Space Filling Curves for Parallel Anisotropic Mesh Adaptation[END_REF], Hilbert space-filling curves plus a correction algorithm are used for the purpose of producing connected mesh partitions on every process, while Mmg is employed as sequential remesher, then partitions are merged and repartitioned to perform Inria new remeshing steps. In [START_REF] Loseille | Serial and Parallel Mesh Modification Through a Unique Cavity-Based Primitive[END_REF], after remeshing is performed in the partition interiors, one or two elements layers next to the interfaces are extracted and either gather or repartitioned to be adapted. In [START_REF] Loseille | Parallel generation of largesize adapted meshes[END_REF], a multiple-levels partitioning is employed to partition the domain, than the set of elements touching the interfaces. Once the interior of the partitions are adapted, the interface layers are enlarged so to include all mesh cavity that will be needed to locally adapt on the interfaces.

Following previous works on the parallel usage of Mmg [START_REF] Moureau | Design of a massively parallel CFD code for complex geometries[END_REF] [Ben+16], we focus on a twolevels partitioning scheme where the mesh is first partitioned on the parallel computer. Then, local data are further partitioned into mesh groups, which can be remeshed sequentially by the local process one after the other. The size of the mesh group is targeted to an optimal size for the Mmg remeshing process. Both interfaces between partitions and mesh groups are kept unchanged during the remeshing step.

After the remeshing step, the mesh is repartitioned in order to change the parallel interface and to allow a new remeshing step. This can be accomplished through several strategies. In [START_REF] Moureau | Design of a massively parallel CFD code for complex geometries[END_REF] [Ben+16], a load balancing step is applied to the partitioning of the parallel mesh group graph rather, than of the parallel mesh element graph, in order to ease the partitioning task for the Metis library. To do that, the size of the mesh groups is recalibrated for the repartitiong task. A high weight is placed on graph edges proportionally to old parallel interfaces, so to penalize the occurrence of these edges in new partition interiors. ParMmg supports the same algorithm.

A certain compromise between an optimal load balancing and the number or remeshingrepartitioning iterations needs to be sought. We have found that load balancing algorithms can be difficult to tune for an effective interface displacement that limits the number of total iterations performed, as their primary aim is that of minimizing a communication cost function, without explicitly targeting interface displacement. For this reason, we have investigated the usage of direct interface displacement methods for mesh repartitioning, at the expense of optimal load balancing.

Metrics interpolation

As the original metrics can be modified by the sequential remesher in order to impose additional geometrical requirements or gradation (this is done in our case by Mmg), the original user-defined metrics needs to be recovered after each remeshing iteration in order to prevent information loss as the remeshing iterations are continued.

In our algorithm, this is done by interpolating the metrics from the mesh at the previous iteration to the mesh to the current adapted mesh. This allows to avoid parallel communication, as both the background and current group meshes are local. A classical walk-search algorithm is employed for node localization, and interpolation on P1 finite elements is used (both are resumed, for example, in [START_REF] Alauzet | P1-conservative solution interpolation on unstructured triangular meshes[END_REF]).

Solution interpolation is not currently supported, but different strategies could be envisaged. In this case, it would be better to interpolate only from the initial to the final mesh in order to reduce the computational time, with parallel box-intersection to pair the differently distributed initial and final groups (as done in [START_REF] Digonnet | Massively parallel anisotropic mesh adaptation[END_REF]).

Mesh repartitioning

Many algorithms can be used to perform mesh partitioning. One category of methods falls into general graph partitioning approaches, such as those commonly used through the Metis and Scotch libraries [Kar] [Pel09]. A second category exploits geometrical or topological information which are specific about the mesh partitioning problem, like recursive spectral bisection (described for example in [Sim91], inertia axis methods (described in [START_REF] Pascal | Mesh Generation: Application to Finite Elements[END_REF] [START_REF] Farhat | Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics[END_REF]) and greedy algorithms [START_REF] Farhat | A simple and efficient automatic fem domain decomposer[END_REF] [FL93], among others.

Graph-based partitioning schemes generally aim at minimizing a given cost function, as a model of the communication cost, and old parallel interfaces can be penalized by applying a high weight on the corresponding graph edge, thus only indirectly trying to minimize the occurrence of a new parallel interface coincident with the old one. Similarly, mesh-based partitioning methods are still designed to produce well-balanced partitions and to reduce the communication cost. This is often done by exploiting more information about the mesh as a bipartite graph, through element and node adjacency. In the following sections, we will rather focus on the construction of a repartitioning algorithm explicitly targeting interface displacement, as this is the primary interest in an iterative remeshing scheme in order to converge to an adapted mesh all over the domain.

Interface displacement by an advancing-front method

We follow the same idea employed in [START_REF] Dobrzynski | Parallel mesh adaptation[END_REF] [CSF05] to move the interface by an advancing-front algorithm. We adopt an element-based partitioning scheme, thus we aim at propagating the front of parallel nodes by walking on edge connectivity, in order to mark the visited tetrahedra with the color brought by the front.

To this purpose, a front direction needs to be chosen. This operation allows to give each front node a unique color, based on the colors of the tetrahedra in its ball, and a logical operator to decide whether this color should be passed to the tetrahedra visited by the front, or not. This operation also allows to handle the case of colliding fronts. Once a direction is chosen for the propagation of the interface, the front nodes visit all the tetrahedra in their ball and mark them for repartitioning, if it is compatible with the front direction. Then, the color is passed to the outer points of the ball, and a new front is created. By performing this process N times, an N -layer mesh subgroup is built just beside the old parallel interfaces. This process is reminiscent of a parallel version of the greedy algorithm for sequential mesh partitioning [START_REF] Farhat | A simple and efficient automatic fem domain decomposer[END_REF], where the seeds are not chosen independently but only the current node interfaces are allowed to grow their ball by N new layers. At the end of each step, a parallel update is performed for the color of the nodes on current parallel interfaces.

This algorithm effectively produces a new mesh partitioning that can be directly used for any already available mesh migration routines. An example of front advancement on 4 partitions in a sphere is given in figure 1. From the practical point of view, this algorithm needs to be complemented with: 1) the choice of the front advancement direction, and 2) handling of disconnected partitions, i.e. partitions where all elements cannot be reached by face adjacency (see for example figure 2), which are very likely to be produced by the advancing front [START_REF] Farhat | A simple and efficient automatic fem domain decomposer[END_REF] [Ozt95].

Groups sorting for interface advancement direction

For every interface, a propagation direction needs to be chosen. In [START_REF] Hammond | Mapping Unstructured Grid Computations to Massively Parallel Computers[END_REF] and [START_REF] Digonnet | Massively parallel anisotropic mesh adaptation[END_REF], processors are paired in order to balance the computational load. Since optimal load balancing is not the main aim of the remeshing phase, we have preferred to sort the current groups by the number of elements, and move the interface in the direction of the bigger mesh group. This naïve global sorting allows to effectively handling the case of colliding fronts, as each of them continues to propagate into the bigger partition found, without the need to form new pairings.

Correcting disconnected partitions

As already hinted in [START_REF] Farhat | A simple and efficient automatic fem domain decomposer[END_REF] [START_REF] Hammond | Mapping Unstructured Grid Computations to Massively Parallel Computers[END_REF], experience shows that any advancing-front mesh partitioning algorithm is likely to produce disconnected partitions in given conditions. Although Mmg is capable of handling disconnected partitions, and it could be argued that a solver should be capable of handling generic mesh partitions, this is often not an optimal situation to perform computations. For example, in mesh adaptation over constrained interfaces one should aim at keeping the ratio between surface and volume elements as high as possible, which is not the case when disconnected mesh parts appear in a partition. Disconnected partitions also require special treatments for the localization step for metrics interpolation from the old to the new mesh (like tree-searches), which are not needed for connected partitions. Some examples of common problems are presented in section 4.3.1. Some a priori corrections to prevent the occurrence of disconnected partitions have been hinted in [START_REF] Farhat | Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics[END_REF], where the greedy algorithm is stopped and restarted if disconnected elements are detected. Similarly, in [START_REF] Ozturan | Distributed Environment and Load Balancing for Adaptive Unstructured Meshes[END_REF] the interface front advancement is said to be stopped if the target processor becomes disconnected from the sender processor. While this correction effectively prevents disconnections in the growing partition, it doesn't prevent shrinking partitions from becoming disconnected (as for example for a non-convex partition, as it will be shown in the next section). For these reasons, we have implemented in ParMmg an a posteriori correction of disconnected partitions, presented in section 4.3.2, to be performed only once after several layers of front advancement have been performed.

Examples of configurations leading to disconnected partitions

The next paragraph focuses on the presentation of the most common geometrical and partitioning configurations leading to disconnected meshes. For sake of simplicity, we use two-dimensional examples to illustrate this configurations.

Eaten non-convex partitions If the original partition is not convex, the interfaces could move inward so to cut away some partition extremities when the interface hits a boundary or when several interface fronts collide. This issue can be easily solved by checking and fixing the contiguity of the interior partition at the end of the interface displacement step. This configuration is illustrated in the right zoom in figure 3.

Isolated bites If care is not given to the order by which each node grows and marks its ball, it can happen that the color of a partition is propagated when it should not have been in the first place, and the following propagation of a higher-priority front takes some isolated bites [START_REF] Farhat | A simple and efficient automatic fem domain decomposer[END_REF] that disconnect the previously grown ball from its main partition. This configuration is illustrated in the left zoom in figure 3.

Parallel star configurations In the same way, if the front reaches an interface on a local partition and this information is not communicated to the remote processor, at the next propagation step the layer that propagated on the remote partition could not be reachable anymore by its original partition. This behavior is easily corrected by always performing a parallel update after one level of front advancement.

A posteriori corrections

From the practical point of view, it is difficult to predict all the situations that could lead to a disconnected partition in three dimensions. A more general and robust approach is that of a posteriori correcting partition connection after the front advancement step. This can be achieved by means of two kinds of checks, one on the contiguity of the local partition, one on the reachability of all layers that have propagated in the local partition by means of their remote counterpart. An a posteriori correction also allows for a generic choice of the interface propagation algorithm.

Contiguity fix for the local partition

1. Similarly to greedy algorithms, we choose a color and start from an element of this color:

we attempt at touching all elements of this color by adjacency (through the element faces).

Elements that we are able to reach by adjacency are stored in a list (main_list).

2. While we are able to find an element of the same color outside of main_list:

• we build by adjacency a second list of elements of this color (next_list);

• If next_list is not empty, we compare the lengths of next_list and main_list and we merge the smaller list of elements into an adjacent color. The biggest list is stored as main_list and we go back to step 2.

3. Go back to step 1 (choice of a color and construction of main_list) until all the colors have been treated.

Reachability fix for the inward-propagating remote partitions As hinted in [START_REF] Ozturan | Distributed Environment and Load Balancing for Adaptive Unstructured Meshes[END_REF], the front advancement can create subgroups cut away from any interface, or subgroups connected only to an interface of different color than their remote counterpart. These subgroups are not reachable by their remote partition anymore. To fix this problem, after a parallel exchange of remote colors on the current interface, for each interface face we attempt at building a list of elements of the same remote color which can be touched by adjacency, and we mark them as reachable. At the end of this process, we iteratively look for a list of adjacent elements which have not been reached by remote colors, and merge them into an adjacent color (reachable or not).

Inria

The current implementation is conceived in order to leave the interface displacement and the contiguity/reachability correction independent. This allows for a certain freedom in the experimentation of different advancing-front methods (for example, advancing on element adjacency instead of node adjacency). and interface sorting methods. Although a partition could be a priori split into an arbitrary number of disconnected parts, the contiguity correction algorithm only uses two lists to immediately compare two parts and merge the smallest into another color, thus limiting the memory usage. Similarly, the reachability correction algorithm only uses one list to store the current subgroup of unreachable elements. At the end of the two correction steps, all mesh elements are guaranteed to having been touched by a list only once, if the counter is decremented every time an element is merged in a different color.

Summary of the algorithm

The key features of the parallel remeshing algorithm can be summarized as follows:

• Two-level parallelization scheme (distributed mesh partitions and local mesh groups);

• Sequential remeshing of mesh groups over constrained parallel interfaces.;

• Mesh repartitioning by interface displacement.

A pseudocode for the ParMmg workflow is presented in algorithm 1. Mesh migration directly exploits the two-level parallelization schemes, as mesh parts to be sent to other processors are assembled into mesh groups to be used for parallel communication, while mesh repartitioning acts as an independent step which can be further tailored to ensure a more robust load balancing. A pseudocode for mesh repartitioning is presented in algorithm 2 Algorithm 1 ParMmg algorithm pseudocode. The presented algorithm is implemented into the ParMmg software package for parallel unstructured mesh adaptation, released under the GNU Lesser General Public License (LGPL) and available at the repository https://github.com/MmgTools/ParMmg. The implementation is targeted to provide:

• Reusage of existing sequential remeshing libraries;

RR n°9307

Algorithm 2 Mesh repartitioning pseudocode.

1: Input(mesh groups); 2: Sort interfaces; /* Choose interface propagation direction */ 3: Parallel update of interface colors; 4: for i layer = 0, . . . , n layer -1 do /* Loop on mesh groups */ 5:

Propagate node front; 6: end for 7: Correct contiguity; 8: Correct reachability; 9: Mesh migration; 10: Output(mesh groups); /* Return repartitioned groups */

• Non-intrusive linkage with third-party solvers;

• Improvable parallel performances by means of dynamic load balancing.

Open-source software packages are used for every step in the computing chain, from mesh partitioning, remeshing, node renumbering, mesh visualization. The remeshing kernel is the sequential Mmg library [DDF14] [Mmg]. Parallelization is performed through Message Passing Interface (MPI) libraries. Partitioning of a centralized input mesh is performed by means of the Metis library [Kar] [Met], and the Scotch library [Sco] is employed for nodes renumbering to reduce cache misses. Finally, mesh files can be saved for visualization in the Medit format (readable by Medit [START_REF] Frey | MEDIT : An interactive Mesh visualization Software[END_REF] [Med] and Gmsh [START_REF] Geuzaine | Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities[END_REF]) and in VTK format [START_REF] Schroeder | The Visualization Toolkit: An Object-oriented Approach to 3D Graphics[END_REF][Vtk]. Finally, version control is performed with Git and continuous integration testing with Jenkins.

Results

Qualitative comparison of graph-based repartitiong and interface displacement algorithms

In this section we compare the behaviour of graph-based repartitioning and repartitioning by interface displacement in effectively enabling mesh adaptation near old parallel interfaces. For graph-based repartitioning, we penalize each old parallel face f by computing an associated weight w f as

w f = min   1 exp α na na i=1 e i , w max   (1)
where index i runs on the edges of the face (n a = 3 for a simplicial mesh), α = 28 and w max = 10 6 . Quantity e i is built using the length of the edge l M,i in the metrics M as

e i =    l M,i -1 if l M,i ≤ 1 1 l M,i -1 if l M,i > 1 (2)
This expression is inspired by the effectiveness index introduced in [Dob05] and used in [START_REF] Dobrzynski | Fast and accurate simulations of air-cooled structures[END_REF]. This weight is converted in integer format and directly applied to graph edges when a mesh partition is split into groups. When groups have to be repartitioned, instead, the sum of the weights on the parallel interface between two groups is applied on the graph edges.

Inria

The effectiveness of the proposed weight is shown in figure 7.1. The test case is a sphere of radius 10, with a tennis ball isotropic metrics

h(x, y, z) = h max -(h max -h min ) exp ŷ -x2 + ẑ2 2 , x = sx, ŷ = sy, ẑ = sz (3)
with s = 0.1, h min = 0.3 and h max = 1.5. For tetrahedra on a parallel interface, the sum of the weights on parallel faces is visualized. For interior tetrahedra, an arbitrary unitary weight is visualized. The weight is capable of capturing the tetrahedra that do not respect the imposed metrics. This includes boundary regions, as boundary surfaces are not adapted in the current implementation. Anyway, graph-based repartitioning has difficulties in converging towards a fully adapted mesh as the number of remeshing-repartitioning is increased when a significant number of partitions/groups is involved. This can be seen in figure 5, where meshes obtained after three iterations of remeshing and load balancing are compared with meshes obtained after three iterations of remeshing and interface displacement. Old parallel interfaces are clearly visible as poorly-adapted regions in graph-based partitions, while this effect is much less evident with direct interface displacement.

Parallel weak-scaling of a uniform refinement test case

For a preliminary evaluation of the parallel performances of the algorithm, we test its weak scalability for an uniform refinement case. The aim is that of distributing the work load on each mesh group as uniformly as possible.

The geometry is a sphere of radius 10. Input meshes have been generated with Gmsh, and their size grows with the number of processors (the input edge size is shown in table 1).

The assigned target mesh size is about 1/6 the original edge size. The size of the output adapted meshes are shown in table , compared with the sizes of the corresponding input meshes. The same results are visualized in figure 7, in order to check that the load is maintained approximately constant in the weak scaling test.

Tests have been performed on the Miriel nodes of PlaFRIM cluster2 , equipped with 2 Dodecacore Haswell Intel Xeon E5-2680 v3 (2.5 GHz) and 128 GB of RAM (see figure 6 for the lstopo view), connected through Infiniband QDR TrueScale (40 Gb/s) and Omnipath (100 Gb/s).

The computational time in the weak scaling test is shown in figure 8. The total time is split into the time spent in the remesher and the time spent in mesh repartitioning. In this phase, the time spent in migrating the mesh (MPI communication) is explicitly highlighted. It can be seen that the remeshing time is kept approximately constant with the number of cores, while the time for mesh migration constitute a bottleneck on more than 64 cores. The reasons for this behavior are currently under investigation. Even if performances can clearly still be optimized, parallel remeshing is able to generate billion-element meshes over 128 cores (table 2).

Preliminary results on anisotropic test cases

A qualitative assessment of the capabilities of our parallel remeshing algorithm to handle anisotropic mesh adaptation is given in this section. The implementation of interface displacement algorithm has not been tuned for anisotropic cases yet, so the following tests are mostly intended to verify that metrics interpolation is correct, and to assess the effects of the iterations in order to collect research directions for future developments.

is given in figure 9, for 6 iterations on 8 processors. It can be seen that still more iterations are needed to converge towards a fully adapted mesh, with respect to the isotropic case. In particular, we notice that some isotropic regions are visible near old parallel interfaces (left zoom in figure 9).

Continuous sinusoidal shock

The last effect is confirmed when adapting on a more complex function, like the continuous sinusoidal shock from [START_REF] Alauzet | A parallel matrix-free conservative solution interpolation on unstructured tetrahedral meshes[END_REF] f = tanh(20(x + 0.3 sin(-10y) -0.3 sin(-0.5(z -0.1)))), x = sx, ŷ = sy, ẑ = sz (5) with s = 0.1. The anisotropic metrics is computed from the Hessian matrix of the function following the approach in [START_REF] Alauzet | Estimateur d'erreur géométrique et métriques anisotropes pour l'adaptation de maillage. Partie I : aspects théoriques[END_REF]. The eigenvalues λ i of the Hessian matrix are truncated as

λi = min max c d |λ i |, 1 h 2 max , 1 h 2 min i = 1, . . . , 3 (6)
with h min = 0.1 and h max = 1.5. Parallel results, for 6 iterations on 8 processors, are compared with the sequential ones in figure 10. It can be noticed that the effects of parallel interfaces in spreading isotropic zones is evident. This is probably due to the way the metrics is corrected in Mmg on parallel interfaces, and an improvement of this correction is likely to improve the anisotropic results too. We have presented a parallel unstructured mesh adaptation algorithm based on iterative remeshing and mesh repartitioning. The algorithm rests on a two-level parallelization scheme allowing to tweak the mesh group size for remeshing, and on a mesh repartitioning scheme based on interface displacement by front advancement. Specific corrections have been developed to avoid the occurrence of disconnected mesh groups during the interface propagation step, and the efficacy of an interface displacement repartitioning algorithm compared to a graph-based repartitioning approach has been shown.

Inria

Isotropic weak-scaling tests and anisotropic tests provide directions for future software improvement. New developments are foreseen in order to enable:

• Adaptation on boundary surfaces.

• Discretization of implicit surfaces described by a level-set function.

• Load balancing improvement during repartitioning.

The described algorithm is implemented into the open-source ParMmg software application and library, released under LGPL license, and available at the reporitory https://github.com/ MmgTools/ParMmg.

Inria

;

  (a) Initial groups. ; (b) Groups after front advancement.

;

  (c) Initial groups (volumic cut). ; (d) Groups after front advancement (volumic cut).

Figure 1 :

 1 Figure 1: Example of mesh repartitioning by interface displacement in a sphere. Left: Initial partitioning. Right: Final partitioning.

Figure 2 :

 2 Figure 2: An example of disconnected mesh partition.

  Inria(a) Initial groups and interface front. (b) Groups after one level of front advancement.

Figure 3 :

 3 Figure 3: Two-dimensional illustration of some configurations leading to disconnected partitions. Right zoom: The extremity of a non-convex partition is cut away from its main domain by front advancement. Left zoom: unordered front advancement leading to an isolated bite (priority is red-blue-green-yellow).

;

  (a) Metrics (1 iteration).

;

  (b) Interface weights (1 iteration).

;

  (c) Metrics (2 iterations). ; (d) Interface weights (2 iterations).

;

  (e) Metrics (3 iterations).

;

  (f) Interface weights (3 iterations).

Figure 4 :

 4 Figure 4: Mesh partitions produced by graph-based repartitioning for different number of remeshing-repartitionig iterations, for the isotropic tennis ball case. Left: isotropic metrics. Right: Interface weights.

;

  (c) Graph-based repartitioning (second cut). ; (d) Interface displacement (second cut).

;

  (e) Graph-based repartitioning (third cut).

;

  (f) Interface displacement (third cut).

Figure 5 :

 5 Figure 5: Comparison of graph-based repartitioning (left) and interface displacement for different volume cuts on the isotropic tennis ball case, for three iterations of remeshing-repartitioning on 8 cores (between 2 and 8 groups per partition are used). Colors represent the isotropic metrics.

Figure 6 :

 6 Figure 6: lstopo view of a miriel node

Figure 7 :

 7 Figure 7: Number of nodes in the input and output meshes for the weak scaling test.

Figure 8 :

 8 Figure 8: Computational time in the weak scaling test.

Figure 9 :

 9 Figure 9: Uniform anisotropic mesh adaptation (volume cut), 6 iterations on 8 processors. Right zoom: A parallel interface is still visible. Left zoom: Isotropic zones induced by a parallel interface.

;

  (c) Sequential (second volume cut).

;

  (d) Parallel (second volume cut).

Figure 10 :

 10 Figure 10: Adaptation on the continuous sinusoidal shock (volume cuts). Left: Sequential Mmg. Right: ParMmg with 6 iterations on 8 processors.

Table 1 :

 1 Input mesh edge size with different number of cores.

		in)
	1	0.16667
	2	0.13228
	4	0.10499
	8	0.08333
	16	0.066142
	32	0.052497
	64	0.041667
	128	0.033071
	256	0.026248
		Inria

Table 2 :

 2 Number of nodes and elements in the input and output meshes, with different number of cores.

RR n°9307

Supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/) RR n°9307

avenue de la Vieille Tour 33405 Talence Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

This work was performed within the framework of the ExaQUte project, founded by the European Union's Horizon 2020 research and innovation programme under grant agreement No 800898.

This work has received funding from the FUI22 ICARUS project, founded by Région Nouvelle-Aquitaine (RNA) under grant agreement 17001260-031 and the Fonds Unique intérministeriel (FUI) under grant agreement No DOS0050687100.

Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/).

The authors would like to thank the scientific support of the YALES2 development team at the CORIA research center in the implementation of the parallel remeshing algorithm.

The authors would like to recognize the fundamental impulse that Cécile Dobrzynski brought to this work.