Emmanuel Thomé
email: thome@lix.polytechnique.fr

Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm

In this paper we describe how the half-gcd algorithm can be adapted in order to speed up the sequential stage of Coppersmith's block Wiedemann algorithm for solving large sparse linear systems over any finite field. This very stage solves a sub-problem than can be seen as the computation of a linear generator for a matrix sequence. Our primary realm of interest is the field Fq for large prime power q. For the solution of a N × N system, the complexity of this sequential part drops from O(N 2 ) to O(M(N ) log N ) where M(d) is the cost for multiplying two polynomials of degree d. We discuss the implications of this improvement for the overall cost of the block Wiedemann algorithm and how its parameters should be chosen for best efficiency.

INTRODUCTION

Coppersmith's block Wiedemann algorithm [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF] applies to the solving of large, sparse linear systems over finite fields. More precisely, a primary statement of the context of the algorithm would be as follows. We are given a large, sparse square matrix B of size N × N defined over K = Fq, where q can be any prime power. We know that the matrix B is singular, and we are interested in computing one or several solutions of the equation:

Bw = 0. (1)
Solving such systems is a somewhat common task [START_REF] Lamacchia | Solving large sparse linear systems over finite fields[END_REF]. We originally encountered the problem in the course of solving discrete logarithm problems over F2n using Coppersmith's index-calculus algorithm from [START_REF] Coppersmith | Fast evaluation of logarithms in fields of characteristic two[END_REF]. In its linear algebra stage, this algorithm requires finding a solution of a huge sparse linear system defined over Z/ (2 n -1)Z (in case this ring is not a field, we can infer the solution modulo 2 n -1 from the solution modulo each of its divisors via the Chinese remainder theorem if the factorization of 2 n -1 is known).

Systems as in equation (1) appear more generally in any

The algorithm of Coppersmith is an extension of an algorithm proposed by Wiedemann in [START_REF] Wiedemann | Solving sparse linear equations over finite fields[END_REF]. In Wiedemann's algorithm, we compute the sequence:

a k = x T B k y, 0 ≤ k ≤ 2N -1,
where x and y are fixed elements of the vector space K N (again, K is the base field) acting as random inputs. If B has γ non-zero coefficients per line on average, we can compute all the a k 's using O(γN 2 ) scalar multiplications in K. This computation is faster if γ is small, that is, B is sparse. In counterpart, this evaluation is sequential by nature since it involves repeated applications of B. Doing this computation in a parallel or distributed setting is infeasible without a fairly huge amount of communication between the different processors or machines taking part to the computation. This first stage of the algorithm is followed by a second stage which computes the minimum generating polynomial for the sequence a k . This polynomial yields a solution to equation [START_REF] Aho | The design and analysis of computer algorithms[END_REF]. It can be obtained with the Berlekamp-Massey or Extended Euclidean algorithm. Both of these require O(N 2 ) scalar multiplications, but subquadratic variants [START_REF] Aho | The design and analysis of computer algorithms[END_REF][START_REF] Gustavson | Fast algorithms for rational Hermite approximation and solution of Toeplitz systems[END_REF] bring O(M(N ) log N ) instead, where M(d) is the cost for multiplying polynomials of degree d. M(d) is O(d log d) with fast Fourier transform (FFT).

Coppersmith [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF] brought the following interesting possibility: instead of vectors x and y, use blocks of vectors, of size N × m and N × n, respectively, where m and n are chosen integers. One "sample" x T B k y therefore contains more information because it is made up of several scalars. This enables us to reduce the number of needed a k 's from 2N down to L = N m + N n + ε, where ε is a small additional term that shows up for technical reasons. For m = n = 1, this algorithm captures the original Wiedemann algorithm. This point of view makes it possible to distribute the computation among several machines, each of them computing for instance a given column of all the a k 's. This achieves coarse-grain parallelization of the computation of the a k 's.

Coppersmith was primarily interested in the case of F2: an n-bit machine can compute a whole line of B k y from B k-1 y in one single operation, performing n binary multiplications (that is, bitwise ANDs) at a time.

The sequence of the a k 's is made up of m × n matrices. A linear generator for this sequence (that is, a n × 1 column vector of polynomials as defined in 2.1) yields a solution to equation [START_REF] Aho | The design and analysis of computer algorithms[END_REF]. The computation of such a linear generator can be done in a variety of ways. For this purpose, Coppersmith has designed an extended version of the Berlekamp-Massey algorithm, running with complexity O((m + n)N 2 ). His algorithm is equivalent to the plain Berlekamp-Massey algorithm when m = n = 1.

We present a new algorithm for this task, adapted from the divide-and-conquer approach that yielded the HGCD (half-gcd ) algorithm from Aho, Hopcroft and Ullman [START_REF] Aho | The design and analysis of computer algorithms[END_REF] and the PRSDC (polynomial remainder sequences by divide-andconquer ) algorithm from Gustavson and Yun [START_REF] Gustavson | Fast algorithms for rational Hermite approximation and solution of Toeplitz systems[END_REF]. Our algorithm has complexity O( (m+n) 3 n M(N ) log N ), and if FFT is available over the base field, this reduces to O( (m+n) 2 n N (m+ n + log N ) log N ). Our algorithm is recursive, as HGCD or PRSDC. It can be seen as a plug-in replacement of Coppersmith's algorithm in the corresponding step of the block Wiedemann algorithm. Since both algorithms end up computing the same quantities, the analyses of the block Wiedemann algorithm by Kaltofen [START_REF] Kaltofen | Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems[END_REF] and Villard [START_REF] Villard | A study of Coppersmith's block Wiedemann algorithm using matrix polynomials[END_REF][START_REF] Villard | Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems[END_REF] apply indifferently. Therefore, the probability of success of the algorithm with respect to its random inputs x and y is not impaired by our enhancement: furthermore, this probability of success is comparable to the probabilities reached with the original Wiedemann algorithm or the Lanczos (standard or block version) algorithm with lookahead [START_REF] Coppersmith | Solving linear equations over GF(2): Block Lanczos algorithm[END_REF][START_REF] Montgomery | A block Lanczos algorithm for finding dependencies over GF(2)[END_REF][START_REF] Teitelbaum | Euclid's algorithm and the Lanczos method over finite fields[END_REF]. Section 2 addresses the problem of finding a linear generator for a given matrix sequence. Coppersmith's algorithm for this task is presented in 2.3. Existing subquadratic approaches and our new algorithm, are presented in section 3. Section 4 exposes the block Wiedemann algorithm, and shows how the computation of a linear generator for a matrix sequence yields a solution. In section 5, we discuss the overall cost of the block Wiedemann algorithm, along with the optimal value of its parameters m and n. Section 6 discusses practical concerns about the implementation of our approach.

LINEAR GENERATORS FOR MATRIX SEQUENCES 2.1 Definition

Throughout this section, we are given a m × n matrix of formal power series denoted A(X). Generators for A(X) are n-dimensional column vectors of polynomials. The degree of a column vector is defined as the maximum of the degrees in the n different entries of the vector. Let us introduce the following definition. Definition 2.1. Given two integers m and n, and a matrix

A(X) ∈ K[[X]] m×n , A(X) is linearly generated up to degree L by u(X) ∈ K[X] n if there exists v(X) ∈ K[X] m such that A(X)u(X) = v(X) + O(X L ), and deg v < deg u.
Such a criterion can be checked using only the first L coefficients of A(X). A generator up to any degree has the same definition with L = +∞.

Usage in the block Wiedemann context

In the block Wiedemann algorithm, when trying to solve (1) for a N × N matrix, we will look for a linear generator for some A(X) ∈ K[[X]] m×n . As hinted at in the introduction, A(X) will be of the form

A(X) = ∞ k=0 a k X k where a k = x T B k y,
x and y being respectively matrices of size N × m and N × n. Villard [START_REF] Villard | A study of Coppersmith's block Wiedemann algorithm using matrix polynomials[END_REF][START_REF] Villard | Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems[END_REF] bounds down (and away from zero) the probability of success of the algorithm with respect to the choice of x and y. The lower bound obtained is particularly close to 1 when the cardinality of the base field is large, or alternatively when the matrix is not too pathological : it is better not to have too many eigenvalues of high multiplicities (compared to m and n).

Since we want to focus on the linear generator computing task, which is the crux of the algorithm, we will briefly state the provided inputs and required outputs for this step. On input, it will be sufficient to have computed the first L = N m + N n + ε terms of A(X). ε can be increased to improve the probability of success. On output, we will need a generator u(X) of lowest possible degree, which will be around N n . Success will be almost certain as soon as L -deg u > N m , and the computed generator will also generate A(X) up to any degree.

Coppersmith's algorithm

Framework

In this section, we focus on accomplishing the task defined in the paragraph above, that is, to find a linear generator for A(X) of size m × n, and degree L -1, with L = N m + N n + ε. In [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF], Coppersmith transposes the problem: he finds a lefthand generator for A(X) T . This is of course equivalent. We stick to the right-hand situation. Also, the algorithm we present here is valid only in the case where m ≥ n. Validity of the algorithm depends on a non-degeneracy assumption on A(X) that will appear in 2.3.2.

Rather than working with only one candidate u(X) at a time for the linear generator of A(X), we work with several of them at a time. Hence we have matrices: candidates for u(X) are gathered in a matrix f (X) in K[X] n×(m+n) , and candidates for v(X) are gathered in g(X) in K[X] m×(m+n) (g is actually never needed in the computations, it only serves the presentation). Eventually, we will have f (X) and g(X) satisfy the following equation:

A(X)f (X) = g(X) + O(X L ), (2)
so that we hope that one or even several columns of f will bring us a generator. Aside from this one-liner equation, we introduce a quantity δj associated with each column j, 1 ≤ j ≤ m + n. This quantity is called by Coppersmith the nominal degree, as this is actually an upper bound on the degree of the coefficients in the j-th column of the polynomial f (X). The algorithm proceeds step by step, increasing a counter t, and satisfying the following equation throughout:

A(X)f (X) = g(X) + X t e(X), (E)
where e(X) ∈ K[X] m×(m+n) is the current "error" that we aim at cancelling. Each particular column of this equation will satisfy:

A(X)fj(X) = gj(X) + X t ej(X), (C1) deg fj ≤ δj, deg gj < δj, deg ej ≤ L + δj -t,
(throughout, the subscript j denotes a column). We will also enforce another condition, [X k ]P denoting the coefficient in X k of the polynomial P : rank([X 0 ]e) = m.

(C2)

Throughout the description of this algorithm, the superscript (t) may be used to stress the fact that we are concerned with the value at round t. It will be omitted in most cases however, since it is generally obvious.

Initialization

We start the algorithm at t0 = m n . All the δj's are initially set to t0. The first m columns of f are filled at random up to degree t0 -1. If we look at the first m columns of the product [X t 0 ](Af ), that is, the [X t 0 ](Afj )'s for 1 ≤ j ≤ m, we see that each of them is a random linear combination of the columns of [X 1 ]A, . . . , [X t 0 ]A. Since each [X k ]A has rank n at most, the maximal rank of the space spanned by the [X t 0 ](Afj )'s is nt0. We repeat trials until we obtain that these m columns are independent, that is, the space they span is of dimension m. This is precisely made possible by setting t0 ≥ m n . If this fails, we can try to increase t0. Otherwise, the algorithm fails as we are unable to initialize the iterative procedure. A(X) would have to be very degenerate for this to happen, so that this situation is considered unlikely. The remaining n × n submatrix of f is set to X t 0 I, where I is the n × n identity matrix. One easily checks that this initialization ensures that both conditions (C1) and (C2) hold.

Description of the iteration

Our goal is to make the gap between the δj's and t bigger and bigger, until the condition demanded in 2.2 is satisfied for some j, that is t-δj > N m . In order to help the presentation, we depict the degree pattern of each of the columns of the product A(X)f (X). Each column is represented by a line of boxes indexed from 0 to +∞. Box number k contains no symbol (or "0") if we know for sure that all the entries in the column of A(X)f (X) have their coefficient of degree k equal to zero. Otherwise, the box contains a black bullet, for instance. So let us imagine that we have the following degree patterns for the different columns of A(X)f (X), at a given round t (the sketches are merely explanatory, they do not pretend to reflect a true situation).

¡ ¢ ¡ ¡ £ ¡£ ¢£ ¤ ¡¤ ¢¤ ¡¤ ¥ ¡¥ ¡¥ ¡¥ ¢¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¢¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¢¥ ¡¥ ¡¥ ¡¥ ¦ ¦ ¦ δj t gj ej j = 1 j = 2 j = 3
Trying to go from t to t + 1, we aim at cancelling the coefficients denoted by diamonds, that is, [X t ](Af ), or [X 0 ]e. This is done through a kind of gaussian elimination, which has to obey the further requirement that the δj 's must not be trashed. We are allowed the following operations on columns:

• Exchange columns.

• Add a multiple of column j1 to column j2 provided that δj 1 ≤ δj 2 . • Multiply a column by X (this shifts the degree pattern one box to the right).

First, we sort the columns so that all the δj's are now in increasing order. Then we do gaussian elimination as usual on the columns, only adding to a column another column of lower index. This way, we zero out all but m columns of [X 0 ]e, the remaining ones being linearly independent because of condition (C2). Condition (C1) now holds at t + 1 for all but these columns. On the degree pattern picture, we have changed all but m of the diamonds into zeroes, without changing the rest of the picture (save the reordering):

§ ¡ § ¡ § ¡¡¡© ¡© ¡© ¡© ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ 0 t j = 1 j = 2 j = 3
In order to satisfy condition (C1) at t + 1 for the m columns for which it still doesn't hold, we multiply them by X. This shifts the degree pattern pictures to the right, and increases the corresponding δj 's by one. We now have:

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ t t + 1 0 0 j = 1 j = 2 j = 3
The diamonds have been kept in the picture, they are now part of [X t+1 ](Af ). Since these are m independent columns, this ensures that condition (C2) holds at round t+1. All the work we have done can be expressed by the multiplication on the right of equation E by a (m + n) × (m + n) matrix that we denote P (t) . Since the relevant input to this iteration consists of only [X t ](Af ) and (δ1, . . . , δm+n), we have given a constructive proof to the theorem below. The C-like pseudocode 2.1 summarizes the procedure.

Theorem 2.2. If conditions (C1) and (C2) hold at round t, there is an algorithm ALGO1 that, knowing [X 0 ]e (t) and (δ

(t) 1 , . . . , δ (t) m+n ), computes a (m + n) × (m + n) matrix P (t) along with integers (δ (t+1) 1 , . . . , δ (t+1) m+n ) such that: f (t+1) = f (t) P (t) , g (t+1) = g (t) P (t) , e (t+1) = e (t) P (t) 1 X ,
and the δ (t+1) j 's satisfy conditions (C1) and (C2) at round t + 1. Furthermore, we have j δ

(t+1) j -j δ (t) j = m. Algorithm ALGO1 INPUT: A m × (m + n) matrix [X 0 ]e, m +
);j0++) if ([X 0 ]ei,j 0 !=0 && busy[j0]==0) break; busy[j0]=1; /* [X 0 ]ei,j 0 is the pivot */ for(j=j0 + 1;j<=(m + n);j++) { λ=[X 0 ]ei,j/[X 0 ]ei,j 0 ; /* subscripts denote columns */ [X 0 ]ej=[X 0 ]ej -λ[X 0 ]ej 0 ; Pj=Pj -λPj 0 ; } } /*

Termination

Now let us consider the average value, say δ of the δj's. It increases by m m+n each time t increases by 1. Therefore, the difference t -δ obeys:

t -δ = t -(t0 + (t -t0) m m + n ) = (t -t0) n m + n .
We can see that for t > N m + N n + t0, the difference exceeds N m , so there exists at least one j for which t -δj > N m . The condition demanded in 2.2 is therefore satisfied by the column fj (X), and we expect it to yield a solution to our linear system. Actual termination can be detected another way. We saw in 2.2 that the desired fj (X) is expected to be a generator up to any degree. If one of the columns of f (X) becomes so at some round t, we will notice that the corresponding column of [X 0 ]e is zero at the beginning of round t + 1. If such a column is zero, then the corresponding fj carries over untouched to the next round. If on several successive rounds, the column of [X 0 ]e associated to a given column of f is zero, then fj is likely to be a linear generator for A(X) up to any degree, so this is probably the quantity we are looking for. In order to check for termination this way, we need to have L a bit above N m + N n . Coppersmith writes

L = N m + N n + O(1)
, gathering this margin in the O(1) term that is not thoroughly investigated. He rather relies on the fact that the algorithm practically does produce a solution soon after t exceeds N m + N n . We stick to that approach, since the analysis of correctness of the block Wiedemann algorithm if far beyond our scope here, and has already been addressed in [START_REF] Kaltofen | Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems[END_REF][START_REF] Villard | A study of Coppersmith's block Wiedemann algorithm using matrix polynomials[END_REF][START_REF] Villard | Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems[END_REF].

As a side note, as long as we have not reached the case where (t -δj ) > N m somewhere, all the δj's are expected to be (almost) equal to δ. Therefore, we might expect that when the average difference exceeds N m , as many as n columns are candidates for producing a solution (but this can be less).

SUBQUADRATIC APPROACHES 3.1 Existing algorithms

Many algorithms exist for computing linear generators for matrix sequences. Coppersmith's, like most of these, has a quadratic complexity. Recall that we are looking for a generator up to degree L = N m + N n +ε. If we detail the complexity in terms of N , m and n, we obtain O((m + n)N 2 ). Other, older, algorithms have sometimes a subquadratic version. These are the "power Hermite Padé solver" by Beckermann and Labahn [START_REF] Beckerman | A uniform approach for the fast computation of matrix-type Padé approximants[END_REF] in O( (m+n) 2 m n M(N ) log N ), and the algorithm of Bitmead, Anderson and Morf [START_REF] Bitmead | Asymptotically fast solution of Toeplitz and related systems of linear equations[END_REF][START_REF] Morf | Doubling algorithms for Toeplitz and related equations[END_REF] for Toeplitzlike matrices, in O((m + n) 2 M(N ) log N ). While these algorithms are asymptotically faster than Coppersmith's, they do not seem to have been tried for large experiments with the block Wiedemann algorithm, like [START_REF] Kaltofen | Distributed matrix-free solution of large sparse linear systems over finite fields[END_REF]. Apart from the relative simplicity of Coppersmith's approach compared to other algorithms, two points might explain why this quadratic algorithm can be seen as having the edge on subquadratic alternatives. First, it requires no randomization, whereas this is needed for the method of Bitmead, Anderson and Morf. Second, the "big O" in the complexity O((m + n)N 2 ) hides no big constant. Counting the exact number of operations required, Coppersmith's algorithm requires no more than m+n 2 N 2 scalar multiplications (see [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF]). On the other hand, subquadratic algorithms always require the use of fast polynomial arithmetic using FFT. Added to the increased complexity in terms of m and n, it turns up that the speedup obtained from this algorithms is probably too small for realistic examples.

In the following subsection, we give another try, providing a subquadratic version of Coppersmith's algorithm. It shares with the original algorithm the absence of need for randomization, as well as the lower complexity in terms of m and n compared to other existing algorithms, provided that m and n remain small, say O(log N ): the complexity of our algorithm is O( (m+n) 3 n M(N ) log N ), and this lowers down to 4(m+n) 2 n N log 2 N + 3(m+n) 3 n N log N scalar multiplications in a ring that supports FFT arithmetic (log denotes the logarithm in base 2). For small m and n (compared to log N ), this is asymptotically better. We will show the importance of this in section 5.

An accelerated version of Coppersmith's algorithm

In Coppersmith's algorithm, the quadratic cost comes from the evaluation of [X t ](Af ) at each round t, for t0 ≤ t ≤ L.

Our divide-and-conquer approach aims at replacing these numerous coefficient computations by a few big polynomial multiplications, in order to take advantage of fast multiplication algorithms, like FFT. In order to do this, we make an extensive use of theorem 2.2. Specifically, the fact that the only knowledge of [X t ](Af ) -that is, [X 0 ]e -is necessary will prove to be crucial. In fact, if one knows the first k coefficients of e (t) (X), this information is enough to compute P (t) up to P (t+k-1) , without updating f (X). Let us formalize these considerations.

Definition 3.1. A k-context is a pair of the form E = (e(X), ∆) corresponding to some stage of the iterative algorithm explained in section 2.3 where ∆ = (δ (t) j )j and e(X) are known up to degree k -1. A context without precision is the same pair with full knowledge of e(X). Proof The proof is easy by induction. It is enough to observe that at round t, the computed matrix P (t) is such that e (t) P (t) ≡ 0 [X]. Then, e (t+1) is e (t) P (t) 1 X . ∆ (t+1) follows also from P (t) since one checks easily that:

δ (t+1) j = max i {δ (t) i + deg P (t) i,j }.
By an abuse of notation, we denote the latter ∆ (t) P (t) . Together, e (t) P (t) 1

X and ∆ (t) P (t) form a (k -1)-context. Generalization of this step from t to t + 1 to the result of the theorem is trivial.

With this formalism, it becomes clear that our main point of interest is the quantity π (0,L-t 0 )

E (t 0 )
where E (t 0 ) = (e (t 0 ) , ∆ (t 0 ) ) is the initial context. Once π (0,L-t 0 )

E (t 0 )
is known, then all the columns of f (t 0 ) (X)π (0,L-t 0 )

E (t 0 )
satisfy the equation E with t = L, and since we know the δj's, we can pick a column that suits the requirements of subsection 2.2.

From theorem 3.3, we design an algorithm whose task is the computation of π

(0,b) E from a given b-context E. It is described in figure 3.1.
In that piece of pseudo-code, ALGO1 is the algorithm in 2.1. The recursive algorithm is named MSLGDC from "matrix sequences linear generator by divideand-conquer". It will be applied to the (L -t0)-context E (t 0 ) = (e (t 0 ) , ∆ (t 0 ) ).

Complexity of MSLGDC

Our algorithm requires two non-trivial (more than linear) operations at each recursion level. These are: eM ← (eπL mod X b ) div X Proof What this theorem says is that the generic result is not only specified using the complexity of FFT for M(d), but that we also improve the complexity with respect to m and n. Let us show how this is obtained.

We refer to [10, chapter 8] for an introduction to fast Fourier transform. In a few words, FFT relies on the one hand on the ability to efficiently compute the evaluation (discrete Fourier transform, DFT) of a polynomial at a bunch of pointsthe 2 k -th roots of unity for some k -and on the other hand on the ability to interpolate equally fast a polynomial given its values at those same points (inverse DFT, or IDFT, operation). The DFTs of two polynomials can be multiplied pointwise (at a linear cost in the number of points) to obtain the DFT of the product polynomial. The latter can then be recovered by an IDFT operation.

Here, our goal is to compute products of polynomial matrices. This is a simple generalization of the principle above: one computes the DFT of each entry in the matrices involved (e, πL, and πR). These form the matrix DFTs e, πL, and πR (these are matrices of scalar sequences, or also sequences of scalar matrices). These DFTs can be multiplied point-wise, involving one scalar matrix multiplication per point, to obtain the (matrix) DFTs of the products: eM , and π.

The number of points at which the DFTs are computed is actually driven by the number d of unknown coefficients in the product: we take the smallest power of 2 above d, so in any case less than 2d. It follows from [10, thm 8.15] that the cost of the computation of the DFTs is below d log d multiplications in K (same for IDFTs). The degrees considered imply that we need transforms using b points at most for the computation eM ← (eπL mod X b )divX b 2 , and transforms using 2m m+n b points at most for the computation of π ← πLπR. Upper bounds on the time required to compute all the transforms are summarized hereafter (of course, the transform of πL needs not to be computed twice, so we keep the largest figure).

DFT :

e → e M1m(m

+ n) b 2 log b 2 , DFT : πL → πL M1(m + n) 2 m m + n b log( m m + n b), IDFT : eM → eM M1m(m + n) b 2 log b 2 , DFT : πR → πR M1(m + n) 2 m m + n b log( m m + n b), IDFT : π → π M1(m + n) 2 m m + n b log( m m + n b).
Additionally, the matrix products involved by the pointwise multiplication of the DFTs yield a complexity of m(m + n) 2 bM1 and 2m(m + n) 2 bM1 operations, respectively. Summing these up, we obtain the announced results. The cost equation for the algorithm MSLGDC for order b is:

C(b) =2C b 2 + 4M1m(m + n)b log b+ 3M1m(m + n) 2 b + O((m + n) 2 b), hence C(b) = 4M1m(m + n)b log 2 b + 3M1m(m + n) 2 b log b + O((m + n) 2 b log b), as claimed.
Plugging into this the parameters used for the block Wiedemann algorithm, namely L = m+n mn N + O(1), we obtain:

C(L) = 4M1 (m + n) 2 n N log 2 N + O((m + n) 3 N log N ).
So the actual * speedup obtained when we compare to Cop-

persmith's version is nN 8(m + n) log 2 N
, as long as m and n stay relatively small.

BLOCK WIEDEMANN ALGORITHM

Now that we have extensively discussed the available tools for finding linear generators of matrix sequences, we will see how they plug into the block Wiedemann algorithm. As told before, we are now interested in the polynomial matrix:

A(X) = L-1 k=0 a k X k , with a k = x T B k y,
where x and y are respectively N × m and N × n matrices.

The coefficients a k of A(X) are m × n matrices. Not surprisingly, we look for a linear generator of these in order to * However, so many parameters are involved that this estimate is not really sharp.

obtain a solution. The number L of computed coefficients of A(X) is here N m + N n +ε. In other words, we stick to the pragmatic approach that works well in practice: compute A(X) up to far enough so that heuristics let us believe that we will obtain a solution. In order to ensure that a solution will be produced, it is necessary to actually set y to Bz, where z is a random vector block. From now on, our context will be the one described in this paragraph. The quantities B, N , L, m, n, x, z, and y will be fixed, corresponding to the aforementioned.

The computation of the coefficients of A(X), which will be named "stage BW1", is done sequentially. A vector variable Y is repeatedly updated by Y ← BY , and dot products x T Y are computed at each step. Once we have A(X) at our disposal, we can infer a linear generator for this matrix sequence, using the tools we have already mentioned (for example, we can use the MSLGDC algorithm). This will be the step BW2 of the block Wiedemann algorithm. We quickly show that such a linear generator yields a solution to the system Bw = 0 with high probability. Let us first recall the condition (C1) that is satisfied at each round by the different columns of the relevant matrices:

A(X)fj(X) = gj (X) + X t ej(X), (C1) deg fj ≤ δj, deg gj < δj, deg ej ≤ L + δj -t.
We detail now why the context given in subsection 2.2 is appropriate in order to find a solution of the equation Bw = 0. At a given round t, considering the quantities in the equation above, the product A(X)fj(X) has zero coefficients for degrees δj up to t -1. In other words, we have:

∀s, 0 ≤ s < t -δj, δ j k=0 ([X s+δ j -k ]A)([X k ]fj ) = 0, i.e. δ j k=0 x T B s+δ j -k y[X k ]fj = x T B s δ j k=0 B δ j -k y[X k ]fj = 0.
Then, the quantity δ j k=0 B δ j -k y[X k ]fj is orthogonal to as many as m(t -δj) vectors: the vectors (B T ) s xi where the xi's are the columns of x. Eventually, namely when (t-δj ) > N m , m(t-δj) exceeds N . If the space spanned by the (B T ) s xi has maximal dimension (this is our heuristic argument that we hope will hold), our quantity is then zero. If we replace y by Bz in the previous equation, we obtain:

B δ j k=0 B δ j -k z([X k ]fj ) = 0. If this equation holds, w = δ j k=0 B δ j -k z([X k ]fj ) is a solu- tion if it is non-zero.
In case it is zero but as a "polynomial" in B, w has a non-zero valuation ν, then we have

B 1+ν ŵ = 0 for ŵ = δ j -ν k=0 B δ j -k z([X k ]f ),
and some B s ŵ is guaranteed to be a solution if ŵ = 0. The computation of ŵ and s such that B s ŵ is a solution is referred to as step BW3.

COMPLEXITY ANALYSIS AND OPTI-MIZATION

Having a block version of the Wiedemann algorithm introduces a new flexibility: we can play with parameters m and n. Nevertheless, these parameters do have some optimal value that we'd better use: obviouly, the bigger m and n, the shorter the computation of the a k 's, but also the more tedious the computation of a solution from these. We will therefore detail the complexity of the different stages (BW1, BW2, BW3) of the algorithm with respect to m, n, and N . For step BW2, we will give complexities for both Coppersmith's and our algorithm.

The block approach allows coarse grain parallelization (see [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF] or [START_REF] Kaltofen | Distributed matrix-free solution of large sparse linear systems over finite fields[END_REF]). In a parallel or distributed setting, distributing the columns of a vector block Y across several machines allows to compute Y ← BY in a real time that does not depend on n (if we have that many machines available). Steps BW1 and BW3 can take advantage of this, and therefore the real time is the appropriate measure for the algorithm. Now the question is, provided that the hardware we have access to allows us several values for m and n, how to choose them in order to achieve the lowest total real time ? This question is answered in theorems 5.3 and 5.4. Since m and n are typically limited by the available hardware, it is reasonable to assume that m and n are bounded by a constant. Therefore, at least for the complexity of step BW2 using our recursive algorithm, we will incorporate this in the complexity equation, and focus on the dominating term.

In order to obtain complexity measurements we introduce two important constants, M0 and M1. M0 stands for the time needed for multiplying a coefficient of the matrix B (typically of size equal to one machine word) by an element of K, while M1 is the time needed for multiplying together two elements of K. Also, we denote by γ the average number of non-zero entries of rows of B (B is expected to be sparse, so γ is small). We do not take additions into account in our analysis. This is an excessive simplification over small fields like F2, but reasonable over larger fields. We prove the following results:

Theorem 5.1. The different steps of the block Wiedemann algorithm require the following real time: BW1 (γM0 + mM1) m+n mn N 2 (see also remark 5.2 below). BW2 M1 m+n 2 N 2 + O(N ) using Coppersmith's algorithm 4M1 (m+n) 2 n N log 2 N +O(N log N ) using our algorithm (provided that m and n are bounded). BW3 γM0 1 n N 2 .

Proof As said before, step BW1 is accomplished by repeating the operation Y ← BY , where Y = y initially. This sums up as nL matrix times vector product, but since the n columns of Y are assumed to be treated separately, the real time is the time needed for L applications of B: γN M0L. Furthermore, we have to add the cost of the dot products (xi T Yj). These cost mM1N at each step, which brings the result (see also remark 5.2 below). The second result follows. As for step BW2, the result follows from [START_REF] Coppersmith | Solving linear equations over GF(2) via block Wiedemann algorithm[END_REF] for Coppersmith's algorithm, and from theorem 3.4 for our algorithm, specialized to m and n bounded. The complexity of step BW3 follows from the fact that as a "polynomial" in B, ŵ has degree N n .

Remark 5.2. In practice, the real time needed for step BW1 can be lowered down to γM0 m+n mn N 2 by using vectors of the canonical basis for the xi's. Indeed, the dot products which account for the mM1 m+n mn N 2 term become trivial (1 operation instead of mM1N with random x's). It should be noted however that when we do so, x is no longer truly random, and the correctness analyses of [START_REF] Kaltofen | Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems[END_REF][START_REF] Villard | A study of Coppersmith's block Wiedemann algorithm using matrix polynomials[END_REF][START_REF] Villard | Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems[END_REF] do not necessarily apply.

We will now write down the overall cost of the block Wiedemann, in light of the theorem above. Our analysis is valid over fields other than F2, since numerous possible tricks in that case tend to shape the things differently.

Proof

If we write down the total time for the block Wiedemann, following theorem 5.1, we obtain:

W = γM0 m + n mn N 2 + M1 m + n 2 N 2 + γM0 1 n N 2 , W = (γM0 2λ + 1 λ 1 n + M1 λ + 1 2 n)N 2 for m = λn.
If we minimize W for a given λ, the optimal values Wopt and nopt are:

nopt = γM02(2λ + 1) M1λ(λ + 1) , Wopt = 2N 2 γM0M1 (2λ + 1)(λ + 1) 2λ .
The minimum value of the quantity (2λ+1)(λ+1) 2λ is obtained for λ = 1 √ 2 , but since we are restricted to λ ≥ 1, λ = 1 is the most appropriate choice. Specializing nopt and Wopt to λ = 1 yields the announced values.

Theorem 5.4. Using algorithm MSLGDC for step BW2, the real time for the block Wiedeman algorithm is lowest for

mopt = nopt = 3γM0N 16M1 log 2 N
. The total time needed in this case is Wopt = 8 3γM0M1N √ N log N .

Proof As before, this follows from theorem 5.1. W writes down as (again using m = λn):

W = γM0 2λ + 1 λ 1 n N 2 + 4M1(λ + 1) 2 nN log 2 N,
Following the same reasoning as before, we obtain the best ratio between m and n for λ = 1 (since we are restricted to λ ≥ 1), and hence the announced Wopt and nopt.

It should be noted that theorem 3.4 yields a low complexity for step BW2 with respect to m and n because of the introduction of the FFT which hides the cubic dependency on m + n. If we had used algorithm MSLGDC with a generic multiplication algorithm, Wopt would certainly be higher.

The optimal value nopt is not necessarily acceptable, because we are limited by the available hardware. We will see in the following section that for realistic examples, nopt is still reasonable.

IMPLEMENTATION CONCERNS 6.1 Interest of the block version

The consequences of our analysis depend on the base field. We excluded F2 from our scope because in that case, precise time estimates are extremely variable depending on the implementation (for example, additions can no longer be neglected versus multiplications, as we do here). The best choice for m and n is almost certainly the wordsize w of the machine (in fact, we can regard this as having M0 and M1 divided by w: as many as w multiplications in K can be done at a time). It is pretty hard to tell without actually trying on real experiments whether it is worthwhile to set m and n to something else (an integer multiple of w for instance). Since our code is focused on large fields, we did no such experiments.

Over large fields, like in the linear algebra problems encoutered in the course of discrete logarithm problems [START_REF] Odlyzko | Discrete logarithms in finite fields and their cryptographic significance[END_REF], the problem is quite different. First, M1 is now typically much bigger than M0: indeed, the coefficients of the input matrix are usually kept bounded to a size of one machine word (see below), so when a generic element of K has size about ten words, M0 is a dozen machine cycles, whereas M1 can reach several hundreds machine cycles. Therefore, the second part of the algorithm could end up dominating the overall cost. If we include these considerations in the computation of the optimal value nopt for the parameters m and n, we see that if one uses Coppersmith's version of step BW2, nopt is very small (sometimes hardly above 1). In other words, there is not much interest in using the block version of the Wiedemann algorithm. On the other hand, our algorithm MSLGDC yields a bigger optimal value. Since we must ensure that the cubic term in (m + n) stays small, numerical values are hard to provide, and depend on a thorough implementation. As a rough estimate, we consider that today's biggest linear systems over large fields can take advantage of the method. For example, for a matrix of size 250, 000 × 250, 000 defined over a field of size 1000 bits with an average of 20 non-zero entries per row, the optimal value for nopt with algorithm MSLGDC is 5, whereas we obtain 1 for the quadratic counterpart. The overall speedup obtained is between 3 and 4, but not counting the cubic complexity in m + n. It is not likely that more "reasonable" systems can benefit of this method for now.

Influences on input filtering

Perhaps more important, our computations have a very interesting consequence on the input given to the block Wiedemann algorithm, when it comes out of a structured gaussian program [START_REF] Pomerance | Reduction of huge, sparse matrices over finite fields via created catastrophes[END_REF], or more generally any filtering stage like in [START_REF] Cavallar | Strategies in filtering in the number field sieve[END_REF]. Such algorithms aim at reducing the matrix size with minimal fill-in -we want the matrix to remain sparse -, as far as this is possible. Their output is then given to an algorithm like Wiedemann's, or alternatively a block version. Depending on the context, reduction rates going from one third to one tenth are achieved. When the base field is not simply F2, the matrices given on input to the filtering program have small coefficients. Therefore, coefficients of the matrix are stored in a single machine word and not allowed to go beyond this in order to reduce the memory storage. In the course of this filtering, one usually arranges for stopping it as soon as the estimated subsequent cost (of the Wiedemann algorithm for instance) starts to rise up again, after having been diminished. See [START_REF] Weber | The solution of McCurley's discrete log challenge[END_REF] for an example of such an estimation. The estimated cost is generally something like γN 2 . As the filtering proceeds, γ grows while N gets smaller.

Our point here is that when using the block version with optimal parameters m and n, we can focus on the quantity √ γN 2 instead. This means that we are able to continue the gaussian elimination a bit further. If we plan to use our subquadratic alternative, the relevant figure is N √ γN log N , but this is only valid as long as m and n remain small. Experiments with matrices coming from discrete logarithm problems showed that the filtering can actually be brought substantially further.

Memory requirements

We hardly addressed the memory concerns for the block Wiedemann algorithm. However, these are really important because the memory storage needed for the matrix B is usually huge. For this very reason, parallelization or distribution is hampered by the relative scarcity of computing resources available that can handle such a big object: if we plan to distribute step BW1 among several machines, these have to work on a local copy of the matrix B. This is why having nopt reasonable was crucial. As a side note, we would like to stress the fact step BW2 does not need the matrix B, so the increased memory requirements of algorithm MSLGDC compared to Coppersmith's algorithm are not very important.

An important point in the ability explained in the previous subsection to carry out the filtering or structured gaussian elimination further than what we used to is that this helps in reducing the storage needed for B: the memory requirements for step BW1 are driven by two quantities: γN for the matrix size, and N for the size of all the linear storage data and such. Continuing the filtering further than before makes these quantities lower, and therefore the algorithm could become more usable if its memory requirements are reduced.

CONCLUSION

We believe that our study of the block Wiedemann algorithm helps greatly in making it more practical over large fields, and also gives some insights on its characteristics in terms of running time and such. In certain settings, we can expect the block Wiedemann algorithm to become very efficient and competitive, but still at sizes that may seem huge for now. Although our original interest was dealing with matrices coming from discrete log problems, this approach could help to advocate for the use of the block Wiedemann algorithm in other contexts where a (very) large sparse linear system over a large finite field shows up.

I would like to thank François Morain who helped me in preparing this paper. I am also grateful to Gilles Villard and the anonymous referees for their valuable questions and comments.

Definition 3 . 2 .

 32 Generalizing the definition from 2.3.3, if E is a context corresponding to round number t of the algorithm in 2.3, we call π(a,b) E the following (m+n)×(m+n) matrix: π (a,b) E = P (t+a) . . . P (t+b-1) , where the P (t+s) are the matrices computed from step 2.3.3 at the corresponding rounds after t. Theorem 3.3. A given k-context E determines completely any π (a,b) E as long as a ≤ b ≤ k. If E corresponds to round t of the algorithm, say E = E (t) , then a (k-b)-context E (t+b) follows from the computation of π (0,b) E .

b 2 , 2 , 2 ,Program 3 . 1 : 2 . 2 )Theorem 3 . 4 .

 222312234 and π ← πLπR. Algorithm MSLGDC INPUT: A b-context E = (e, ∆). OUTPUT: π (0,b) E . { if b==0 return Im+n; (eL, ∆L)=(e mod X b ∆); πL=MSLGDC((eL, ∆L)); (eM , ∆M )=(eπL mod X b div X b ∆πL); P =ALGO1((eM , ∆M )); πL=πLP ; if (b > ( b 2 + 1)) /* i.e. b > 2 */ { (eR, ∆R)=(eM P mod X b 2 div X, ∆M P ); πR = MSLGDC((eR, ∆R)); π = πL × πR; return π; } else return πL; } Recursive algorithm for computing π (0,b) E Of these polynomials, e has degree b, and πL and πR have degree m m+n b Using a generic multiplication algorithm requiring M(d) operations to multiply two polynomials of degree d, these operations would cost m(m + n) 2 M(b) and (m + n) 3 M( m m+n b , that is, at most 3 2 m(m + n) 2 M(b). Now, if we use fast Fourier transform (FFT), we can do much better: If K supports FFT (see [10, chapter 8]), the two operations above can be achieved in time 4M1m(m + n)b log b + 3M1m(m + n) 2 b + O((m + n) 2 b), where M1 is the cost of a multiplication in K. This yields a complexity bound for algorithm MSLGDC with a b-context of 4M1m(m+ n)b log 2 b + 3M1m(m + n) 2 b log b + O((m + n) 2 b log b)).

Theorem 5 . 3 .

 53 Using Coppersmith's algorithm for step BW2, the real time for the block Wiedeman algorithm is lowest for mopt = nopt = 3γM0 M1 . The total time needed in this case is Wopt = 2 √ 3γM0M1N 2 .

  n integers δ1, . . . , δm+n. OUTPUT: P as defined by theorem 2.2.

	{	P =Im+n;	/* the identity matrix */
		Reorder columns so that δ1 ≤ . . . ≤ δm+n, updating P accordingly;
		/* Gaussian elimination */
		for(j0=1;j0<=(m + n);j0++) busy[j0]=0;
		for(i=1;i<=m;i++) { for(j0=1;j0<=(m + n


Valentin Bonzom

Matteo Smerlak

Bubble divergences from cellular cohomology

Keywords: powercounting, topological gauge theory, bubble divergence, spinfoam models

We consider a class of lattice topological field theories, among which are the weak-coupling limit of 2d Yang-Mills theory, the Ponzano-Regge model of 3d quantum gravity and discrete BF theory, whose dynamical variables are flat discrete connections with compact structure group on a cell 2-complex. In these models, it is known that the path integral measure is ill-defined in general, because of a phenomenon called 'bubble divergences'. A common expectation is that the degree of these divergences is given by the number of 'bubbles' of the 2-complex. In this note, we show that this expectation, although not realistic in general, is met in some special cases: when the 2-complex is simply connected, or when the structure group is Abelian -in both cases, the divergence degree is given by the second Betti number of the 2-complex.

I. INTRODUCTION

One road to the quantization of backgroundindependent field theories, such as Schwarz-type topological field theories or general relativity, is the spinfoam formalism (although outdated, [START_REF] Baez | An Introduction to spin foam models of quantum gravity and BF theory[END_REF][START_REF] Perez | Spin Foam Models for Quantum Gravity[END_REF] remain good reviews; see also [START_REF] Freidel | Spin foam models and the classical action principle[END_REF], and [START_REF] Engle | Flipped spinfoam vertex and loop gravity[END_REF][START_REF] Freidel | A New Spin Foam Model for 4d Gravity[END_REF] for more recent developments). In this approach, the Feynman path integral is realized as a sum of amplitudes associated to oriented two-dimensional cell complexes, aka foams.

Spinfoam amplitudes, however, are plagued by bubble divergences, which arise notably in the topological models whose dynamical variables are flat G-connections, with G a compact Lie group. This includes the weak-coupling limit of 2d Yang-Mills theory, the Ponzano-Regge model of 3d quantum gravity and discrete BF theory in higher dimensions. In these instances, the foam Γ is the 2skeleton of the cell complex dual to the triangulated spacetime manifold. 1 Here, however, we will not restrict ourselves to these cases, and consider arbitrary foams. This is relevant both from the perspective of canonical loop quantum gravity, where foams are interpreted as 'gauge histories' of spin-networks [START_REF] Perez | Spin Foam Models for Quantum Gravity[END_REF], and of group field theory [START_REF] Freidel | Group Field Theory: An Overview Int[END_REF][START_REF] Oriti | The group field theory approach to quantum gravity in Oriti[END_REF], where foams are generated as Feynman diagrams of a certain auxialiary field theory: in both cases, the one has to deal with foams which are not dual to triangulated manifolds of the relevant dimension.

Although various regularization schemes have been proposed, 2 the structure of these divergences has not been elucidated so far. In particular, no general result is known concerning the divergence degree of a foam Γ: 1 In these cases, the dimension of the spacetime manifold is equal to the number of faces (2-cells) adjacent to each edge (1-cell) of Γ. 2 For example, the Turaev-Viro and Crane-Yetter models, in three and four dimensions respectively, make use of a quantum group in the place of G.

the number Ω(Γ, G) such that

0 < lim Λ→0 |Λ -Ω(Γ,G) Z Λ (Γ, G)| < ∞ (1)
where Λ is a suitable cutoff, and Z Λ the corresponding regularized amplitude. Upon inspection, it appears heuristically that Ω(Γ, G) is related to the number of 'bubbles' of Γ -independent sets of faces forming closed surfaces [START_REF] Perez | A spinfoam model without bubble divergences[END_REF]. A partial result along these lines, in 3 dimensions with structure group SU(2), has indeed been obtained recently in [START_REF] Freidel | Group field theory renormalization -the 3d case: Power counting of divergences[END_REF], where bubbles are characterized in a purely graphical way. Specifically, they show that for a special class of foams coined 'type 1', the divergence degree is given by B -1, where B is the number of these 'graphical bubbles'. Similar results are also given in [START_REF] Ben Geloun | Linearized Group Field Theory and Power Counting Theorems[END_REF],

where for the sake of simplicity the structure group G is replaced by the non-compact Abelian group R.

Our purpose in this note is to clarify, in the topological spinfoams models based on flat connections, the relation between the divergence degree of a closed foam and the number of its 'bubbles'. For that matter, we introduce in section II the (co)homological language suitable to make precise the notion of 'bubbles'. In section III, we discuss the relation between the bubbles and the divergence degree of a foam Γ, showing in particular the following results:

• If Γ is simply connected or if G is Abelian, then Ω(Γ, G) = dim G b 2 (Γ).
• If Γ admits a single flat connection, then (b

2 (Γ) + χ(Γ) -1)/2 ≤ Ω(Γ, G)/ dim G ≤ b 2 (Γ).
where b 2 (Γ) and χ(Γ) are the second Betti number and the Euler characteristic of Γ respectively. In the conclusion, we explain why such cellular invariants, however, are too rough to capture the divergence degree of a generic foam, and outline a finer analysis, in terms of twisted cohomology, to be detailed in a forthcoming paper [START_REF] Bonzom | Bubble divergences from twisted cohomology[END_REF].

II. PRELIMINARIES

Our setting is the following. Let G be a compact semisimple Lie group with Lie algebra g, and Γ be a closed foam (i.e. an oriented cell 2-complex without boundary). We denote Γ i (i = 0, 1, 2) the set of its i-cells (vertices, edges and faces respectively), and

V = |Γ 0 |, E = |Γ 1 |, F = |Γ 2 |.
A connection on Γ is the assignment of elements of the structure group G to each edge of Γ ('parallel transport' operators). The space of connections on Γ is therefore

A = A = (g e ) e∈Γ1 ∈ G E , (2)
The curvature of a connection A is the family of F group elements given by

H(A) = H f (A) = e∈∂f g [f :e] e f ∈Γ2 , (3)
where [f : e] is the incidence number of the face f on the edge e (H f (A) is the 'holonomy' of the connection A around the face f ). A connection A is flat if3

H(A) = 1. (4)
The spinfoam amplitude considered in this note is then defined formally as the partition function of a system of flat G-connections on Γ:

Z(Γ, G) = A dA f ∈Γ2 δ H f (A) , (5)
where dA = e∈Γ1 dg e is the Haar measure on A = G E , and δ(g) is the Dirac delta on G. Obviously, the support of this integral is the set of flat connections

F = H -1 (1). (6)

A. Gauge transformations

Gauge transformations change the local frame at each vertex of Γ: this defines an action of G V on the set of discrete connections, according to

h • A = h t(e) g e h -1 s(e) e∈Γ1 . (7)
Here h = (h v ) v∈Γ0 is a set of V group elements, and t(e) (respectively s(e)) is the end (respectively starting) vertex of the edge e.

Gauge transformations leave the integrand of (5) invariant. When there is more than a single vertex in Γ 0 , it is therefore convenient to partially fix this gauge symmetry by setting g e = 1 on every edge of a maximal tree

F = Hom π 1 (Γ), G . (8)
In particular, when Γ is simply connected, F is just a point.

B. (Co)homological bubbles

Naively speaking, the divergence of ( 5) comes from the fact that some of the delta functions attached to the faces of the foam Γ are redundant. This phenomenon was first observed by Ponzano and Regge [START_REF] Ponzano | Semiclassical limit of Racah coefficients[END_REF] in the context of 3d quantum gravity, where Γ is the 2-skeleton of the dual cell complex to a triangulated closed 3-manifold ∆ and the gauge group is SU [START_REF] Perez | Spin Foam Models for Quantum Gravity[END_REF]. Using a sharp cutoff Λ on the spins labelling the irreducible representations of SU [START_REF] Perez | Spin Foam Models for Quantum Gravity[END_REF] in the Peter-Weyl decomposition of the delta function, they interpreted the divergence as coming from the N vertices of ∆, and conjectured that Ω(Γ, SU(2)) = 3N . This point of view was then strengthened by Freidel and Louapre [START_REF] Freidel | Diffeomorphisms and spin foam models[END_REF], who gave a geometric interpretation to this conjecture by exhibiting a discrete Bianchi identity associated to the vertices of ∆: if F v denotes the faces of Γ 'wrapping around' a vertex v of the triangulation ∆, then there is an ordering of F v such that

f ∈Fv H ǫ f f = 1, (9)
where ǫ f is ±1.

Unfortunately, this intuition -divergences associated to vertices in three dimensions, or (n -3)-simplices in n dimensions -turns out to be misleading. First, as mentioned in the introduction, one would like to consider foams that are not dual to any simplicial complex, hence where the notion of (n -3)-simplex of the dual triangulation is meaningless. Second, counter-examples are known to the Ponzano-Regge conjecture, like Bing's house with two rooms considered in [START_REF] Barrett | The Ponzano-Regge model[END_REF]. Third, and more importantly, it does not hold in higher dimensions: when Γ is the dual cell-complex to a triangulated n-manifold with n ≥ 4, it is easy to see that Ω(Γ, G) is not given by the number of (n -3)-simplices. (For n = 4, for instance, a 1-5 Pachner move on the triangulation immediately generates a foam violating this conjecture [START_REF] Ooguri | Topological lattice models in four dimensions[END_REF]).

Recently, Gurau [START_REF] Gurau | Colored Group Field Theory[END_REF] has considered a special class of foams, which he calls 'colored', and gave a graphtheoretic definition of 'bubble' and 'bubble homology' for these foams. This is the language in which the results of Ben Geloun et al. in [START_REF] Ben Geloun | Linearized Group Field Theory and Power Counting Theorems[END_REF] were framed. Although interesting in itself, this Gurau homology is somewhat idiosyncratic, and it seems preferable to use more stantard, and more general concepts to express the notion of 'bubble'.

It is enlightening in this respect to look at the linearization of (9) in the neighbourhood of the trivial connection. This gives

f ∈Fv e∈∂f [e : f ] X e = 0, (10)
for any choice of X e ∈ g. This observation suggests to consider the cellular homology of Γ with coefficients in g

0 -→ g F ∂2(Γ,g) -→ g E 0 -→ g -→ 0 ( 11
)
and its dual cohomology

0 ←-g F 0 ←-g E δ1(Γ,g) ←-g ←-0 (12)
as the natural setting for powercounting considerations.

Here ∂ 1 (Γ, g) and δ 0 (Γ, g) vanish because Γ has a single vertex, and δ 1 (Γ, g) and ∂ 2 (Γ, g) are related to the usual cellular operators with integer coefficients δ 1 (Γ, Z) and ∂ 2 (Γ, Z) by

δ 1 (Γ, g) = δ 1 (Γ, Z) ⊗ id g ∂ 2 (Γ, g) = ∂ 2 (Γ, Z) ⊗ id g . (13)
In this language, the equation ( 10) is simply ker ∂ 2 (Γ, g) = {0}, i.e. H 2 (Γ, g) = {0}. Thus, we propose to define a bubble as a 2-cycle, and the number of bubbles as the second Betti number

b 2 (Γ, g) = dim G b 2 (Γ). ( 14
)
Notice that this is definition is purely topologogical, in the sense that the structure group enters only via the multiplicative constant (dim G). Is the divergence degree Ω(Γ, G) given by b 2 (Γ, g)? Answering this question is the purpose of this note.

III. HOMOLOGICAL POWERCOUNTING

The ill-defined amplitude (5) can be conveniently regularized by replacing the delta functions with heat kernels 4 K τ on G, and considering the τ → 0 limit. Using 4 Recall that Kτ is the solution of the heat equation on G

(∂τ -∆)Kτ = 0 with initial condition lim τ →0 Kτ (g) = δ(g).
the standard small-time asymptotics

K τ (g) ∼ τ →0 (4πτ ) -dim G 2 e -|g| 2 4τ , ( 15
)
where |g| is the Riemannian distance between g and the unit 1 of G, and setting

Λ τ = (4πτ ) -1 2 (16)
as the cutoff, we see that this yields in the τ → 0 limit the Laplace-type integral

Z τ (Γ, G) ∼ τ →0 Λ (dim G)F τ A dA e -Sτ (A) 4τ , (17)
with the action

S(A) = f ∈Γ2 |H f (A)| 2 . ( 18
)
It would seem, therefore, that the divergence degree of Z τ (Γ, G) is determined by the behaviour of the Hessian of the action S along its critical set, which is of course the set of flat connections F . This first intuition is deceiving, however, because in general F is not a manifold [START_REF] Goldman | An algebraic proof for the symplectic structure of moduli space[END_REF], and the critical points are degenerate. It remains that, when H (and hence S) has isolated critical points, perhaps modulo some group action, Laplace's method can still be successful. Indeed, this typically happens in two cases: when Γ is simply connected, and when G is Abelian. In both cases, this line of reasoning yields the exact divergence degree -which, as anticipated, is indeed given by the second Betti number of Γ:

Ω(Γ, G) = dim G b 2 (Γ). (19)
Moreover, when Γ admits a unique flat G-connection, the same method still gives lower and upper bounds on Ω(Γ, G). In these considerations, the following observation will be key: the differential of the curvature map at the trivial connection is the first cellular coboundary operator of Γ with coefficients in g,

dH 1 = δ 1 (Γ, g). (20)
In particular, the number of bubbles og Γ is given by

b 2 (Γ, g) = (dim G)F -rk dH 1 ( 21
)
where rk denotes the rank of a linear map.

A. Simply connected foams

A simply connected foam admits a unique flat connection, the trivial one: that is, in this case, S has a unique global minimum at 1 ∈ G E . The Hessian of S there is the bilinear map on g E defined by

Hess(S) 1 (X, Y ) = dH 1 (X), dH 1 (Y ) g F , ( 22
)
where •, • g F is an invariant inner product in g F . By the Hurewicz theorem, we know that π 1 (Γ) = {1} implies H 1 (Γ) = ker δ 1 (Γ)/ im δ 0 (Γ) = 0, and since δ 0 (Γ, g) is identically zero (because Γ has a single vertex),

ker dH 1 = {0}. ( 23
)
Hence, the map Hess(S) 1 is non-degenerate, and the standard Laplace approximation gives

dA e -Sτ (A) 4τ ∼ τ →0 g E dX exp - dH 1 (X) 2 g F 4τ , ∼ τ →0 Λ -rk dH1 τ det Hess(S) 1 -1/2 . ( 24
)
Here the Hessian determinant is evaluated in an orthonormal basis of g E . Combining the exponent of Λ τ coming from the asymptotics of K τ with the Gaussian contribution rk dH 1 , and using the cohomological identity

rk dH 1 = rk δ 1 (Γ, g) = (dim G)(F -b 2 (Γ)), (25)
we obtain

Z τ (Γ, G) ∼ τ →0 Λ (dim G)b2(Γ) τ det Hess(S) 1 -1/2 . ( 26
)
In fact, this result is slightly more general. Indeed, it relies on two ingredients only: flat connections where the condition (20) holds, and the non-degeneracy condition (23). 5 The first condition is ensured if flat connections live in the center of G E , since then

dH A = δ 1 (Γ, g) • θ A , (27)
with θ the Maurer-Cartan form on G E , and therefore rk dH A = rk δ 1 (Γ, g). For instance, if G = SU(2), the two conditions are satisfied if π 1 (Γ) is a dihedral group D 2n , a symmetric group S n , the alternating group A 5 , or to GL(2, ).Using some standard presentations of these groups 6 , it can be checked, through direct computations, that flat connections live in the center {-1, 1} E . Furthermore, non-degeneracy of the Hessians follows from looking at the abelianization of π 1 (Γ), from which it can be concluded that the spaces H 1 (Γ) are trivial. 5 The requirement that flat connections be isolated is actually enforced by the non-degeneracy condition on the Hessian, by the Morse lemma. 6 Precisely, they admit the following presentations:

D 2n = r, f |r n = f 2 = (rf ) 2 = 1 , Sn = (σ i ) i=1,...,n-1 |σ i = 1, σ i σ j = σ j σ i if j = i ± 1, σ i σ i+1 σ i = σ i+1 σ i σ i+1 , A 5 = s, t|s 2 = t 3 = (st) 5 = 1 and GL(2, ) = j, a, b|j 2 = (ja) 2 = (jb) 2 = (aba) 4 = 1, aba = bab .
The fact that the representations of these groups into SU(2) are very simple can be traced to the fact that the equation g 2 = 1 is solved in SU(2) only by g = ±1.

B. Abelian structure group

When G is Abelian, another simplification arises: the curvature map H : G E → G F is a Lie group homomorphism. This means that H can be factored through its kernel -the flat connections -and thus be made injective. In other words, in the Abelian case, the gauge fixing procedure (reduction of a maximal tree in Γ) can be superseded by the global factorization of the flat connections.

Here is how this goes.

Let H denote the quotient of H trough its kernel, and d Ā the Haar measure on (the compact Lie group) Q = G E / ker H. Then we have

S(A) = f ∈Γ2 | Hf ( Ā)| 2 , ( 28
)
where Ā is the equivalence class of A modulo ker H. This defines a function S on G E / ker H having a unique global minimum at 1 ∈ Q. Up to exponentially suppressed corrections, the Laplace integral can therefore be restricted to a neighbourhood U of 1 where

S( Ā) = d H1 (log Ā) 2 g F . (29)
To deal properly with the degeneracy of the Hessian, we introduce Riemannian normal coordinates on U adapted to the decomposition

q = ker d H1 ⊕ (ker d H1 ) ⊥ , (30)
and integrate in the direction of ker d H1 . This gives a constant C. Next, we perform the Gaussian integration in the orthogonal direction, observing that rk H = rk H, and from dH 1 = δ 1 (Γ, g) we conclude that

Z τ (Γ, G) ∼ τ →0 CΛ Ω(Γ,G) τ det(d H1 ) -1/2 |(ker d H1) ⊥ (31)
with Ω(Γ, G) as in [START_REF] Forman | Small volume limits of 2-d Yang-Mills[END_REF]. That is, in the Abelian case, the divergence degree is given by the number of bubbles of Γ whatever its topology.

C. Single degenerate flat connection

Let us eventually point out some difficulties arising when the critical points of the action are degenerate. (For simplicity, we assume that Γ admits a single flat connection up to gauge transformations.) As before, the tangent space at the identity has a natural splitting g E = ker dH 1 ⊕ (ker dH 1 ) ⊥ . However, unlike the Abelian case, S will not just be quadratic on ker dH 1 , and one has to further expand it along these directions. Writing S ≈ Hess(S) 1|(ker dH1) ⊥ + T ker dH1 :

Z τ (Γ, G) ∼ τ →0 Λ (dim G)F τ (ker dH1) ⊥ dX e - dH 1 (X) 2 (ker dH 1 ) ⊥ 4τ × ker dH1 dY e -T (Y ) 4τ , (32)
where T (Y ) is at least quartic in Y . Despite the possibly complicated behaviour of T , one can easily get some bounds on the degree of divergence Ω(Γ, G) in that situation. Indeed, the basic idea is that the integral over the kernel of dH 1 , after some truncation of the expansion of T , reduces the degree of divergence by providing negative powers of Λ τ . This can be seen for instance when T is a monomial of total degree k. Then, rescaling Y by τ -1/k produces a factor Λ -2 dim ker dH 1 k τ . The dimension of ker dH 1 being fixed, this means that the most divergent case corresponds to the vanishing of T at all orders. Since G is compact, the integral over Y does not bring about additional divergences. Thus, the divergence degree is always smaller than the one obtained for T = 0:

Ω(Γ, G) ≤ dim G F -rk dH 1 , ≤ dim G b 2 (Γ). (33)
Furthermore, the least divergent situation is for T being exactly quartic on ker dH 1 . Then, a simple rescaling of Y by τ -1/4 leads to the following bound on the divergence degree:

Ω(Γ, G) ≥ dim G b 2 (Γ) - 1 2 dim ker δ 1 (Γ) . (34)
Since δ 0 (Γ) is identically zero, the dimension of ker δ 1 (Γ) is the Betti number b 1 (Γ). Introducing the Euler characteristic of Γ, χ(Γ) = b 2 -b 1 + 1, we finally get the following bounds:

1 2 b 2 (Γ) + χ(Γ) -1 ≤ Ω(Γ, G) dim G ≤ b 2 (Γ). ( 35
)
Although the above bounds only depend on Γ and do not exhibit any entanglement between Γ and G, this analysis already shows that the exact degree Ω(Γ, G) will depend on G in a more sophisticated way than the simple scaling by (dim G). By the BCH formula, one sees that T ker dH1 depends on the (non-)commutative structure of the Lie algebra g. In particular T identically vanishes as soon as G is Abelian, consistently with the result of the previous section.

IV. CONCLUSION

We have shown in this note that, in some special cases, the intuition that the divergence degree of a foam de-pends on its topology only (up to the multiplicative constant dim G) is correct. But, in our opinion, more interesting is the realization that this is not true in general. Technically, we saw that this is because the flat configurations form an extended set, along which the action S(A) has a degenerate Hessian. An example of this phenomenon is provided by the weak-coupling limit of 2d Yang-Mills theory: for genus g ≥ 2, the partition function is well-known to converge as τ → 0 for G = SU(2), and to diverge for Abelian groups.

Still, it is possible to adapt the cohomological analysis to this case, by making the cochain complex local. For every flat connection φ ∈ F , dH φ defines a twisted coboundary operator [START_REF] Goldman | An algebraic proof for the symplectic structure of moduli space[END_REF]. This local cochain complex is well-known in two dimensional Yang-Mills theory [START_REF] Witten | On quantum gauge theories in two dimensions[END_REF][START_REF] Forman | Small volume limits of 2-d Yang-Mills[END_REF], and similar analyses have been performed for BF theories in the continuum [START_REF] Blau | Topological Gauge Theories of Antisymmetric Tensor Fields[END_REF][START_REF] Horowitz | Exacly Soluble Diffeomorphism Invariant Theories[END_REF][START_REF] Gegenberg | The partition function for topological field theories[END_REF]. In our framework, this line of reasoning yields a local divergence degree ω(Γ, G; φ), such that 0 < lim Λ→0 |Λ -ω(Γ,G;φ) Z τ (Γ, G; φ)| < ∞ where

Z τ (Γ, G, φ) = U φ dA f ∈Γ2 K τ (H f (A)), (36)
for some neighbourhood U φ ⊂ A of φ, given (or bounded) by the second Betti number in this twisted cohomology [START_REF] Bonzom | Bubble divergences from twisted cohomology[END_REF]. To infer the global divergence degree Ω(Γ, G) from this local analysis, one should then study the behaviour of this twisted cohomology as φ approaches the singularities of F .

In short, the divergence degree for a generic foam Γ involves both the topology of Γ and the non-Abelian structure of G in a rather subtle way -indeed much subtler than the notion of 'number of bubbles' would suggest a priori.

In this note, 1 denotes the unit element of the relevant group.in Γ, i.e. a subgraph of Γ 1 touching every vertex of Γ without forming any loop. This is actually equivalent to considering the partition function on a deformation retract of Γ with only one vertex. The remaining gauge transformations consist in the standard action of G on A by a global conjugation. Thanks to the homotopy invariance of the divergence degree, see below, we will assume without loss of generality that Γ is indeed of this kind.The fundamental group π 1 (Γ) of such a foam admits a presentation with one generator per edge, together with one relation per face exactly of the form of H f , (3). It follows that the space of flat connections F can be identified with the representation variety of π 1 (Γ) into G:

Acknowledgements

We are indepted to Jacques Magnen and Thomas Krajewski for the suggestion to study the Abelian case first, and to Razvan Gurau, Joseph Ben Geloun, Vincent Rivasseau and Henrique Gomes for useful discussions on homology and powercounting. We also thank collectively the Marseille quantum gravity group for their support.


GUILLEMIN JEAN-PHILIPPE (1), [START_REF] Lines | Nanomaterials for practical functional uses[END_REF] , OLIVIER BONNEFOY (2) * [START_REF] Feynman | There's plenty of room at the bottom, discours prononcé le 29 décembre 1959 au congrès annuel[END_REF] Nexter Munitions, Engineering Direction, 7 route de Guerry, 18023 Bourges, France* [START_REF] Lines | Nanomaterials for practical functional uses[END_REF]  une taille de grain de l'ordre de 10 -9 m (1-100 nm) ;

 une surface spécifique très élevée ;

 des matériaux améliorant les propriétés mécaniques ;

 -des matériaux chimiquement très réactifs [2].

Suspension micro-chargée Suspension nano-chargée

Pas de contrainte seuil Apparition d'une contrainte seuil Les résultats expérimentaux ont montré que le changement d'échelle de la matière pulvérulente engendre une évolution de la loi de comportement à l'écoulement des suspensions. Ainsi, pour les suspensions micro-chargées utilisées dans cette étude, le comportement reste newtonien alors que, pour les suspensions nano-chargées, l'écoulement devient non newtonien, avec notamment l'apparition d'une contrainte seuil au delà de laquelle la matière peut s'écouler (voir Figure 1). Autre particularité due, en partie, à l'excédent de surface spécifique offert par les entités nanométriques : pour un même volume de matière solide au sein de la phase liquide, la suspension nano-chargée est plus visqueuse que la suspension micro-chargée (voir Figure 2). De plus, la modification des comportements physiques des produits finis intégrant des nanomatériaux induit des modifications à plusieurs niveaux dans une chaine de production : étanchéité des installations, temps de flux de matière, et élimination des déchets. La mise en oeuvre de ces matériaux conduit trivialement à une analyse du cycle de vie du couple matière / procédé. Il est donc important de garder à l'esprit les fondamentaux suivants, c'est-à-dire :

F Fi ig gu ur re e 1 1: : M Me es su ur re es s d de e l la a c co on nt tr ra ai in nt te e d de e c ci is sa ai il ll le em me en nt t  e en n f fo on nc ct ti io on n d de e l la a v vi it te es ss se e d de e c ci is sa ai il ll le em me en nt t  p po ou ur r d di if ff fé ér re en nt te es s f fr ra ac ct ti io on ns s v vo ol lu um mi iq qu ue es s s so ol li id de es s  d d' 'a al lu um mi in ni iu um m. . L Le es s c co ou ur rb be es s m mo on nt tr re en nt t c cl la ai ir re em me en nt t l le es s m mo od di if fi ic ca at ti io on ns s d du u c co om mp po or rt te em me en nt t à à l l' 'é éc co ou ul le em me en nt t d d' 'u un ne e s su us sp pe en ns si io on n m mi ic cr ro o--c ch ha ar rg gé ée e o ou u n na an no o--c ch ha ar rg gé ée e. . L L' 'a ap pp pa ar ri it ti io on n d d' 'u un ne e c co on nt tr ra ai in nt te

 dans un souci de processabilité, démontrer la faisabilité connective risque/technique/économie permettant la compatibilité des nanomatériaux et des procédés de transformation ;

 comprendre comment bien disperser les nanomatériaux dans une matrice pour une mise en oeuvre optimisée à l'intérieur de différents procédés ;

 adapter les procédés industriels de transformation habituels aux contraintes des nanomatériaux.

C'est en gardant ces principes rationnels à l'esprit que les nanomatériaux auront des propriétés finales d'un grand intérêt en vue de l'optimisation des fonctions d'usage d'un produit fini.

  e s se eu ui il l r ré év vè èl le e q qu ue e l la a s su us sp pe en ns si io on n n na an no o--c ch ha ar rg gé ée e n ne e p po ou ur rr ra a s s' 'é éc co ou ul le er r q qu u' 'a au u d de es ss su us s d de e c ce et tt te e v va al le eu ur r. . C Cr ré éd di it t : : J J. .P P. . G GU UI IL LL LE EM MI IN N e et t a al l. . d d' 'a ap pr rè ès s [ [3 3] ], , d de es ss si in n : : P P. . B Bo ou ui il ll lo on n. . Toutes ces caractéristiques confèrent aux nanomatériaux des comportements spécifiques, fonction de la taille, qui les diffèrent des entités micrométriques. Ces différences peuvent s'observer, par exemple, sur les propriétés rhéologiques (propriétés d'écoulement) d'une suspension micro-chargée ou nano-chargée. Dans un souci d'anticipation des conséquences de l'intégration de tels matériaux au sein d'une suspension, Nexter Munitions, le CNRI (Centre national des risques industriels) et le laboratoire SPIN de l'Ecole nationale supérieure des mines de Saint-Etienne ont mené une étude comparative sur le comportement à l'écoulement de suspensions concentrées intégrant une poudre d'aluminium dont les grains se présentent sous deux échelles de tailles différentes : micrométriques ou nanométriques [3].

F

  De même que les propriétés d'écoulement, les propriétés mécaniques obtenues en compression uniaxiale diffèrent selon que l'entité considérée est nanométrique, ou micrométrique. Ces observations ont été modélisées par Lamy et al.[4] lors de la réalisation de comprimés intégrant des nanomatériaux ou des micromatériaux. L'auteur a particulièrement constaté que la diminution de porosité lors de l'étape de compression évoluait de manière totalement différente selon l'échelle de grain utilisée. Fi ig gu ur re e 3 3: : E Ev vo ol lu ut ti io on n d de e l la a p po or ro os si it té é d d' 'u un n l li it t d de e p po ou ud dr re e n na an no om mé ét tr ri iq qu ue e o ou u m mi ic cr ro om mé ét tr ri iq qu ue e l lo or rs s d de e l la a r ré éa al li is sa at ti io on n d de e c co om mp pr ri im mé és s p pa ar r c co om mp pr re es ss si io on n u un ni ia ax xi ia al le e. . L Le es s m ma at té ér ri ia au ux x c co on ns si id dé ér ré és s s so on nt t l l' 'o ox xy yd de e d de e z zi in nc c ( (a a) ) ( (m mi ic cr ro om mé ét tr ri iq qu ue e ( (Z Zn nO O µ µ) ) o ou u n na an no om mé ét tr ri iq qu ue e ( (Z Zn nO O n n) )) ), , l l' 'a al lu um mi in ni iu um m ( (b b) ) ( (m mi ic cr ro om mé ét tr ri iq qu ue e ( (A Al l µ µ) ) o ou u n na an no om mé ét tr ri iq qu ue e ( (A Al l n n) )) ) e et t l le e t tu un ng gs st tè èn ne e ( (c c) ) ( (m mi ic cr ro om mé ét tr ri iq qu ue e ( (W W µ µ) ) o ou u n na an no om mé ét tr ri iq qu ue e ( (W W n n) )) ). .

  Ecole Nationale Supérieure des Mines de Saint Etienne, Centre SPIN ; Département PMCC ; LPMG -UMR CNRS 5148, 158 Cours Fauriel ; 42023 Saint-Étienne Cedex 2, FranceRésuméL'arrivée des nanomatériaux parmi les objets du quotidien semble porteuse de fonctions d'usage innovantes, mais pose de nombreux problèmes de mise en oeuvre lors de l'intégration de particules nanométriques dans des procédés de fabrication standardisés. Il semble donc impératif d'adapter les procédés de transformation habituels.

	Q Q Q u u u e e e l l l s s s u u u s s s a a a g g g e e e s s s d d d e e e s s s n n n a a a n n n o o o m m m a a a t t t é é é r r r i i i a a a u u u x x x a a a u u u q q q u u u o o o t t t i i i d d d i i i e e e n n n ? ? ?
	Les nanomatériaux ne sont plus seulement une curiosité de laboratoire, mais ont maintenant
	atteint le stade de commercialisation. Ils touchent tous les secteurs industriels et intègrent
	déjà des produits de tous les jours : nanoparticules dans les cosmétiques, les bétons, les
	peintures…et, peut être un jour voire, dans nos assiettes.
	Si les nanomatériaux reçoivent une attention particulière de la communauté scientifique sur
	leurs propriétés finales (électrique, mécanique ou thermique), le besoin d'évolution des
	procédés de mise en oeuvre intégrant des nanopoudres n'est que rarement évoqué.
	M M M i i i c c c r r r o o o ---n n n a a a n n n o o o : : : d d d e e e s s s c c c o o o m m m p p p o o o r r r t t t e e e m m m e e e n n n t t t s s s d d d i i i f f f f f f é é é r r r e e e n n n t t t s s s . . .

R. Feynman

[1]

lors du congrès annuel de l'American Physical Society, en 1959, annonçait qu'une nouvelle ère de recherche était à la portée des scientifiques qui sauraient synthétiser, contrôler, et caractériser les nanomatériaux. Il avait cependant oublié qu'une autre étape primordiale était nécessaire pour conférer à ces matériaux les promesses technologiques attendues, celle de leur intégration, sans risque, dans les procédés industriels actuels employant des micro-charges.

Les mots clés liés aux nanomatériaux peuvent se résumer ainsi :