Joris Van Der Hoeven

Grégoire Lecerf
email: lecerf@lix.polytechnique.fr

Sparse polynomial interpolation in practice

Introduction

Sparse polynomial interpolation consists in recovering of a sparse representation of a polynomial P given by a blackbox program which computes values of P at as many points as necessary. In practice P is typically represented by DAGs (Directed Acyclic Graphs) or SPLs (Straight Line Programs). For polynomials with at most t terms over a field K, this task typically involves O(t) evaluations of P , operations on integers for discovering the exponents of the nonzero terms of P , and an additional number of operations in K that can be bounded by O ˜(t) for recovering the coefficients [START_REF] Ben-Or | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF].

However, the latter complexity analysis does not take into account the sizes of coefficients in K and the expression swell that might occur when evaluating at points with high height [START_REF] Kaltofen | Modular rational sparse multivariate polynomial interpolation[END_REF]. For practical implementations, it is important to perform most of the computations over a prime finite field F p , where p fits into a single machine register. On modern architectures, this typically means that p < 2 64 . There mainly are two approaches which can be used over finite fields: the "prime number" approach [START_REF] Kaltofen | Modular rational sparse multivariate polynomial interpolation[END_REF] and the "Kronecker substitution" approach [START_REF] Kaltofen | Fifteen years after DSC and WLSS2, what parallel computations I do today[END_REF]. For more references and practical point of views on known algorithms we refer the reader to [START_REF] Arnold | Faster sparse polynomial interpolation of straight-line programs over finite fields[END_REF][START_REF] Arnold | Multivariate sparse interpolation using randomized Kronecker substitutions[END_REF][START_REF] Javadi | Parallel sparse polynomial interpolation over finite fields[END_REF] (see also [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial multiplication[END_REF] in a more restricted context). We recall these approaches in Section 2. In Section 3, we present new techniques which may be used to further enhance and combine these classical approaches.

We report on our implementations in the multimix C++ library of the Mathemagix system [6]. For the sake of conciseness some discussions on the probabilistic aspects will be informal. The interested reader might consult [START_REF] Arnold | Multivariate sparse interpolation using randomized Kronecker substitutions[END_REF][START_REF] Kaltofen | Early termination in sparse interpolation algorithms[END_REF] on this topic. Of course, once a candidate for the sparse representation is found, then the Schwartz-Zippel lemma can be used to verify it with a low level of failure [START_REF] Zur Gathen | Modern Computer Algebra[END_REF].

Previously known approaches

Throughout this paper, we will use vector notation for n-tuples: given variables x 1 , ..., x n , we write K[x] := K[x 1 , ..., x n ]. If α is a vector of n elements in K or the sequence of the variables x 1 , ..., x n , and if a ∈ N n , then we write

α a := α 1 a1 ••• α n an and |a| := a 1 + ••• + a n . If P = i=1 t c i
x ei with all the exponents e i ∈ N n pairwise distinct and c i = / 0, then for all α ∈ K n we have

f (z) := i 0 P (α 1 i , ..., α n i ) z i = 1 i t c i 1 -α ei z . (1)
If the values α ei are pairwise distinct, then it is classical that c 1 , α e1 , ..., c t , α et ∈ K can be computed efficiently from the first 2 t terms of the power series f (z) [START_REF] Ben-Or | A deterministic algorithm for sparse multivariate polynomial interpolation[END_REF]. One may further recover the e i from the α ei with suitable values of α. If no bound for t is known in advance, then we try to interpolate for successive upper bounds t in geometric progression. Over many common fields such as K = Q, the numbers α ei can become quite large. For efficiency reasons, it is better to work over a finite field F p as much as possible. Moreover, we wish to take a p which fits into a single machine register, so that computations in F p can be done very efficiently. When using modular reduction, the problems of computing the e i and computing the c i are actually quite distinct, and are best treated separately. The e i do not mostly depend on p (except for a finite number of bad values) and only need to be computed for one p. The c i are potentially large numbers in Q, so we may need to compute their reductions modulo several p and then recover them using rational number reconstruction [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. From now on, we focus on the computation of the support of P written supp P := {e i | 1 i t}. Let d i represent the partial degree of P in x i , and let

D i := d i + 1.
For the determination of suitable α ∈ F p n such that the e i can be reconstructed from the α ei , the "prime number" approach is to take α = q mod p, where q = (q 1 , ..., q n ) and q i is the i-th prime number. As long as q ei < p, we may then recover e i from q ei by repeated divisions. If d := max i t |e i | is the total degree of P , then it suffices that q n d < p. We recall that q n asymptotically grows as O ˜(n), so that p can be taken of bit-size in O ˜(d log n). This approach is therefore efficient when d is sufficiently small.

If K = F p , the "Kronecker substitution" approach is to take α = (ω, ω D1 , ω D1D2 , ..., ω D1•••Dn-1 ), where ω is a primitive root of the multiplicative group

F p * . Assuming that D 1 ••• D n p -1, we can compute all the value α ei = ω ei,1+ei,2D1+•••+ei,nD1•••Dn-1 .
Moreover, assuming that the prime number p is "smooth", meaning that p -1 has only small prime factors, the discrete logarithm problem can be solved efficiently in F p * : given a ∈ F p * there exists a relatively efficient algorithm to compute l ∈ {0, ..., p -2} with ω l = a [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[END_REF]. In this way we deduce all the e i . This approach is efficient when the partial degrees are small. More specifically, we prefer it over the prime number approach if

D 1 ••• D n < q n d .
We notice that bounds for d, d 1 , ..., d n are sometimes known in advance (e.g. from a syntactic expression for P ) and sometimes have to be guessed themselves. The total degree can be guessed efficiently by using sparse interpolation for the univariate polynomial P (α 1 t, ..., α n t), where α = (α 1 , ..., α n ) is a random point in (F p * ) n . Similarly, the partial degrees d i are obtained by interpolating P (α 1 , ..., α i-1 , t, α i+1 , ..., α n ).

Remark. It often occurs that the expression for P involves division even though the end result is a polynomial; this happens for instance when computing a symbolic determinant using Gaussian elimination. When division is allowed in the prime number approach, then some care is required in order to avoid systematic divisions by zero. For instance, 1/(x 1 -1) cannot be evaluated at α 0 and 1/(3 x 1 -2 x 2 ) cannot be evaluated at α 1 when α = q = (2, 3, ..., q n ). The first problem can be avoided by taking f := i 1 P (α i ) z i . The nuisance of the second problem can be reduced by replacing the q i by small random and pairwise distinct primes.

New incremental approaches

In this section we carry on with the same notation, and K is the finite field F p . We aim at decomposing the interpolation problem into several ones with less variables in order to interpolate more polynomials than with the previously known techniques. For all our algorithms, we assume that the support supp Q = {f 1 , ..., f s } ⊆ N n-m of Q(x m+1 , ..., x n ) := P (α 1 , ..., α m , x m+1 , ..., x n ) is known for some 1 < m < n and random α 1 , ..., α m ∈ F p * . We will write d m and d >m for the total degrees of P in x 1 , ..., x m resp. x m+1 , ..., x n . Let η > 0 and assume that p η d t. By the Schwartz-Zippel lemma, taking random α i in {0, ..., η s d m -1} ensures that supp Q coincides with the projection of supp P on N n-m with probability at least 1 -1/η. Separating forms. Assume that 1 < m < n -1 and let u ∈ N n-m be such that u • f 1 , ..., u • f s are pairwise distinct. Such a vector u, seen as a linear form acting on the exponents, is said to separate the exponents of Q. A random vector in {0, ..., η s 2 /2} n-m separates exponents with probability at least 1 -1/η. Since one can quickly verify that u is a separating form, it is worth spending time to search for u with small entries. Now consider a new variable y and R(x 1 , ..., x m , y) := P (x 1 , ..., x m , y u1 , ..., y un-m ). The partial degree of R in y is O(η s 2 d >m ), hence its total degree is O(η d t 2 ). If h is in the support of R then there exists a unique exponent e of P such that e = (h 1 , ..., h m , u • (e m+1 , ..., e n )). We can compute e efficiently after sorting the f i accordingly to the values u • f i . We have thus shown how to reduce the sparse interpolation problem for P to the "smaller" sparse interpolation problem for Q. If p ≫ d t 2 , then the method succeeds with high probability.

Coefficient ratios. Let α = (q 1 , ..., q n ) and let f (z) be the generating series associated to P and α as in [START_REF] Arnold | Faster sparse polynomial interpolation of straight-line programs over finite fields[END_REF]. In a similar way, we may associate a generating series f ˜(z) to P ˜(x) = P (q 1 x 1 , ..., q m x m , x m+1 , ..., x n ). Using sparse interpolation, we find c i and α ei such that (1) holds, as well as the analogous numbers c ˜i = c i q 1 ei,1 ••• q m ei,m and α ei for f ˜(z). If q m d m < p, then these data allow us to recover the vectors e i, m = (e i,1 , ..., e i,m ) from the ratios c ˜i/c i . We may next compute the complete e i from α ei-e i, m , since we assumed supp Q to be known. This strategy also applies to the "Kronecker substitution" approach. In that case, we take P ˜(x) = P (ω x 1 , ..., ω D1•••Dm-1 x m , x m+1 , ..., x n ), and we require that

D 1 ••• D m p -1. If none of the conditions q m d m < p or D 1 ••• D m < p - 1
holds, then we let m ˜be maximal such that either q m d m < p or D 1 ••• D m p -1, and we recursively apply the strategy to P (α 1 , ..., α m , x m +1 , ..., x n ) and then to P itself.

Closest points. Let α = (ω, ω D1 , ..., ω D1•••Dn-1 ) be as in the "Kronecker substitution" approach. For each f i in the support of Q, let ϕ i ∈ {0, ..., p -2} be such that ω ϕi = α fi , and let δ be the smallest distance between any two distinct points of i=0 s (ϕ i + (p -1) Z). If d >m is large and the exponents of P are random, then δ is expected to be of the order p/s 2 (this follows from the birthday problem: taking s random points out of p/δ, the probability of a collision is 1/2 as soon as s ≍ p/δ ). Now assume that D 1 ••• D m δ. Performing sparse interpolation on P , we obtain numbers ω e1 , ..., ω et , as well as the corresponding ε i ∈ {0, ..., p -2} with ω εi = α ei . For each i ∈ {1, ..., t}, there is unique j ∈ {1, ..., s} and k ∈ {0, 1} with

0 ε i -ϕ j + k (p -1) < D 1 ••• D m δ.
We may thus recover e i from f j and ε iϕ j + k (p -1). In order to improve the randomness of the numbers ϕ i modulo p -1, it is recommended to replace D m by a random larger number.

Implementation and timings

The Mathemagix platform divides into three main components: low level structuring and efficient C++ libraries for classical mathematical objects, a compiler and an interpreter of the eponym language, and interfaces to external libraries. Mathemagix is an open source academic project hosted at http://gforge.inria.fr/projects/mmx/. The Internet home page concerning installation and documentation is http://www.mathemagix.org.

Multivariate polynomials, power series, jets, and related algorithms are integrated in the multimix C++ library of Mathemagix. Algorithms for sparse and dense representations have been previously reported in our article [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial multiplication[END_REF], in which we focused on fast polynomial products assuming given an overset of the support. This short note reports on the implementation of DAGs, SLPs, and sparse interpolation. At the C++ level, a DAG with coefficients in C has type dag_polynomial<C>. Arithmetic operations, evaluation, substitution, and also construction from a polynomial in sparse representation are available. For efficiency purposes, the evaluation of one or several DAGs on several points can be speeded up by building a SLP from it, whose type is slp_polynomial<C>. These classes are available from multimix/dag_polynomial.hpp and multimix/slp_polynomial.hpp. An overview of the main features in multimix together with examples and useful links to browsable C++ source code is available from http://www.mathemagix.org/www/multimix/doc/html/index.en.html.

Sparse interpolation is implemented in multimix/sparse_interpolation.hpp. Complete examples of use can be found in multimix/test/sparse_interpolation_test.cpp. If f : Q n → Q represents the polynomial function that we want to interpolate as a polynomial in Q[x 1 , ..., x n ], then our main routines take as input a function f ¯: Q n × N → N such that f ¯((a 1 , ..., a n ), p) is the preimage of f (a 1 , ..., a n ) computed modulo a prime number p. If computing f modulo p involves a division by zero, then an error is raised. For efficiency reasons, such a function f ¯can be essentially a pointer to a compiled function. Of course DAGs over Z or Q can be converted to such functions via SLPs.

In the next examples, which can be found in multimix/bench/sparse_interpolation_bench.cpp, we illustrate the behaviours of the aforementioned algorithms on an Intel(R) Core(TM) i7-3720QM CPU @ 2.60GHz platform with 8 GB of 1600 MHz DDR3 .

Example 1. Our first family of examples concerns products of random polynomials given in sparse representation: we pick up m polynomials with t terms, in n variables, and with partial degrees at most d, and compute the support of their product. With m = 8, n = 20, d = 40, t = 3, then a direct use of the "Kronecker substitution" involves computing with GMP based modular integers of bit size about 160: the total time amounts to 171 s (91 s are spent in the Cantor-Zassenhaus stage for root finding). With the "coefficient ratios" approach, the set of variables is split into 3 blocks and all the computations can be done with 64-bit integers for a total time of 31 s (most of the time is still spent in the Cantor-Zassenhaus stages, but relatively less in the discrete logarithm computations). With the "closest points" technique the set of variables is split into 5 blocks and all the computations are also done with 64-bit integers for a total time of 47 s. The "separating form" approach is not competitive here, since it does not manage to keep the computations on 64 bits integers only. Nevertheless, in a "lacunary polynomials" context, namely when d becomes very large, the computation of a very large smooth prime number becomes very expensive, and the "separating form" point of view becomes useful.

Example 2. As a second family of examples, we consider the determinant of a n × n matrix whose entries are independent variables. This determinant is a polynomial in n 2 variables with n! terms, whose total degree is n and whose partial degrees are all 1. The following table displays timings for interpolating this polynomial using the "Kronecker substitution" approach: n 5 6 7 8 Kronecker substitution 110 ms 915 ms 9.8 s 162 s Table 1. Timings for interpolating the determinant polynomial of a n × n matrix.

For n = 8 computations are performed via 128-bits modular arithmetic. Here we used a fast compiled determinant function, so that most of the time is spent in the Cantor-Zassenhaus stage. We noticed that the "closest points" strategy is not well suited to this problem. The "coefficient ratios" approach allows to perform all the computations on 64-bits for n = 8 within 223 s, but it is penalized by two calls to Cantor-Zassenhaus.

For a convenient use, our sparse interpolation routine is available inside the mmx-light interpreter. In the following session, we interpolate the determinant polynomial of a matrix of size n × n for n = 5 in 1.

  3 s, and for n = 6 in 9.6 s. As a comparison, the function sinterp, modulo 2 31 -1, of Maple 16 (trademark of Waterloo Maple Inc. http://www.maplesoft.com/products/maple) takes 18 s for n = 5, and 1 hour for n = 6. Mmx] use "multimix"; n:= 5; Mmx] det_mod (v: Vector Integer, p: Integer): Integer == { w == [ z mod modulus p | z in v ]; M == [ @(w[i * n, (i+1) * n]) || i in 0..n ]; return preimage det M; }; Mmx] coords == coordinates (coordinate ('x[i,j]) | i in 0..n | j in 0..n); Mmx] #as_mvpolynomial% (det_mod, coords, 1000) 120 Bibliography


Main text:

Entrepreneurship and, thus, small-and middlesized firms (SMEs) have had a growing interest for the past two decades, from the academic world as well as from public authorities. This interest is part of many economic changes. In particular, technological change and the increasing incidence of innovation in most developed countries have reduced the importance of the size of the companies in the industry and favored the development of entrepreneurial activities. In addition, globalization would have dragged the comparative advantages of North American and European countries toward knowledge-based activities, while the "knowledge-based economy" would be relatively more conducive to entrepreneurship and to SMEs.

At the European level, the Lisbon Agenda (2000) confirms the significance of innovation as a driver of change in the economic growth of tomorrow. In this perspective, entrepreneurship can be considered as one of the main levers to operate, especially since it is part of specific contemporary dynamics. First, researchers in economics highlight the involvement of a growing number of active SMEs in the innovation process, particularly in the case of clusters and competitiveness clusters. Moreover, the increase rate of unemployment during the 2000s, also fueled by economic and financial crisis that begun in 2007, led governments of many countries to ease the creation of business or to promote self-entrepreneurship, in order to induce agents to create their own jobs. In addition, developed economies coped with the aging of their populations, including company leaders, whose business will have to find a buyer who could well manage them. Furthermore, a transmission of small business on five results on a bankruptcy filing within 6 years in France or in Canada.

2

The issues in terms of ability to manage the creation, transition, and business development are primordial, both in their qualitative and quantitative dimension. It is in this context, conducive to new needs of knowledge, that emerge entrepreneurship teachings designed to inspire and enable individuals to start and to grow entrepreneurial ventures. They can be addressed in two steps.

First, a historical approach will show how teachings in entrepreneurship have evolved in their implementation based on a double dynamic of empowerment and "complication" of training programs in entrepreneurship, which seems structured around the controversy over the ability to learn to undertake business or initiate the risk culture. Second, practical teaching methods of entrepreneurship will be analyzed, making sure to highlight the multifaceted reality of innovative approaches and actions through an international benchmark conducted by the PIMREP

(I). The story of a controversy: can we train to entrepreneurship?

Historically, Myle Maces has provided the first entrepreneurship courses in Harvard in 1947 [START_REF] Katz | The chronology and intellectual Trajectory of American Entrepreneuriat Education[END_REF]. However, the 1970s mark the true genesis of a plethora of actions that affects other schools: high schools, universities (schools of business and engineering), and centers of entrepreneurship (ibid.), both nationally and internationally, starting by Anglo-Saxon cultured countries. This expansion is fueled by accreditation bodies of academic programs that enhance the efforts to encourage entrepreneurship in the design of programs, from the mid-1990s [START_REF] Adcroft | Missing the point? Management education and entrepreneurship[END_REF]. During this particularly prolific period, two significant trends have come together to shape entrepreneurship education aswe knowit nowadays. Firstly, it is a process of empowerment of entrepreneurship training programs: "entrepreneurship in universities has so far been developed as an add-on to business education, first as an elective course, then more courses, and finally as a concentration, major or program" [START_REF] Vesper | Unfinished business[END_REF]. Secondly, teaching programs are subject to growing complexity, in terms of teaching through theoretical approaches and in 3 terms of broadening perspectives. According to this interpretative framework, it is possible to distinguish several periods that stand out by their approach to entrepreneurship, which seem to be structured around the controversy over the faculty and the opportunity to learn to undertake business or to initiate the culture of risk.

"Entrepreneurs cannot be manufactured, only recognised"

In early youth of entrepreneurship education, it has been mainly treated around the issue of business creation. The teachings are based primarily on the testimony of successful business entrepreneurs (▶ Entrepreneur ;[START_REF] Fiet | The pedagogical side of entrepreneurship theory[END_REF] with the aim to share E 650 Entrepreneurship Education meaningful experiences of business creation and to highlight the elements of success of these success stories. Learn from experiences through analogies, even though each business creation isby definitionspecific, may seem paradoxical. It is this gap that interferes in a series of skeptical researchers against such teaching practices and critical of the ability to train in entrepreneurship. Most of the arguments are based on the idea that the concept of entrepreneurship education refers both to the teaching of know-how that are objectifiable and to teaching of skills (▶ Entrepreneurial Capability and Leadership). They cover two levels of analysis. The first relates to the figure of the entrepreneur himself, which economic literature has long strived to shape: attracted by risk-taking andmarked by the need for achievement, it stands out for others by his taste for independence and deviance to the familiar and established. In this context, [START_REF] Chaharbaghi | Beyond entrepreneurship: new market values[END_REF] argue that "entrepreneurs cannot be manufactured, only recognised." The second criticism concerns the deterministic and contingent dimensions of testimonies and more globally, of the overall teaching methods mobilized. Some authors suggest that entrepreneurship takes a pattern of behavior that is rooted within a specific context and is isolatedwithin that context, whereasAdcroft, Willis, and Dhaliwal (2004) state that "the entrepreneur being in the right place at the right timemay involve elements of judgement but also 4 involves elements of serendipity." As a consequence, entrepreneurship has long been considered as non-teachable because it cannot result froman optimized and infinitely reproducible approach.

"Entrepreneurship is not an innate quality, but a discipline of mind and action"

It is interesting to note that these criticisms are the seeds of a radical change in approaches to the issue of entrepreneurship in the 2000s. Indeed, beyond several empirical studies validating the specific value of entrepreneurship training, it seems to be largely in response to the criticism that academics undertake to enrich the educational treatment of entrepreneurship. The latter is more complex and therefore wins the groundwork for a separate discipline: "entrepreneurship is not an innate quality, but a discipline of mind and action that can be the appanage of a great number of students if only we train them" [START_REF] Santi | Peut-on enseigner l'entrepreneuriat?[END_REF]. In any case, entrepreneurial skills must allow students to face a new problem by drawing on a heritage of knowledge and by reconstructing from them the elements necessary for the exploration of new solutions, although they take place in a complex and dynamic environment. The process that initiates such a change of mindwhich will be only slightly challenged latergoes through a drastic evolution in the way we apprehend entrepreneurship, at the crossroads of several factors. On the one hand, the shared sense that entrepreneurship education should be divided into two approaches, both through action on the individual behaviors of students to stimulate innovative initiative and autonomy necessary for its development, that through the transmission of theoretical (and methodological) corpus necessary to analyze the essential elements of trends extension or, conversely, discontinuous elements. On the other hand, a process of empowerment of training curricula for entrepreneurship is coupled with programs that are getting more and more complex, in terms of theorization and in terms of broadening perspectives.

Multiple dynamics overlapped and fertilized entrepreneurship education

During the 2000s, trainings in entrepreneurship are subject to multiple dynamics that overlap and fertilize. The first of these consists in promote a balance between theoretical and practical lessons, which greatly contributed to the empowerment and to the recognition of the entrepreneurship education. The purpose of such theoretical approaches, known as theory-based education [START_REF] Fiet | The pedagogical side of entrepreneurship theory[END_REF], was to build a consistent and structured framework to maximize the probability of success for entrepreneurs. Specifically, they mobilize concepts and theories that have a clear applied and explanatory nature, such as agency theory, resource theory, or the economics of transaction costs (ibid.). Beyond the theoretical knowledge deepening that mainly concerns business schools, entrepreneurship trainings drastically expand the range of topics covered, as the legal aspects (idea protection), technical aspects (new product development, technological innovation), organizational aspects, marketing aspects, and especially the financial aspects (▶ Business Project; ▶ Angel Investors; ▶ Business Incubator) and individual stimulation (negotiation, leadership). Also, the entrepreneurship courses have not kept out of the profound mutations of pedagogical logic, since treatment of these last two themes went hand in hand with the shift from a passive pedagogy, in which instruction is designed as an "information delivery," to an active approach in which the purpose is to make the learner an actor of learning, which is referred to as experiential learning. This type of teachings is based primarily on computer and behavioral simulations or on creativity techniques (mind mapping, divergent thinking, brainstorming, or lateral thinking).

So far, transformations of entrepreneurship education have been drawn in broad strokes. It should be noted that they vary in space, in addition to vary over time. Indeed, if [START_REF] Solomon | The State of Entrepreneuriat Education in the United States: a National Wide Survey and Analysis[END_REF] find that business plan, case studies, and traditional teachings were still dominant educational tools in entrepreneurship education in the early 2000s, there have beenmutations since then, both in terms of depth, that enlargement of views, or in teaching 6 approaches. In this landscape renewed, what are the novelties concerning entrepreneurship education? Does the generalization of these developments have given rise to a standardization process of training in entrepreneurship? Some of the answers and lines of thought based on an international benchmark on training in innovation management led by the ParisTech Innovation Management Education Research (PIMREP) can be provided.

(II) How far have we advanced on the learning curve for teaching entrepreneurship? Findings of an international benchmark

The PIMREP network was set up at the end of 2008 and encompasses many French high schools which belong to the ParisTech network (http://www.paristech.fr/index.php/eng/). After a study in 2009 on training in innovation in ParisTech schools, the PIMREP conducted an international benchmark in 2010-2011 in the same field and that is useful here. The aim was to identify trends and foster experience sharing between the members of the network and faculties abroad. The scope of this benchmark has covered eight institutions, including business schools (HEC Montreal, NCCU), technological institutes/universities (TU Munich, ETH Zurich, KTH, KAIST), and comprehensive universities (NUS, Aalto University). This selection demonstrates a commitment to observe the most innovative teaching practices on innovation and entrepreneurship (▶ Creative Pedagogy) and also intends to embrace a broad spectrum of contexts and of cultures in order to measure their relative importance on teaching approaches adopted. Each of these institutions has been visited and has been subjected to a questionnaire structured around a specific grid analysis. Fromthis one, several trends have been identified.

Training in entrepreneurship requires diverse teaching models that range fromthe acquisition of academic knowledge to learning that recreate a context of thought and action that are close to real-life entrepreneurship situations. Given the traditions and contexts of each institution, the 7 survey shows a wide variety of experiences following two separate models, but with similar lines of development, but above all, these experiences appear more and more territorially (▶ Territory and Entrepreneurship).

An analytical grid to characterize programmes in entrepreneurship

The PIMREP network designed a system of reference to characterize the programs under study, which is built around different "educating situations" in innovation and entrepreneurship programs: awareness raising (involving presentations, testimonies, and introductive conferences), development of students' capacity for initiative (challenges, i.e., individual experiences with little assistance in terms of methodology or theory), training in methods and theories (lessons, seminar), and training in contexts of innovation (implication in entrepreneurship contexts focused on the integration of theoretical and methodological tools through tutoring). The survey consisted in analyzing the schools' degree courses with the following grid: type of teaching situations offered, type of students involved, "weight" in terms of time allotted and credits, and distribution throughout the degree courses. It aimed, on the one hand, to identify trends and typical configurations and, on the other, to identify and describe particularly interesting cases.

The architectural side of the entrepreneurship education

The first observation is that all these schools implement each of the teaching situations identified. Depending on their dominant culture (school of engineering, school of commerce, etc.), and according to other contingency factors (size, composition of the labor pool), the emphasis is placed on some of these teaching situations and, beyond, focuses on the issue of the creation or on the issue of business resumption. In addition, if the trainings in entrepreneurship are always available at each stage of university studies degree, the most ambitious educational activities, also the most demanding educational resources, are mostly related to specific curricula, as MSc, MBA, or EMBA. In this context, the master program is often called as bank storage for teachings or for case study bound for degree programs and PhD. Another finding is the fact that teaching staff are not only strongly multidisciplinary but consist of a large proportion of entrepreneurs previously or concurrently to their teaching. This proportion varies from significant to exclusive (TU Munich) and goes hand in hand with a changing role of trainers, from the role of teacher, to that of tutor, and up to the role of coach. Some workshops are self-managed by students, teaching staff being there only to guide and to answer questions from students. Please also note this revolution resonates with the emergence and spread of project-based teaching models.

The pedagogical side of the entrepreneurship education

Project-based teachings, i.e., concrete scenarios, real or simulated, based on collaborative or individual learning, greatly resonate to teaching teams. Frequently, on the basis of an original business idea, a gradual approach requires students to identify the major trends of the environment, to prioritize those most likely to have an impact on the development of the idea, and, finally, to explore possible changes or variations. In addition, on many occasions, multidisciplinary approaches (▶ Interdisciplinarity and Innovation) and those claiming to "design thinking", combining empathy and iterative process, were mentioned. However, one important trend is to give a more and more concrete perspective to teachings, in particular through the submission of actual projects by industry that can give rise to an oral assessment with the presence of top managers, also through networking with entrepreneurs from all backgrounds, and through the access to venture capitalsimulated or notof the students projects (▶ Networking Entrepreneurship), which are now major areas of improvement for trainings in entrepreneurship.

The corollary is that even if for some training in entrepreneurship, pedagogical considerations dominate, in a growing number of other cases, territorial considerations seem to prevail (bavarian silicon valley in Germany, silicon valley of user-driven innovation in Otaniemi, Finland, etc.), especially in the context of ▶ Clusters (▶ Innovative Milieux and Entrepreneurship (Volume Entrepreneurship)).

Conclusion and future directions

"Compared to many other disciplines, the discipline of entrepreneurship is in its infancy, with no standard framework or agreed upon best practices for entrepreneurial education" (Solomon 2007). This finding should be reconsidered in the light of the foregoing. Indeed, even if the learning curve for teaching entrepreneurship is still long, it seems clear that the practices of experiential learning are now well established, as well as the "learning by studying" of the early time has been replaced by the "learning by experiencing," the "learning by interacting," or the "learning by doing." New perspectives probably depends on a "territorialization" of the teachings marking a decompartmentalization of entrepreneurship training that yesterday freeing itself from the shackles of traditional disciplines, now probably tends to emancipate itself from the shackles of (higher) education. The challenge is now to articulate this education to all stakeholders that form the ecosystem of the entrepreneur (education and research institutions, national and local policymakers, entrepreneurs, private sector, etc.). Many approaches apprehend this issue, been called for by the United Nations, such asKIC (Knowledge and Innovation Communities) from the EIT (European Institute of Innovation and Technology), or the project PEEPS (Pôle de l'Entrepreneuriat Etudiant Paris Saclay -Paris student entrepreneurship center) carried by the PIMREP network.

(

  ParisTech Innovation Management Research and Education Program) network (PIMREP 2010, 2011) (▶ Higher Education and Innovation).


Martin J Gander
email: gander@unige.ch

Kévin Santugini
email: santugini-repiquet@ipb.fr

Cross-Points in Domain Decomposition Methods with a Finite Element Discretization

Non-overlapping domain decomposition methods necessarily have to exchange Dirichlet and Neumann traces at interfaces in order to be able to converge to the underlying mono-domain solution. Well known such non-overlapping methods are the Dirichlet-Neumann method, the FETI and Neumann-Neumann methods, and optimized Schwarz methods. For all these methods, cross-points in the domain decomposition configuration where more than two subdomains meet do not pose any problem at the continuous level, but care must be taken when the methods are discretized. We show in this paper two possible approaches for the consistent discretization of Neumann conditions at cross-points in a Finite Element setting.

Introduction

Domain decomposition methods (DDMs) are among the best parallel solvers for elliptic partial differential equations, see the books [START_REF] Smith | Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations[END_REF][START_REF] Quarteroni | Domain Decomposition Methods for Partial Differential Equations[END_REF][START_REF] Toselli | Domain Decomposition Methods -Algorithms and Theory[END_REF] and references therein. While classical Schwarz methods only exchange Dirichlet information from subdomain to subdomain, and converge because of overlap, non-overlapping methods like Dirichlet-Neumann, FETI, Neumann-Neumann and optimized Schwarz methods (OSMs) also exchange Neumann traces, or combinations of Dirichlet and Neumann traces between subdomains. In a general decomposition of a domain Ω ⊂ R 2 into non-overlapping subdomains (Ω i ) 1≤i≤I , naturally cross-points arise. Such cross-points, where more than two subdomains meet, do not pose any problem in a continuous variational setting, but as soon as one introduces a finite dimensional approximation, the discretization of a Neumann condition over a cross-point does not follow naturally. The earliest paper dedicated to cross-points dates, to our knowledge, back to 1986: in [START_REF] Dryja | A method of domain decomposition with crosspoints for elliptic finite element problems[END_REF], a Dirichlet-Neumann method is presented for domain decompositions with cartesian topology that can be colored with only two colors. Boundary points, including cross-points, are part of the Neumann subdomains, and all Neumann subdomains are coupled at cross-points, while Dirichlet subdomains are fully decoupled. In [START_REF] Bialecki | Nonoverlapping domain decomposition with cross points for orthogonal spline collocation[END_REF], a Krylov accelerated DDM to compute the collocation solution of the Poisson equation in a square with Hermite finite elements is studied. There are four subdomains in a 2 × 2 grid configuration, thus involving a cross-point, and theoretical convergence estimates are provided. The FETI-DP algorithm [START_REF] Farhat | FETI-DP: A Dual-Primal unified FETI methodpart I: A faster alternative to the two-level FETI method[END_REF][START_REF] Klawonn | Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients[END_REF] modifies the FETI algorithm [START_REF] Mandel | Balancing domain decomposition for problems with large jumps in coefficients[END_REF] at cross-points by replacing the dual variables by primal ones and thus avoiding the problem of Neumann conditions there. Similarly, strong coupling at cross-points is also proposed in [START_REF] Bendali | Non-overlapping domain decomposition method for a nodal finite element method[END_REF][START_REF] Boubendir | Coupling of a non-overlapping domain decomposition method for a nodal finite element method with a boundary element method[END_REF] for nodal finite elements. In [START_REF] Gander | Best Robin parameters for optimized Schwarz methods at cross points[END_REF], it was shown for optimized Schwarz methods (OSMs) in an algebraic setting that optimized Robin parameters scale differently at cross-points, namely like O(1/h), in contrast to O(1/ √ h) at interface points which are not cross-points, see also [START_REF] Loisel | Condition number estimates for the nonoverlapping optimized Schwarz method and the 2-Lagrange multiplier method for general domains and cross points[END_REF] for condition number estimates in the presence of cross-points. Cross points can also be handled in the context of mortar methods, and in very special symmetric configurations, it is actually possible for cross-points not to pose any problems, see [START_REF] Gander | On the applicability of Lions' energy estimates in the analysis of discrete optimized schwarz methods with cross points[END_REF]. The cross-point problem can be avoided entirely when using cell-centered finite volume discretizations, because they do not contain cross-points at the discrete level, see [START_REF] Cautres | The Lions domain decomposition algorithm on non-matching cell centred finite volume meshes[END_REF] for the convergence of the cell-centered finite volume Optimized Schwarz method with Robin transmission conditions; see [START_REF] Halpern | A finite volume Ventcell-Schwarz algorithm for advection-diffusion equations[END_REF] for the convergence of the cell-centered finite volume Optimized Schwarz with Ventcell transmission conditions in the absence of cross-points; and [START_REF] Gander | Optimized Schwarz at cross points: Finite volume case[END_REF] for the extension of the convergence proof to symmetric positive definite transmission operators even in the presence of cross-points.

We describe in this paper in detail two approaches to exchange Neumann traces over cross points in a finite element setting for two dimensional problems: the auxiliary variable method, and complete communication. The auxiliary variable method keeps in addition to the primal unknowns also auxiliary unknowns representing interface data in each subdomain. These auxiliary variables permit a consistent discretization of the Neumann traces at cross points while only communicating with neighboring domains sharing a boundary of non-zero one-dimensional measure. As a first main result, we show that with auxiliary variables, one can prove convergence of the discretized domain decomposition algorithm using energy estimates, which is not possible for finite element discretizations with cross-points otherwise [START_REF] Gander | On the applicability of Lions' energy estimates in the analysis of discrete optimized schwarz methods with cross points[END_REF]. A disadvantage of the auxiliary variables is that they are not necessarily converging to a limit, but this does not affect the convergence of the primal unknowns in the iteration. The complete communication method needs to exchange information with all subdomains touching at cross points, also those which touch only at a point, in order to have a consistent discretization of Neumann conditions. Our second main result is to show how to determine among the many possible splittings of Neumann traces one that minimizes oscillation.

Our paper is organized as follows: in §2, we describe on the concrete example of an OSM why the discretization of the Neumann part of the transmission condition is ambiguous at cross-points. In §3, we present the first approach on how to transmit Neumann information near cross-points using auxiliary variables, and give a general convergence proof for a nonoverlapping OSM discretized by finite elements with cross-points. In §4, we describe how Neumann information can be transmitted near cross-points by communicating among all subdomains sharing the cross point, and we propose a specific method minimizing oscillation. After our conclusions in §5, we show in Appendix A that instead of using higher order, so called Ventcell transmission conditions, see for example [START_REF] Japhet | Conditions aux limites artificielles et décomposition de domaine: Méthode oo2 (optimisé d'ordre 2). application à la résolution de problèmes en mécanique des fluides[END_REF][START_REF] Japhet | Optimized Krylov-Ventcell method. Application to convection-diffusion problems[END_REF][START_REF] Chevalier | Symmetrized method with optimized second-order conditions for the Helmholtz equation[END_REF][START_REF] Japhet | The best interface conditions for domain decomposition methods: Absorbing boundary conditions. to appear[END_REF][START_REF] Japhet | The optimized order 2 method. application to convection-diffusion problems[END_REF][START_REF] Gander | Optimized Schwarz methods[END_REF][START_REF] Gander | Optimized Schwarz methods[END_REF], one can algebraically naturally obtain such conditions from Robin conditions using mass lumping techniques in a finite element setting. This avoids the need for discretizing higher order differential operators in the tangential direction, and even works at cross-points, which is our third important result.

The discrete Optimized Schwarz Method

For the elliptic problem Lu = f in Ω, and a non-overlapping decomposition (Ω i ) 1≤i≤I , the OSM with Robin transmission conditions at the continuous level is (see for example [START_REF] Gander | Optimized Schwarz methods[END_REF]) Algorithm 2.1 (OSM).

1. Set p > 0.

2. Start with an initial guess u 0 i in each subdomain Ω i .

3. Until convergence, compute in parallel the unique solution u n+1 i to

Lu n+1 i = f in Ω i , (1)
∂u n+1 i ∂n ii ′ + pu n+1 i = ∂u n i ′ ∂n ii ′ + pu n i ′ on ∂Ω i ∩ ∂Ω i ′ . (2)
In a variational formulation of Algorithm 2.1, cross-points do not pose any problems, since they have measure zero. In a finite dimensional approximation however, using for example finite elements, the Neumann part of the Robin transmission conditions is only known as a variational quantity, as an integral over the edges connected to the cross-point. When discretizing OSM (or any DDM), there are two guiding principles:

1. The discrete mono-domain solution should be a fixed point of the discrete OSM.

2. The discrete OSM should have a unique fixed point.

We show in this section that it is not completely straightforward to follow these two principles when cross-points are present.

Geometric setting and notation

Let T be a polygonal mesh of Ω ⊂ R 2 . Let (Ω i ) 1≤i≤I be a non-overlapping domain decomposition of the domain Ω. We assume that the subdomains Ω i are polygonal, and that each cell of T is included in exactly one subdomain. Let T i be the restriction of the mesh T to Ω i , and denote by x j the vertices of the mesh T . We consider a finite element space P(T ) subset of H 1 0 (Ω) with the following properties:

1. There is exactly one degree of freedom at each vertex of T for P(T ).

2. For any edge [x j x j ′ ] of P(T ) and for any u in P(T ), u(x j ) = 0 and u(x j ′ ) = 0 implies u vanishes on the entire edge [x j x j ′ ].

Both these conditions are satisfied for P 1 elements on triangular meshes and Q 1 elements on cartesian ones. We define P(T i ) := {u |Ω i |u ∈ P(T )}. We denote the hat functions by φ j , i.e. the unique function in P(T ) such that

φ j (x j ′ ) = 1 if j = j ′ , 0 if j = j ′ ,
and by φ i;j we denote (φ j ) |Ω i . We will systematically use for subdomain indices the letter i, and separate it from nodal indices j using a semicolon.

The discretized OSM operates then on the space

V := N i=1 P(T i ).
Since a node located on a subdomain boundary may belong to more than one subdomain, we use the index i in x i;j to distinguish degrees of freedom located at the same node but belonging to different subdomains.

Discretization of Robin transmission conditions

The To investigate this problem, it suffices to study the case of the elliptic operator L := η -△, η > 0 in Algorithm 2.1. Following finite element principles, we should solve for every subdomain Ω i at every new iteration n + 1

η Ω i u n+1 i φ i;j + Ω i ∇u n+1 i • ∇φ i;j + p ∂Ω i u n+1 i φ i;j dσ(x) = f i;j + g n+1 i;j (3)
for all j such that x i;j is a node of mesh T located in Ω i , in order to find the new finite element subdomain solution approximation u n+1 i = j u n+1 i;j φ i;j . The data g n+1 i;j needs to be gathered from neighboring subdomains, satisfying (2) variationally. We denote by the matrix A i the sum of the mass and stiffness contributions corresponding to the interior equation η -△ in each subdomain Ω i ,

A i;j,j ′ := η Ω i φ i;j (x)φ i;j ′ (x)dx + Ω i ∇φ i;j (x)∇φ i;j ′ (x)dx. (4)
The matrix B cons i contains the boundary contribution p ∂Ω i u n+1 i φ i;j dσ(x), including the Robin parameter p: if the finite elements are linear on each edge, which holds for Q 1 and P 1 elements, we have the consistent interface mass matrix

B cons i;j,j ′ :=      p 3 j ′′ |x i;j -x i;j ′′ | if j ′ = j and x i;j lies on ∂Ω i , p 6 |x i;j -x i;j ′ | if [x i;j x i;j ′ ] is an edge of ∂Ω i , 0 otherwise, (5)
where the sum is taken over all j ′′ = j such that [x j x j ′′ ] is a boundary edge of T i . A lumped version of the interface mass matrix

B cons i is B lump i;j,j ′ := p 2 j ′′ |x i;j -x i;j ′′ | if j = j ′ and x i;j lies on ∂Ω i , 0 otherwise, (6)
where again the sum is taken over all j ′′ = j such that [x j x j ′′ ] is a boundary edge of T i . We explain in Appendix A why using a lumped interface mass matrix B lump i leads to faster convergence than using a consistent mass matrix B i , by interpreting the lumping process at the continuous level as introducing a higher order term in the transmission condition, see also [START_REF] Dolean | Can the discretization modify the performance of Schwarz methods?[END_REF]. This higher order term can even be optimized using a new concept of overlumping we will introduce. Note that in the context of discrete duality finite volume methods, it was shown in [START_REF] Gander | Optimized Schwarz algorithm in the framework of DDFV schemes[END_REF] that the consistent mass matrix can even completely destroy the asymptotic performance of the optimized Schwarz method, even without cross-points. This is however not the case for the finite element discretizations we consider here.

Using the matrix notation we introduced, we have to solve at each Schwarz iteration the to (3) equivalent matrix problem

(A i + B lump i )u n+1 i = f i + g n+1 i , (7)
where the vector g n+1 i is zero at interior nodes of Ω i and contains the values g n i,i ′ transmitted from the neighboring subdomains Ω i ′ on the interface nodes of Ω i . The computation of f i and g n+1 i should be done in such a way that the two guiding principles listed at the beginning of §2 are satisfied. At the continuous level, f i would just be the restriction of f to Ω i , and hence, if the continuous function f is known, one can set

f i;j := Ω i f (x)φ i;j dx.
If only f is known, then one has to choose f i in such a way that the jth component of f satisfies f j = i f i;j where the sum happens over all indices i such that x j belongs to Ω i . For the transmitted values g n i,i ′ with a finite element discretization, the Neumann contribution is defined by a variational problem. At the continuous level, if (η -△)u i = f inside Ω i , we have by Green's formula

∂Ω i ∂u i ∂n i v = η Ω i uv + Ω i ∇u∇v - Ω i f v. (8)
This formula can be used to define discrete Neumann boundary conditions: for x i;j a vertex of the fine mesh located on ∂Ω i , we define

N i;j (u i ) := η Ω i u i φ i;j + Ω i ∇u i ∇φ i;j -f i;j . (9)
At the discrete level, the no Neumann jump condition satisfied by the discrete mono-domain solution is given by i N i;j (u i ) = 0 where the sum is over all i such that x j is a boundary vertex of T i . For interface points that belong to exactly two subdomains Ω i and Ω i ′ , the Robin update is not ambiguous and we set

g n i,i ′ ;j := -N i ′ ;j (u n i ′ ) + p 2 u n i ′ ;j j ′ |x i;j -x i;j ′ |, (10)
where the sum is over all j ′ such that [x j x j ′ ] is a boundary edge of both T i and T i ′ . The g n i,i ′ ;j must be sent by subdomain Ω i ′ to subdomain Ω i , and then g n+1 i;j = g n i,i ′ ;j , since there is only one contribution from the unique neighbor Ω i ′ .

Ambiguity of the Robin update at cross-points

To see why the Robin update [START_REF] Gander | Optimized Schwarz methods[END_REF] can not be used at cross points, consider as an example the cross point x 1 belonging to subdomain Ω 1 shown in Figure 1. Following [START_REF] Gander | Optimized Schwarz methods[END_REF], to compute g n+1 1 at cross-point x 1 , one would intuitively set

g n+1 1;1 = -N 2;13 (u n 2 ) + p 2 |x 1 -x 3 |u n 2;1 -N 5;12 (u n 5 ) + p 2 |x 1 -x 2 |u n 5;1 ,
where N 2;13 is the part of N 2 located on edge [x 1 x 3 ], and likewise for N 5;12 . Unfortunately, at the discrete level, the Neumann contributions of u n 2 and u n 5 at x 1 are only known as an integral over the edges coming from x 1 . We cannot distinguish the contribution of each edge to the Neumann conditions N 2 (u n 2 ) and N 5 (u n 5 ). We only know that

N 2 (u n 2 ) = N 2;13 (u n 2 ) + N 2;14 (u n 2 ), N 5 (u n 5 ) = N 5;12 (u n 5 ) + N 5;16 (u n 5 ).
When transmitting the Robin condition at a cross point, the Neumann contribution must be split across each edge in such a way that the discrete monodomain solution remains a fixed point of the optimized Schwarz method, see principle 1 at the beginning of §2. The discrete mono-domain solution satisfies

u i;j = u i ′ ;j for all i ′ with x j in Ω i ′ , and i,x j ∈∂Ω i N i;j (u i ) = 0. ( 11
)
We should therefore split the Neumann contributions in such a way that if properties [START_REF] Gander | Optimized Schwarz methods[END_REF] are satisfied for an iterate u n i , then the transmission conditions do not change any more, g n+1 i;j = g n i;j . We show in the next two sections that such a splitting can either be obtained using auxiliary variables and communicating only with neighbors, or by communicating with all subdomains that share the cross-point.

Auxiliary variables at cross-points

We now show how to introduce auxiliary variables near the cross points. At the continuous level, we have on the interface between subdomain Ω i and Ω i ′ from (2) the identity

g n+1 i = ∂u n+1 i ∂n ii ′ + pu n+1 i = ∂u n i ′ ∂n ii ′ + pu n i ′ = - ∂u n i ′ ∂n i ′ i + pu n i ′ = -g n i ′ + 2pu n i ′ ,
since by definition

g n i ′ = ∂u n i ′ ∂n i ′ i
+ pu n i ′ and the normals are in opposite directions. At the discrete level, the same equality can be used to update the Robin transmission conditions,

g n+1 i;j = -g n i ′ ;j + 2 p 2 u n i ′ ;j j ′ |x i;j -x i;j ′ |, (12)
where the sum is over all j ′ such that [x j x ′ j ] is a boundary edge of T i . This is very useful in practice, because one then does not even need to implement a normal derivative evaluation [START_REF] Gander | Optimized Schwarz methods without overlap for the Helmholtz equation[END_REF]. At interface points which are not crosspoints, this update will give the same update as applying formula (10) using the definition [START_REF] Farhat | FETI-DP: A Dual-Primal unified FETI methodpart I: A faster alternative to the two-level FETI method[END_REF]. Therefore, if we are given the values g n i,i ′ ;j which represent the Robin transmission information sent from subdomain i ′ to subdomain i, we can compute u n+1 i by setting

g n+1 i;j = i ′ g n i,i ′ ;j (13)
and solving Eq [START_REF] Dolean | Can the discretization modify the performance of Schwarz methods?[END_REF]. The sum in [START_REF] Gander | Best Robin parameters for optimized Schwarz methods at cross points[END_REF] above is over all i ′ such that there exists an edge originating from the vertex x j that belongs to both T i and T i ′ . We then set

g n+1 i ′ ,i;j := -g n i,i ′ ;j + 2 p 2 u n+1 i;j j ′ |x i;j -x i;j ′ |, (14)
where the sum is over all j ′ such that [x j x j ′ ] is a boundary edge of both T i and T i ′ . For this we need however to store the auxiliary variables g n+1 i ′ ,i;j , because it is not possible to recover g n+1 i ′ ,i;j from u n+1 i when x j is a cross-point. Only the sum over i ′ of the g n+1 i ′ ,i;j can be recovered from u n+1 i . Since the g n i,i ′ ;j represent a split of the discrete Robin conditions, we can deduce from them a split of the discrete Neumann conditions and introduce the N n i ′ ,i;j . We set

N n+1 i,i ′ ;j := g n i,i ′ ;j - p 2   j ′ |x j -x j ′ |   u n+1 i;j , (15)
where the sum is over all j ′ such that [x j x j ′ ] is a boundary edge of both T i and T i ′ . By Eqs. ( 6), ( 9) and [START_REF] Dolean | Can the discretization modify the performance of Schwarz methods?[END_REF], we obtain

N i;j (u n+1 i ) = i ′ N n+1 i,i ′ ;j , (16)
where the sum is over all i ′ such that there exists an edge originating from x j that is a boundary edge of both T i and T i ′ .

Convergence of the auxiliary variable method

At the continuous level, one can prove convergence of OSM using energy estimates, see for example [START_REF] Lions | On the Schwarz alternating method. III: a variant for nonoverlapping subdomains[END_REF][START_REF] Després | Domain decomposition method and the helmholtz problem[END_REF]. At the discrete level, this technique fails in general [START_REF] Gander | On the applicability of Lions' energy estimates in the analysis of discrete optimized schwarz methods with cross points[END_REF], precisely because of the cross-points.

We prove now convergence of OSM in the presence of cross-points, when auxiliary variables are used. Lemma 3.1. Let f = (f j ) be a right hand side of the discretized operator η-△ with f i;j such that i f i;j = f j . Then there exist g i,i ′ ;j which are a fixed point of the discrete Optimized Schwarz algorithm with auxiliary variables near cross points.

Proof. Let u be the discrete mono-domain solution. Let u i be the restriction of u to T i . Let E i;j := {j ′′ , [x j x j ′′ ] boundary edge of T i }, E i;i ′ ;j := {j ′′ , [x j x j ′′ ] boundary edge of T i and of T i ′ }.

We use formula [START_REF] Farhat | FETI-DP: A Dual-Primal unified FETI methodpart I: A faster alternative to the two-level FETI method[END_REF] to obtain the existence of g i;j such that the solution of ( 7) are the u i . For any given cross-point node x j , we have to split the g i;j into g i,i ′ ;j that satisfy

g i;j = i ′ s.t. E i;i ′ ;j =∅ g i,i ′ ;j , g i ′ ,i;j = -g i,i ′ ;j + 2 p 2 u j j ′ ∈E i;i ′ ;j |x i,j -x i,j ′ |.
Subtracting the Dirichlet parts on both sides in the first equation, and transferring half the Dirichlet part in the second equation from the right to the left, we get

g i;j - p 2 u j j ′′ ∈E i;j |x i,j -x i,j ′ | = i ′ s.t. E i;i ′ ;j =∅ (g i,i ′ ;j - p 2 u j j ′′ ∈E i,i ′ ;j |x i,j -x i,j ′ |), g i ′ ,i;j - p 2 u j j ′′ ∈E i,i ′ ;j |x i,i ′ ,j -x i,j ′ | = -(g i,i ′ ;j - p 2 u j j ′′ ∈E i,i ′ ;j |x i,j -x i,j ′ |),
We recognize the discrete Neumann conditions, see [START_REF] Gander | Optimized Schwarz at cross points: Finite volume case[END_REF]. So the problem becomes the concrete splitting problem of Neumann conditions: given N i;j , find N i,i ′ ;j such that

N i;j = i ′ s.t. E i;i ′ ;j =∅ N i,i ′ ;j , (17)
N i,i ′ ;j = -N i ′ ,i;j . (18)
By [START_REF] Gander | Optimized Schwarz methods[END_REF], since u is the discrete mono-domain solution, we have i N i;j = 0.

For each cross-point x j , we define a graph G, whose set of vertices V (G) and set of edges E(G) are defined as

V (G) = {i, x j ∈ Ω i }, E(G) = {{i, i ′ } ⊂ V (G)
, T i and T i ′ share an edge originating from x j }.

We apply now Lemma B.1 to conclude the proof.

Theorem 3.2. The optimized Schwarz method (2.1) discretized with finite elements (3) and using auxiliary variables for the transmission conditions is convergent.

Proof. Because of Lemma 3.1, we can assume without loss of generality that f i = 0. For each subdomain Ω i , we multiply the definition of the discrete Neumann condition (9) by u i;j , then sum over all j such that x j belongs to Ω i to obtain

Ω i |∇u n+1 i | 2 + η Ω i |u n+1 i | 2 = x j ∈∂Ω i N n+1 i;j u n+1 i;j . = i ′ x j ∈∂Ω i ∩∂Ω i ′ N n+1 i,i ′ ;j u n+1 i;j
(by ( 16))

= i ′ x j ∈∂Ω i ∩∂Ω i ′ |N n+1 i,i ′ ;j + p 2 j ′′ |x j -x j ′′ |u n+1 i;j | 2 2p j ′′ |x j -x j ′′ | - |N n+1 i,i ′ ;j -p 2 j ′′ |x j -x j ′′ |u n+1 i;j | 2 2p j ′′ |x j -x j ′′ | , = i ′ x j ∈∂Ω i ∩∂Ω i ′ |g n i,i ′ ;j | 2 -|g n+1 i ′ ,i;j | 2 2p j ′′ |x j -x j ′′ |
(by ( 15) and ( 14)).

Figure 2: Error using OSM with auxiliary variables for 4 × 1 (solid) and 2 × 2 (dashed-dotted) subdomains

We now sum over all subdomains i and over the iteration index n to get

N n=0 I i=1 Ω i |∇u n+1 i | 2 + η Ω i |u n+1 i | 2 = i,i ′ x j ∈∂Ω i ∩∂Ω i ′ |g 0 i,i ′ ;j | 2 -|g N +1 i ′ ,i;j | 2 2p j ′′ |x j -x j ′′ | ≤ i,i ′ x j ∈∂Ω i ∩∂Ω i ′ |g 0 i,i ′ ;j | 2 2p j ′′ |x j -x j ′′ | .
This shows that the sum over the energy over all iterates and subdomains stays bounded, as the iteration number N goes to infinity, which implies that the energy of the iterates, and hence the iterates converge to zero.

Numerical observation using auxiliary variables

Using auxiliary variables can have surprising numerical side effects. We show in Figure 2 the error measured in L ∞ of OSM with auxiliary variables for the domain Ω = (0, 4) 2 decomposed once into 2 × 2 subdomains and once into 4 × 1 subdomains, for p = 2.0 and η = 0.0 and mesh size h = 1/10. We iterate directly on the error equations, f = 0, and initialize the transmission conditions with random values. We observe that in the presence of cross points, convergence stagnates around the machine precision, whereas without, the stagnation comes much later.

To understand these results, we need to consider floating point arithmetic, see [START_REF]IEEE. IEEE Standard for Floating-Point Arithmetic[END_REF][START_REF] Sterbenz | Floating-point computation[END_REF][START_REF] Goldberg | What every computer scientist should know about floating point arithmetic[END_REF], and in particular the machine precision macheps and the smallest positive floating point number minreal. We used in the above experiment double precision in C++ so macheps= 2 -53 ≈ 1.1• -16 and minreal≈ 4.9 • 10 -324 . Had we been computing a real problem with nonzero right hand side f , we would expect stagnation near the machine precision. However, when iterating directly on the errors, stagnation should occur much later, at the level of the smallest positive floating point number.

Ω 1 Ω 2 Ω 3 Ω 4 u 1 u 2 u 3 u 4 g 1,2 g 1,4 g 2,1 g 2,3 g 3,4 g 3,2 g 4,3
g 4,2

Figure 3: Degenerate case.

To analyze the early stagnation observed, we consider a simple model problem with 2 × 2 subdomains, see Figure 3, where there is exactly one Q 1 element per subdomain and the only interior node is a cross-point. This means the mono-domain solutions u is a scalar. We thus have Ω = (-h, h)× (-h, h), and for the subdomains

Ω 1 = (0, h) × (0, h), Ω 2 = (-h, 0) × (0, h), Ω 3 = (-h, 0) × (-h, 0), Ω 4 = (0, h) × (-h, 0
). We apply the OSM with lumped Robin transmission conditions and f = 0. Since there is only one interior node in the whole mesh, there is only a single test function φ with φ(x, y) = (1 -|x|) (1 -|y|). By Eq. ( 7), we have

A 1 = A 2 = A 3 = A 4 = ηh 2 1 0 (1 -x) 2 dx 2 + 1 0 (1 -x) 2 dx + 1 0 (1 -y) 2 dy = ηh 2 9 + 2 3 .
We use lumped Robin transmission conditions, and by ( 6), we get

B 1 = B 2 = B 3 = B 4 = p 2 h 1 0 (1 -x)dx + 1 0 (1 -y)dy = ph.
Therefore, we have by ( 7) and ( 13)

u n+1 i = g n+1 i 2 3 + ηh 2 9 + ph , i = 1, . . . , 4.
Thus, for the OSM iteration, we obtain

u n+1 1 = g n 12 + g n 14 2 3 + ηh 2 9 + ph , u n+1 2 = g n 23 + g n 21 2 3 + ηh 2 9 + ph , u n+1 3 = g n 32 + g n 34 2 3 + ηh 2 9 + ph , u n+1 4 = g n 43 + g n 41 2 3 + ηh 2 9 + ph , (19)
and by ( 14), we get

g n+1 i ′ ,i := -g n i,i ′ + phu n+1 i .
Eliminating the u n+1 i from the iteration leads to

             g n+1 1,2 g n+1 2,1 g n+1 2,3 g n+1 3,2 g n+1 3,4 g n+1 4,3 g n+1 4,1 g n+1 1,4              =             0 α -1 α 0 0 0 0 0 α -1 0 0 0 0 0 0 α 0 0 0 α -1 α 0 0 0 0 α α -1 0 0 0 0 0 0 0 0 0 0 α -1 α 0 0 0 0 α α -1 0 0 0 α 0 0 0 0 0 0 α -1 0 0 0 0 0 α α -1 0                          g n 1,2 g n 2,1 g n 2,3 g n 3,2 g n 3,4 g n 4,3 g n 4,1 g n 1,4 ,             
, where we introduced the scalar quantity

α = ph ηh 2 9 + 2 3 + ph .
Since 0 < α < 1, the ℓ ∞ norm of this iteration matrix is 1, and hence its spectral radius is bounded by 1. Note however that 1 and -1 are eigenvalues of this matrix, with corresponding eigenvectors

(-1, 1, -1, 1, -1, 1, -1, 1) T and (1, 1, -1, -1, 1, 1, -1, -1) T .
This shows that the vector of auxiliary variables will not converge to 0 in general. However, the modes with eigenvalue +1 and -1 make no contribution to the u i , see Eq. ( 19), so the algorithm will converge for the u n i , as proved in Theorem 3.2. In floating point arithmetic however, the fact that the auxiliary variables do not converge (and remain O(1) because of their initialization) prevents the algorithm applied to the error equations to converge in u n i below the machine precision, as we observed in Figure 2. Luckily, this has no influence when solving a real problem with non-zero right hand side, but must be remembered when testing codes.

Complete communication method

We now present a different approach, not using auxiliary variables, but still guaranteeing that the discrete mono-domain solution is a fixed point of the discrete OSM. This requires subdomains to communicate at cross-points with every subdomain sharing the cross-point. Most methods obtained algebraically using matrix splittings use complete communication. To get Domain Decomposition methods directly from the matrix, one usually duplicates the components corresponding to the nodes lying on the interfaces between subdomains so that each node is present in the matrix as many times as the number of subdomains it belongs to, see for example [START_REF] Gander | Best Robin parameters for optimized Schwarz methods at cross points[END_REF][START_REF] Loisel | Condition number estimates for the nonoverlapping optimized Schwarz method and the 2-Lagrange multiplier method for general domains and cross points[END_REF]. To prove convergence of this approach needs however different techniques from the energy estimates, see [START_REF] Gander | Best Robin parameters for optimized Schwarz methods at cross points[END_REF][START_REF] Loisel | Condition number estimates for the nonoverlapping optimized Schwarz method and the 2-Lagrange multiplier method for general domains and cross points[END_REF].

Keeping the discrete mono-domain solution a fixed point

Consider a cross point x j belonging to subdomains Ω i for i in {1, . . . , I} with I ≥ 3. We consider local linear updates for the discrete Robin transmission conditions at cross-points of the form

g n+1 i;j = ℓ D ((u n i;j ) 1≤i≤I ) + ℓ N ((N i;j (u i ))) 1≤i≤I ),
where ℓ D and ℓ N are linear maps from R I to R I , which can be represented by matrices,

      g n+1 1;j . . . . . . g n+1 I;j       = A D       u n 1;j . . . . . . u n I;j       + A N       N n 1;j . . . . . . N n I;j       . ( 20
)
At the cross point x j , the mono-domain solution satisfies (

u i;j = u 1;j for all i in {1, . . . , I},

I i=1 N i;j (u i ) = 0. (21)
For the mono-domain solution to be a fixed point, g n+1 i;j should be equal to g n i;j whenever conditions (21) are satisfied. Therefore, the matrices must satisfy

(A N ) ii ′ = δ i,i ′ -α i , I i ′ =1 (A D ) ii ′ = p 2 j ′′ s.t. [x j x j ′′ ] is a boundary edge of T i |x j -x j ′′ |, (22)
for some constants α i .

An intuitive Neumann splitting near cross-points

Suppose we are given I values (N i ) i=1,...,I , each representing the discrete Neumann values at x j for subdomain Ω i . Our goal is to find a splitting (N + i , N - i ) i=1,...,I such that

N i = N + i + N - i . (23)
There are obviously many such splittings. At the continuous level, the monodomain solution has no Neumann jumps at the interface between subdomains. It thus makes sense, at an intuitive level, to search for a splitting

Ω 1 Ω 2 Ω 3 Ω 4 Ω 5 N + 1 N - 2 N - 4 N + 4 Figure 4: Splitting of N i into N + i and N - i minimizing the Neumann jumps N - i+1 +N + i , see Fig. 4
. Therefore, we choose to minimize

I i=1 |N + i + N - i+1 | 2 ,
where, by convention, N - I+1 denotes N - 1 . We will see that this still does not give a unique solution, but all such splittings give rise to the same transmission conditions in the OSM discretized by finite elements.

We denote by a ∈ R I the vector with a i = N - i , which implies N + i = N ia i . We thus search for a in R I such that the function

a → I i=1 |-a i + N i + a i+1 | 2
is minimized, i.e. we want to compute the solution of

argmin a∈R I La -N 2 2 , (24)
where the matrix L = (ℓ ii ′ ) 1≤i,i ′ ≤I with

ℓ ij =      1 if i ′ = i, -1 if i ′ = i + 1 mod I, 0 otherwise,
or more explicitly

L =             1 -1 0 . . . 0 0 0 1 -
. . . 0 1 -1 -1 0 . . . 0 0 1             .
Equation ( 24) is a standard least squared problem, but its solution is not unique, since ker(L) = R[1, . . . , 1] T . If we require in addition that a is orthogonal to ker(L), then a is unique and

a = L † N , (25)
where L † is the pseudo-inverse of L, and all the solutions to ( 24) are then of the form

L † N + R[1, . . . , 1] T .
Since L is a circulant matrix, its pseudo-inverse L † is also a circulant matrix. Let (µ i ) i∈Z be I-periodic such that ℓ † ii ′ = µ i ′ -i , which implies

L † =       µ 0 µ 1 • • • µ I-1 µ I-1 µ 0 . . . . . . . . . . . . . . . µ 1 µ 1 • • • µ I-1 µ 0       .
In addition, since ker(L) = R[1, . . . , 1] T , we have

L † L = I - 1 I    1 . . . 1 . . . . . . . . . 1 . . . 1    ,
and therefore,

µ 0 -µ I-1 = 1 - 1 I and µ i -µ i-1 = - 1 I for all 1 ≤ i ≤ I.
Therefore, for all i = 0, . . . , I -1 we get

µ i = µ 0 - i I .
Moreover, range(L † ) = ker(L) ⊥ , and therefore I-1 i=0 µ i = 0, which yields µ 0 = I-1 2 . Therefore, for all i = 0, . . . , I -1,

µ i = I -1 2 - i I .
We thus obtain for the solution of the least squares problem

a i = I i ′ =1 µ i ′ -i N i ′ ,
which gives for the splitting of the Neumann values

N + i = I i ′ =1 µ i ′ -i N i ′ , N - i = N i - I i ′ =1 µ i ′ -i N i ′ .
We can use this splitting now in the OSM to exchange the Neumann contributions N + i and N - i+1 in the Robin transmission conditions, i.e., we set

(A N N ) i = -N - i+1 -N + i-1 , = -N i-1 + I i ′ =1 µ i ′ -i+1 N i ′ - I i ′ =1 µ i ′ -i-1 N i ′ , = -N i-1 + I i ′ =1 (µ i ′ -i+1 -µ i ′ -i-1 )N i ′ .
But

µ i ′ -i+1 -µ i ′ -i-1 =      1 -2 I if i ′ = i mod I, 1 -2 I if i ′ = i -1 mod I, -2 I otherwise.
Therefore, we set

(A N N ) i = N i - 2 I I i ′ =1 N i ′ .

An intuitive splitting of the Dirichlet part

We must choose a matrix A D satisfying [START_REF] Japhet | The best interface conditions for domain decomposition methods: Absorbing boundary conditions. to appear[END_REF], i.e., satisfy:

I i ′ =1 (A D ) ii ′ = p 2 j ′′ ,x j ′′ ∈∂Ω i , [x j x j ′′ ] edge of T i |x j -x j ′′ |,
There are also many possible choices for (A D ) ii ′ , but in contrast to the Neumann conditions which are only known variationally, the Dirichlet values are known on the boundary. Therefore, to split the sum of |x jx j ′′ |, we look at which neighbouring subdomain the edge [x j x j ′′ ] belongs to: if one is Ω i , and the other is Ω i ′ , then we put p|x jx j ′′ | into (A D ) ii ′ . Hence, we set

(A D ) ii ′ =      p 2 j ′′ ,x j ′′ ∈∂Ω i ∩∂Ω i ′ , [x j x j ′′ ] edge of T i |x j -x j ′′ | if i ′ = i, 0 if i ′ = i.

Numerical simulations

We do the same experiment for the complete communication method as we did for the auxiliary variable in §3.2. The results are shown in Figure 5.

As expected, for the complete communication method, convergence is also observed up to minreal for the 2 × 2 subdomain cases, i.e., when there are crosspoints. In practice, when using complete communication methods, the Robin parameters should be different at cross-points, see [START_REF] Gander | Best Robin parameters for optimized Schwarz methods at cross points[END_REF] for full details.

In this paper, we chose not to do so and use the same p at cross-points.

Conclusion

This paper contains two concrete propositions on how to discretize Neumann conditions at cross points in domain decomposition methods: the auxiliary variable method and complete communication. We showed three new results: first that the introduction of auxiliary variables makes it possible to prove convergence of the discretized methods for very general decompositions, including cross points, using energy estimates. Second that Neumann conditions can be split at cross points in a way minimizing artificial oscillation in the domain decomposition, and third, in the Appendix, that lumping the mass matrix in a finite element discretized optimized Schwarz method leads to better performance. We explained this by a reinterpretation at the continuous level, which shows a tangential higher order operator appearing. Its weight can even be optimized using the new concept of overlumping, and this can be done purely at the algebraic level, without need to discretize a complicated higher order operator. We have restricted ourselves to two spatial dimensions. In higher dimensions, in addition to cross-points, there would also be cross-edges. Both the auxiliary variables method and complete communication can be adapted to higher dimensions, which is work in progress.

A (Over)lumping of the Interface mass matrix

We start with a numerical experiment, using the consistent interface mass matrix B i from ( 5) and the lumped interface mass matrix B lump i from (6) in the Robin transmission condition of the OSM. We solve the Poisson equation with right hand side f (x, y) = 2(y(4.0-y)+x(4.0-x)) on the square domain Ω = (0, 4) 2 with 3 × 3 subdomains of equal size, and Robin parameter p = 2.0, discretized using Q 1 finite elements with mesh size h = 1/15. Figure 6 shows how the error decreases as a function of the iteration index in the OSM for these two choices. We see that initially the two methods converge at the same rate, but around iteration 40, the method using the consistent mass interface matrix slows down. We show in Figure 7 snapshots of the error distribution for selected iteration indices. We see that a highly oscillatory mode appears in the error along the interfaces. Snapshots of the error distribution using the lumped mass matrix B lump i are shown in Figure 8 for the same experiment setting. We see that with the lumped mass matrix, the high frequency error mode along the interface is much less pronounced, and convergence is faster.

In order to understand this phenomenon, we reinterpret the effect of mass lumping at the continuous level: the difference B lump i;j,j ′ -B i;j,j ′ =      p 6 j ′′ |x i;jx i;j ′′ | if j ′ = j and x i;j lies on ∂Ω i , -p 6 |x i;jx i;j ′ | if [x i;j x i;j ′ ] is an edge of ∂Ω i , 0 otherwise, looks like the discretization of a negative, one-dimensional Laplacian. This holds technically only if the step size h is constant and we are not at a cross-point. In that case, the lumped matrix actually discretizes the higher If we could modify the value of ph 2 , we would obtain a truly optimizable higher order, or Ventcell, transmission condition. This motivates the idea of overlumping: introducing a relaxation parameter ω, we define B ω i;j,j ′ := (1ω)B i;j,j ′ + ωB lump i;j,j ′ ,

and thus obtain a discretization of the transmission condition

∂u ∂n i + ω ph 2 6 ∂ 2 u ∂ 2 τ + pu. (27)
We perform now a numerical experiment with this overlumped mass matrix. For a rectangular domain Ω = (0, 4) × (0, 2) with two square subdomains Ω 1 = (0, 2) × (0, 2) and Ω 2 = (2, 4) × (0, 2), we run the OSM on Laplace's equation discretized with Q 1 finite elements and homogeneous boundary conditions, thus simulating directly the error equations. We start with a random initial guess on the interface {2} × (0, 2). We apply 50 Optimized Schwarz iterations. We do this for 10 × 10, 20 × 20, 50 × 50 and 100 × 100 cells per subdomains, with the Robin parameter p going from 1 to 20 with increment of 0.5 and the lump parameter ω going from 0 to 100 with increment of 0.25. We give the optimal p and ω in Table 1. Using the asymptotic results from [START_REF] Gander | Optimized Schwarz methods[END_REF], the optimal asymptotic choice of p for the consistent mass interface matrix should behave like p = O(1/h 1/2 ), and in the emulated Ventcell case from overlumping, we should have p = O(1/h 1/4 ) and ω = O(1/h), which is well what we observe.

We perform now a new numerical experiment with this overlumped mass matrix but in the presence of a single cross-point. For this experiment, we

5 Figure 1 :

 51 Figure 1: Example of a cross point in the decomposition

Figure 5 :

 5 Figure 5: Numerical convergence of the complete communications method for 4 × 1 (solid) and 2 × 2 (dashed-dotted) subdomains

Figure 6 :

 6 Figure 6: Convergence with lumped Robin(dashed-dotted) and consistent Robin(solid)

Figure 7 :

 7 Figure 7: Scaled error distribution at iteration 35, 50, 75, 100, 150 and 200 for OSM with consistent interface mass matrix using auxiliary variables at cross-points.

Figure 8 :

 8 Figure 8: Scaled error distribution at iteration 35, 50, 65, 80, 95, 110 for OSM with lumped interface mass matrix using auxiliary variables at crosspoints.

Table 1 :

 1 Optimal Robin parameter p and overlump factor ω with corresponding numerical convergence factor κ = exp(log( u 50 ∞ / u 0 ∞ )/50) and 2 subdomains.

	order transmission condition
	∂u ∂n i	+	ph 2 6	∂ 2 u ∂ 2 τ	+ pu.

Acknowledgements

This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02).

use the auxiliary variable method, see Table 2, and complete communication 1 , see Table 3. For a square domain Ω = (0, 4) × (0, 4) with four square subdomains Ω 1 = (0, 2) × (0, 2) and

and Ω 4 = (2, 4) × (2, 4), we run the OSM on Laplace's equation discretized with Q 1 finite elements and homogeneous boundary conditions, thus simulating directly the error equations. We start with a random initial guess on the interface {2} × (0, 4) ∪ (0, 4) × {2}. We apply 50 optimized Schwarz iterations. We do this for 10 × 10, 20 × 20, 50 × 50 and 100 × 100 cells per subdomains. We started with the Robin parameter p going from 1 to 20 with increment of 0.5 and the lump parameter ω going from 0 to 100 with increment of 0.25. For the 100 × 100 cells per subdomain with consistent Robin conditions case, we extended the search for the Robin parameter up to 24.5. For the best (overlumping) case, 2 × 2 subdomains and 10 × 10 cells per subdomain, we extended the search for the optimal p to the interval [0.1, 1] with increment of 0.1.

B A simple lemma on connected graphs

Lemma B.1. Let G be a connected graph. Let V (G) be its set of vertices and E(G) be its set of edges. Let φ be a function from

Then, there exists such that

Proof. By recurrence over the number of vertices. The lemma is trivially true when the number of vertices is 1. Suppose the lemma is true when the number of vertices is n with n ≥ 1. Let G be a connected graph with n + 1 vertices. It is well known that there exists a vertex v such that G -{v} remains connected. Since G is connected, there are edges of G originating from v. Choose w 0 adjacent to v. Set ψ(v, w 0 ) := φ(v), ψ(w 0 , v) := -φ(v) and ψ(v, w) := ψ(w, v) := 0 for all other vertices w adjacent to v. Set φ : V (G) \ {v} → R w → φ(w) if w not adjacent to v, φ(w)ψ(w, v) if w adjacent to v.

We have w φ(w) = w φ(w) = 0. We apply the lemma on φ and G -{v} which is connected and get the remaining values of ψ.