Laurent Busé

Thang Luu Ba

The surface/surface intersection problem by means of matrix based representations

Evaluating the intersection of two rational parameterized algebraic surfaces is an important problem in solid modeling. In this paper, we make use of some generalized matrix based representations of parameterized surfaces in order to represent the intersection curve of two such surfaces as the zero set of a matrix determinant. As a consequence, we extend to a dramatically larger class of rational parameterized surfaces, the applicability of a general approach to the surface/surface intersection problem due to J. Canny and D. Manocha. In this way, we obtain compact and efficient representations of intersection curves allowing to reduce some geometric operations on such curves to matrix operations using results from linear algebra.

Introduction

Computing the intersection between two parameterized algebraic surfaces is a fundamental task in Computer Aided Geometric Design. Several methods and approaches have been developed for that purpose. Some of them are based on the use of matrix representations of the objects because they allow to transform geometric operations on the intersection curve into matrix operations. This approach seems to have been first introduced by J. Canny and D. Manocha in their paper [START_REF] Manocha | A new approach for surface intersection[END_REF]. Roughly speaking, it consists in representing the implicit equation of one of the two surfaces as the determinant of a certain matrix, necessarily square. Then, instead of using this implicit equation, the matrix itself is used as a representation of this first parameterized surface and then a matrix representation of the intersection curve is easily obtained by substituting the implicit variables with the parameterization of the second surface.

As far as we know, this matrix based approach and all its successive improvements (see e.g. [START_REF] Fioravanti | Computing the intersection of two ruled surfaces by using a new algebraic approach[END_REF][START_REF] Shen | Homeomorphic approximation of the intersection curve of two rational surfaces[END_REF]), have only been developed by using square matrices for representing parameterized surfaces. These matrices are obtained either as resultant matrices, which is the case for instance in [START_REF] Manocha | A new approach for surface intersection[END_REF], or as matrices filled with some syzygies of a parameterization. This second class of matrices is known under the name of the moving quadrics method (see [START_REF] Sederberg | Implicitization using moving curves and surfaces[END_REF][START_REF] Cox | On the validity of implicitization by moving quadrics of rational surfaces with no base points[END_REF][START_REF] Busé | Implicitization of surfaces in P 3 in the presence of base points[END_REF]). It turns out that only some particular surface parameterizations, namely the parameterizations without base points (i.e. that are well defined over all their parameter space) can be represented by such matrices (with the exception of the matrices given in [START_REF] Busé | Implicitization of surfaces in P 3 in the presence of base points[END_REF]). This absence of base points is definitely a very strong constraint in the context of applications in solid modeling. It is hence the main limitation of applicability of the Canny-Manocha matrix based approach to the surface/surface intersection problem that is nevertheless an interesting compromise to provide an efficient, robust and accurate solution to this problem (see [START_REF] Manocha | A new approach for surface intersection[END_REF]). The goal of this paper is to overcome this limitation.

Recently, new matrix representations of parameterized algebraic surfaces have been introduced in [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF][START_REF] Busé | Implicitizing rational hypersurfaces using approximation complexes[END_REF][START_REF] Busé | Elimination and nonlinear equations of rees algebras[END_REF]. These matrices are filled with syzygies of a parameterization in the same spirit as the moving quadrics method, but with the difference that they are non-square matrices. However they are still representation matrices because they are generically full rank matrices and their rank drop exactly on the surface (this is a direct generalization of a matrix determinant to non-square matrices). The main advantage of using these representation matrices is that they exist for a significantly larger class of parameterizations, in particular for most of parameterizations having base points (see [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF][START_REF] Busé | Implicitizing rational hypersurfaces using approximation complexes[END_REF][START_REF] Busé | Torsion of the symmetric algebra and implicitization[END_REF][START_REF] Busé | Elimination and nonlinear equations of rees algebras[END_REF] for details).

In this paper, we will introduce the use of these more general matrix representations in the context of the surface/ surface intersection problem. By doing this, a new difficulty appears because we will have to manipulate pencils of matrices 1 that are non-square, whereas in the classical Canny-Manocha approach the intersection curve is directly represented as a matrix determinant. It turns out that most techniques and algorithms that allow to determine the intersection curve with its exact topology need an implicit equation of this curve. Therefore, it is necessary to extract such an equation from a non-square matrix representation of this curve. For that purpose, instead of proceeding in a naive way by computing a greatest common divisor of several minors, we develop an algorithm based on matrix operations to extract from the non-square pencil of matrices all the information we need under the form of a pencil of square matrices. We will here follow the work of V. N. Kublanovskaya on what is called the ∆W -1 decomposition algorithm [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF].

The paper is organized as follows. In Section 2, we briefly define and review the matrix representations of a parametrized surface that we will use in the sequel. In Section 3, we deal with the surface/surface intersection problem. In particular, we show how to reduce the computation of the intersection curve of two parameterized surfaces to the determination of the spectrum of a bivariate pencil of matrices. Then, in Section 4 we propose a method, based on the ∆W -1 decomposition of V. N. Kublanovskaya, that allows us to extract the regular part corresponding to the one-dimensional eigenvalues of such a bivariate pencil of matrices. The paper ends with some illustrative examples. This work is a follow-up of a more general research program whose goal is to show that non-square matrix representations of algebraic curves and surfaces can be used in the place of square matrix representations with the advantage of being available for a dramatically larger class of parameterizations. Thus, in [START_REF] Luu Ba | Curve/surface intersection problem by means of matrix representation[END_REF] the curve/surface intersection problem has been addressed and the space curve/space curve intersection problem is treated in [START_REF] Busé | Matrix-based implicit representations of algebraic curves and applications[END_REF]. As a natural continuation, we deal with the surface/surface intersection problem in this paper. This work is part of the PhD thesis of the second author [START_REF] Ba | Matrix-based implicit representations of algebraic curves and surfaces and applications[END_REF].

For simplicity, throughout the paper the ground field will be an algebraically closed field, typically the field of complex numbers C. However, mention that most of the results in Section 2, notably the matrix-based representations of surfaces we will introduce, could be given over an arbitrary infinite field.

Matrix based implicit representations of parameterized surfaces

Given a parameterized algebraic surface, we briefly recall from [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF][START_REF] Busé | Implicitizing rational hypersurfaces using approximation complexes[END_REF] how to build a matrix that represents this surface in a sense that we will make explicit. So suppose given a parameterization

P 2 C φ - → P 3 C (s : t : u) → ( f 1 : f 2 : f 3 : f 4 )(s, t, u) of a surface S such that gcd( f 1 , . . . , f 4 ) ∈ C \ {0}. Set d := deg( f i ) ≥ 1, i = 1,
2, 3, 4 and denote by x, y, z, w the homogeneous coordinates of the projective space P 3 C . Notice that s, t, u are the homogeneous parameters of the surface S and that an affine parameterization of S can be obtained by "inverting" one of these parameters; for instance, setting s = s/u and t = t/u we get the following affine parameterization of S:

C 2 φ - → C 3 (s , t ) → f 1 (s , t , 1) f 4 (s , t , 1) , f 2 (s , t , 1) f 4 (s , t , 1) , f 3 (s , t , 1) f 4 (s , t , 1)
The implicit equation of S is a homogeneous polynomial S (x, y, z, w) ∈ C[x, y, z, w] of smallest degree such that S ( f 1 , f 2 , f 3 , f 4 ) = 0 (observe that it is defined up to multiplication by a nonzero element in C). It is well known that the quantity deg(S) deg(φ) is equal to d 2 minus the number of common roots of f 1 , f 2 , f 3 , f 4 in P 2 C , that are called base points of the parameterization φ, counted with suitable multiplicities (see for instance [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF]Theorem 2.5] for more details). The notation deg(S) stands for the degree of the surface S that is nothing but the degree of the implicit equation of S. The notation deg(φ) stands for the degree of the parameterization φ (co-restricted to S) that, roughly speaking, measures the number of times the surface S is drawn by the parameterization φ. More precisely, deg(φ) is equal to the number of pre-images of a general point on S by the parameterization φ.

For all non negative integer ν, we build a matrix M(φ) ν as follows. Consider the set L(φ) ν of polynomials of the form a 1 (s, t, u)x + a 2 (s, t, u)y + a 3 (s, t, u)z + a 4 (s, t, u)w such that

• a i (s, t, u) ∈ C[s, t, u
] is homogeneous of degree ν for all i = 1, . . . , 4,

• 4 i=1 a i (s, t, u) f i (s, t, u) ≡ 0 in C[s, t, u].
The set L(φ) ν has a natural structure of C-vector space of finite dimension because each polynomial a i (s, t, u) is homogeneous of degree ν and that the set of homogeneous polynomials of degree ν in the variables s, t, u is a C-vector space of dimension ν+2 2 with canonical basis the set of monomials {s ν , s ν-1 t, • • • , u ν }. So, denote by L (1) , . . . , L (n ν ) a basis of the C-vector space L(φ) ν ; it can be computed by solving a single linear system whose indeterminates are the coefficients of the polynomials a i (s, t, u), i = 1, 2, 3, 4. The matrix M(φ) ν is then by definition the matrix of coefficients of L (1) , . . . , L (n ν ) as homogeneous polynomials of degree ν in the variables s, t, u. In other words, we have the equality of matrices:

s ν s ν-1 t • • • u ν M(φ) ν = L (1) L (2) • • • L (n ν ) .
Notice that we have chosen for simplicity the monomial basis for the C-vector space of homogeneous polynomials of degree ν in s,t,u. However, any other choice, for instance the Bernstein basis, can be made without affecting the result that we will state in the rest of this paper. For all integer ν ≥ 2d -2, the matrix M(φ) ν is said to be a representation matrix of φ because it satisfies the following properties under the assumption that the base points of φ, if any, form locally a complete intersection, which means that at each base point, the ideal of polynomials ( f 1 , f 2 , f 3 , f 4 ) can be generated by two equations (see [START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF]Definition 4.8] for more details):

• The entries of M(φ) ν are linear forms in C[x, y, z, w].

• The matrix M(φ) ν has ν+2 2 rows (which is nothing but the dimension of the C-vector space of homogeneous polynomials of degree ν in three variables, here s, t, u) and possesses at least as much columns as rows.

• The rank of M(φ) ν is ν+2 2 .

• When specializing M(φ) ν at a given point P ∈ P 3 C , its rank drops if and only if P belongs to S.

• The greatest common divisor of the ν+2 2 -minors of M(φ) ν is equal to the implicit equation of S raised to the power deg(φ).

From a computational point of view, the matrix M(φ) ν with the smallest possible value of ν has to be chosen. It is rarely a square matrix. Also, notice that the last property given above is never used for computations; our aim is to keep the matrix M(φ) ν as an implicit representation of S in place of its implicit equation.

There are many results that lead to enlarge the above family of matrices and to make it available in other contexts. Since a detailed overview of these results is not the purpose of this paper, we just recall them shortly with appropriate references to the literature:

• The hypothesis on the base points of φ can be relaxed. If the base points are locally almost complete intersection, meaning that they are locally given by three (and not two) equations, then the above family of matrices can still be constructed and provide a matrix representation of the surface S plus a certain product of hyperplanes that can be described from the parameterization φ. In addition, the bound 2d -2 for the integer ν can be decreased. See [START_REF] Busé | Implicitizing rational hypersurfaces using approximation complexes[END_REF][START_REF] Busé | On the closed image of a rational map and the implicitization problem[END_REF].

• In our setting, φ parameterizes what is called a triangular Bezier patch. It turns out that a similar family of matrices M(φ) ν can be built for parameterizations of tensor product surfaces, and even for any parameterization whose parameter space is a projective toric variety (triangular and tensor product surfaces are particular cases of parameterizations whose parameter space is a projective toric variety). We refer the interested reader to [START_REF] Busé | Implicitization of bihomogeneous parametrizations of algebraic surfaces via linear syzygies[END_REF][START_REF] Botbol | Matrix representations for toric parametrizations[END_REF][START_REF] Botbol | Implicitization of rational maps[END_REF].

• To build the matrices M(φ) ν we used what is called moving planes, that is to say syzygies of the parameterization φ. It is actually possible to build another family of matrices by taking into account moving quadrics, i.e. syzygies associated to the square of the ideal generated by the parameterization of φ. In this way, we get a family containing smaller matrices whose entries are either linear or quadratic forms in C[x, y, z, w]. In some sense, they generalize the matrices given in [START_REF] Cox | On the validity of implicitization by moving quadrics of rational surfaces with no base points[END_REF] and [START_REF] Busé | Implicitization of surfaces in P 3 in the presence of base points[END_REF]. See [START_REF] Busé | Elimination and nonlinear equations of rees algebras[END_REF].

Representation of the intersection curve

With the results presented in Section 2, we can generalize the Canny-Manocha method for representing the intersection curve between two parameterized algebraic surfaces [START_REF] Manocha | A new approach for surface intersection[END_REF]. Indeed, the matrix based approach used by J. Canny and D. Manocha requires the existence of square matrix representations of parameterized algebraic surfaces. Hereafter, we will relax this limitation by using the matrix representations given in Section 2. Moreover, in Section 4 we will develop linear algebra techniques in order to obtain the intersection curve as a determinant matrix, exactly as in [START_REF] Manocha | A new approach for surface intersection[END_REF]. In this way, the output of our algorithm will be compatible with the determination of the exact topology of the intersection curve by means of several techniques, for instance [START_REF] Manocha | A new approach for surface intersection[END_REF] or more recently [START_REF] Mantzaflaris | A subdivision approach to planar semi -algebraic sets[END_REF], that make use of an implicit equation.

Suppose given two parameterized algebraic surfaces S 1 and S 2 . A standard problem in non linear computational geometry is to determine the set S 1 ∩ S 2 ⊂ P 3

C which is a curve in P 3 C providing S 1 and S 2 are two distinct surfaces. As we explained in Section 2, if the parameterization of S 1 has locally complete intersection base points then one can build a representation matrix of S 1 that we will denote by M(x, y, z, w). Let

Ψ : P 2 C → P 3 C : (s : t : u) → (a(s, t, u) : b(s, t, u) : c(s, t, u) : d(s, t, u
)) be a parameterization of S 2 where a(s, t, u), b(s, t, u), c(s, t, u), d(s, t, u) are homogeneous polynomials of the same degree and without common factor in C[s, t, u]. By substituting in the representation matrix M(x, y, z, w) the variables x, y, z, w by the homogeneous polynomials a(s, t, u), b(s, t, u), c(s, t, u), d(s, t, u) respectively, we get the matrix

M(s, t, u) := M(Ψ(s, t, u)) = M(a(s, t, u), b(s, t, u), c(s, t, u), d(s, t, u)).
From the properties of the representation matrix M(x, y, z, w), we known that M(s, t, u) has maximal rank ρ (ρ is the number of rows of M and M has at least as much columns as rows). Moreover, for all point (s 0 : t 0 : u 0 ) ∈ P 2 we have rank(M(s 0 :

t 0 : u 0 )) < ρ if and only if              Ψ(s 0 , t 0 , u 0 ) ∈ S 1 ∩ S 2 or (s 0 : t 0 : u 0 ) is a base point of Ψ. (1)
Indeed, by property of the representation matrix M(x, y, z, w), we know that the rank of M drops at the point Ψ(s 0 , t 0 , u 0 ), providing this later is well defined, if and only if Ψ(s 0 , t 0 , u 0 ) ∈ S 1 . If Ψ(s 0 , t 0 , u 0 ) is not well defined, or in other words if (s 0 : t 0 : u 0 ) is a base point of Ψ, then the matrix M(Ψ(s 0 : t 0 : u 0 )) is equal to the null matrix since all the entries of M are linear forms in x, y, z, w, and therefore its rank drops.

Define the spectrum of the matrix M(s, t, u) as the set (s 0 : t 0 : u 0 ) ∈ P 2 such that rank(M(s 0 : t 0 : u 0 )) < ρ .

Then, the equivalence [START_REF] Ba | Matrix-based implicit representations of algebraic curves and surfaces and applications[END_REF] shows that the spectrum of M(s, t, u) yields the intersection locus of S 1 ∩ S 2 plus the base points of the parameterization Ψ of S 2 . The following result shows that the base points of Ψ has not to be removed from the spectrum of M(s, t, u) that this later actually gives exactly the information we need to obtain the intersection locus S 1 ∩ S 2 .

Theorem 1. The spectrum of the matrix M(s, t, u) is an algebraic curve in P 2 , which means that it is equal to the zero locus of a homogeneous polynomial in C[s, t, u]. In particular, there are no isolated points in the spectrum of M(s, t, u).

Proof. By property of the representation matrix M(x, y, z, w), we know that the ideal generated by the ρ-minors of M(x, y, z, w), denoted det ρ M(x, y, z, w), is supported on the hypersurface S 1 . In other words, the algebraic variety associated to det ρ M(x, y, z, w) is exactly S 1 . Now, since the substitution of x, y, z, w by Ψ(s, t, u) commutes with the formation of the determinantal ideals, more

precisely det ρ (M(s, t, u)) = det ρ (M(Ψ(s, t, u))) = det ρ M(x, y, z, w) (Ψ(s, t, u)),
we deduce det ρ (M(s, t, u)) is supported on the algebraic curve obtained by substituting x, y, z, w by Ψ(s, t, u) in an implicit equation of S 1 . We conclude the proof by noting that the spectrum of M(s, t, u) is by definition supported on the algebraic variety associated to the ideal det ρ (M(s, t, u)).

Remark 1. If the parameterization of S 1 has base points that are almost complete intersection, then the above results still hold but in the equivalence (1) and in the proof of Theorem 1, the surface S 1 has to be replaced with (S 1 ∪ p H p ) where H p is a hyperplane which is associated to a base point p of the parameterization of S 1 which is not a complete intersection.

The algebraic curve C ∈ P 2 in this theorem is a representation of the intersection set S 1 ∩ S 2 because the parameterization Ψ induces a rational map from C to S 1 ∩ S 2 . Therefore, the computation of an equation of the curve C allows to write down an explicit parameterization of the intersection locus S 1 ∩ S 2 . In [START_REF] Manocha | A new approach for surface intersection[END_REF], such an equation is directly obtained as a determinant matrix because they restrict their study to the class of parameterized surfaces S 1 that admit a square representation matrix. In our setting, since we handle a much more larger class of parameterized surfaces, we get non-square matrices. The purpose of the next section is therefore to describe an algorithm that allows to reduce these non-square matrices to square matrices by linear algebra methods. Then, in Section 5 we will state the resulting algorithm and illustrate it with some detailed examples. But before moving on, let us end this section with the following interesting geometric consequence of Theorem 1.

Corollary 1. For any parameterized surface S 1 as above, the algebraic curve describing the spectrum of the matrix M(s, t, u) will always goes through the base points of the parameterization Ψ of S 2 .

Reduction of a bivariate pencil of matrices

As a consequence of Theorem 1, if we use matrix representations to deal with the surface/surface intersection problem, we will end up at some point with a pencil of bivariate and non-square matrices that represents the intersection curve (after dehomogenization). Therefore, in order to be able to handle this intersection curve, for instance to determine its exact topology, it is necessary to extract a pencil of bivariate and square matrices that yields a matrix representation of the intersection curve as a matrix determinant. For that purpose, we develop an algorithm based on the remarkable work of V. N. Kublanovskaya [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF].

The spectrum of a bivariate polynomial matrix

Let M(s, t) be a matrix of size m × n depending on the two variables s and t. The spectrum of M(s, t) is defined as the set

{(s 0 , t 0 ) ∈ C × C : rank(M(s 0 , t 0 )) < ρ}
where ρ := rank M(s, t). Denote by M j 1 ,..., j ρ i 1 ,...,i ρ the matrix obtained from M(s, t) by taking the ρ rows of index i 1 , ..., i ρ , and the ρ columns of index j 1 , ..., j ρ , where 1 ≤ i 1 < ... < i ρ ≤ m and 1 ≤ j 1 < ... < j ρ ≤ n. The spectrum of M(s, t) is exactly the set of common roots of all the algebraic equations det M j 1 ,...,

j ρ i 1 ,...,i ρ = 0, 1 ≤ i 1 < ... < i ρ ≤ m, 1 ≤ j 1 < ... < j ρ ≤ n.
(

) 2
The one-dimensional and zero-dimensional algebraic components of the system of algebraic equations (2) determine respectively the one-dimensional and zero-dimensional eigenvalues of the matrix M(s, t). We recall that the onedimensional eigenvalues (also called eigencurves) form the continuous part of the spectrum of M(s, t) which can be described by an algebraic equation in the parameters s and t. The zero-dimensional eigenvalues form the discrete part of the spectrum of M(s, t).

Linearization of a bivariate polynomial matrix

Suppose given an m×n-matrix M(s, t) = (a i, j (s, t)) with polynomial entries a i, j (s, t) ∈ C[s, t]. It can be equivalently written as a polynomial in s whose coefficients are m × n-matrices with entries in

C[t]. If d = max i, j {deg s (a i, j (s, t))} then set M(s, t) = M d (t)s d + M d-1 (t)s d-1 + . . . + M 0 (t)
where M i (t) ∈ C[t] m×n for all i = 0, . . . , d.

A(t) =                       0 I m . . . . . . 0 0 0 I m . . . 0 . . . . . . . . . . . . . . . 0 0 . . . . . . I m M t 0 (t) M t 1 (t) . . . . . . M t d-1 (t)                       , B(t) =                       I m 0 . . . . . . 0 0 I m 0 . . . 0 . . . . . . . . . . . . . . . 0 0 . . . I m 0 0 0 . . . . . . -M t d (t)                      
, where I m stands for the identity matrix of size m and M t i (t) stands for the transpose of the matrix M i (t). These companion matrices allows to linearize the polynomial matrix M(s, t) in the sense that there exists two unimodular matrices E(s, t) et F(s, t) with coefficients in C[s, t] and of size dm and (d -1)m + n respectively, such that

E(s, t) (A(t) -sB(t)) F(s, t) = t M(s, t) 0 0 I m(d-1) . (3)
In particular, a straightforward computation shows that for all s ∈ C and v ∈ C[t] m we have

M t (s, t)v = 0 ⇔ (A(t) -sB(t))                  v sv . . . s d-1 v                  = 0.
It is important to notice that (3) implies that the computation of the spectrum of the polynomial matrix M(s, t) can be reduced to the computation of the spectrum of the polynomial matrix A(t) -sB(t) which has the advantage to be linear in the variable s.

The ∆W -1 decomposition

Hereafter, we present an algorithm due to V. N. Kublanovskaya and which is called the ∆W -1 decomposition. Given an univariate polynomial matrix M(t), this decomposition transforms M(t) into the form [∆(t), 0] by columns operations, where ∆(t) is a polynomial matrix of full column rank and 0 is a zero block-matrix. Notice that such a transformation is classical for matrices with coefficients in C by using LU-decomposition for instance (see e.g. [START_REF] Luu Ba | Curve/surface intersection problem by means of matrix representation[END_REF] in a similar setting), but for a polynomial matrix this task is much more complicated.

In what follows, we give the ∆W -1 decomposition which is due to V. N. Kublanovskaya [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF]. Anyway, we will provide a detailed presentation and a sketch of proof because this algorithm is very hard to follow directly from [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF].

Suppose given an univariate polynomial matrix M(t) of size m × n and write it under the form

M(t) =[M s,1 , 0, 0, . . . , 0]t s + [M s-1,1 , M s-1,2 , 0, . . . , 0]t s-1 + • • • (4) +[M s-p+2,1 , . . . , M s-p+2,p-1 , 0]t s-p+2 + [M s-p+1,1 , • • • , M s-p+1,p-1 , M s-p+1,p ]t s-p+1 +[M s-p,1 , . . . , M s-p,p-1 , M s-p,p ]t s-p + • • • + [M 0,1 , M 0,2 , . . . , M 0,p ]
where 1 ≤ p ≤ s + 1 and for each j = 1, 2, . . . , p, the block matrices M i, j is of size m × t j for all i = 0, 1, . . . , s. We Proof. Suppose that the matrix M(t) is not of full column rank. Then, there exists a polynomial vector

F(t) ∈ C[t] n×1 , F(t) 0 such that M(t)F(t) = 0.
Denoting by k the maximum of the degree of the entries of F(t), we can write

F(t) = F k t k + F k-1 t k-1 + . . . + F 0
where

F i = (F i,1 , F i,2 , . . . , F i,n ) t ∈ C n×1
, for all i = 0, 1, . . . , k and F k 0. From the equality

M(t)F(t) = 0 = [M s,1 , 0, 0, . . . , 0]F k t s+k + [M s-1,1 , M s-1,2 , 0, . . . , 0]F k + [M s,1 , 0, 0, . . . , 0]F k-1 t s+k-1 + [M s,1 , 0, 0, . . . , 0]F k-2 + [M s-1,1 , M s-1,2 , 0, . . . , 0]F k-1 + [M s-2,1 , M s-2,2 , M s-2,3 , . . . , 0]F k t s+k-2 + • • • + [M 0,1 , M 0,2 , . . . , M 0,p ]F 0
we deduce that the coefficients with respect to the variable t of the matrix M(t)F(t) are null matrices. Moreover, recall that the matrix M = [M s,1 , M s-1,2 , . . . , M s-p+1,p ] is of full column rank by assumption. So, looking at the coefficient of t s+k , we obtain that necessarily

F k,1 = F k,2 = . . . = F k,t 1 = 0.
Looking now at the coefficient of t s+k-1 , we obtain that necessarily

F k-1,1 = F k-1,2 = . . . = F k-1,t 1 = 0 and F k,t 1 +1 = F k,t 1 +2 = . . . = F k,t 1 +t 2 = 0.
Continuing this way step by step, we finally arrive at the conclusion that F k has to be the null vector and hence get a contradiction.

Corollary 2. Let M(t) = t s M s + t s-1 M s-1 + . . . + M 0 be an univariate polynomial matrix of size m × n. If M s is of full column rank then M(t) is of full column rank.

Proof. Apply Lemma 1 where the decomposition ( 4) is taken with p = 1.

We are now ready to describe the ∆W -1 decomposition algorithm. We suppose given an univariate polynomial matrix M(t) of size m × n, of rank ρ and of degree s ≥ 1. We write it as

M(t) = t s M s + t s-1 M s-1 + . . . + M 0
where M 0 , M 1 , . . . , M s are matrices with entries in C. The ∆W -1 decomposition consists in computing two polynomial matrices W(t) and ∆(t) of size n × n and m × ρ respectively, such that

M(t)W(t) = [∆(t), 0] (5)
with the properties that W(t) is unimodular and that ∆(t) if of full column rank and of degree less or equal to s. The notation 0 stands here for the null matrix of size m×(n-ρ). The following algorithm computes two sequences of polynomial matrices M 0 (t) = M(t), M 1 (t), . . . , M l (t) and W 1 (t), . . . , W l (t) such that M l (t) = [∆(t), 0], W k (t) is unimodular and M k (t) = M k-1 (t)W k (t) for all k = 1, 2, . . . , l.

Step 1. Construct an auxiliary matrix N 1 as follows.

(i) If all the columns of M s are nonzero then N 1 := M s . Otherwise, M s contains some zero columns. By performing column permutations, we can transform M s into M * s := [ Ms,1 , 0] where Ms,1 is the nonzero columns of M s of size m × t 1 . This transformation is then applied to the matrices M q for all q = 0, . . . , s -1, which is transformed into M * q := [M q,1 , M q,2 ], where M q,1 , M q,2 are of size m × t 1 and m × (nt 1 ) respectively. (ii) If all the columns of M s-1,2 are nonzero, then

N 1 := [ Ms,1 , M s-1,2 ].
Otherwise, the columns of the matrices M q,2 for all q = 0, . . . , s -1, can be permuted to get M * s-1,2 := [ Ms-1,2 , 0] where Ms-1,2 is the nonzero columns of M s-1,2 of size m × t 2 and M * q,2 := [M q,2 , M q,3 ], q = 0, . . . , s -2. The matrices M q,2 , M q,3 are of size m × t 2 and m × (nt 1t 2 ) respectively.

(iii) if all the columns of M s-2,3 are nonzero, then

N 1 := [ Ms,1 , Ms-1,2 , M s-2,3 ].
Otherwise, the above process will be repeated and it terminates after p ≤ s + 1 steps with a matrix

N 1 := [ Ms,1 , Ms-1,2 , Ms-2,3 , . . . , Ms-p+2,p-1 , M s-p+1,p ]
built with block-matrices of size m × t 1 , m × t 2 , . . . , m × t p-1 and m × (n -δ p-1 ) respectively, where δ k = k i=1 t i .

(iv) If p < s + 1, then all the columns of N 1 are nonzero. If p = s + 1, the last columns of N 1 may be zero columns.

In this case, we can reduce the matrix M(t) by deleting zero columns and thus get a polynomial matrix M (t) of smaller size, say m × n 1 , n 1 ≤ n. We get

N 1 := [ Ms1 t 1 , Ms-1,2 t 2 , . . . , Ms-p+2,p-1 t p-1
, Ms-p+1,p Step 2. If N 1 is of full column rank, then ∆(t) = M (t) because M (t) is of full column rank (Lemma 1). The algorithm stops here. Otherwise, find an n 1 × (n 1r 1 ) matrix T 1 whose columns form a basis of the right null space of the matrix N 1 (r 1 := rank N 1 ).

Step 3. The matrix T 1 is transformed into a lower triangular matrix L 1 of size n 1 × h 1 , h 1 ≥ n 1r 1 , without permuting rows. The matrix L 1 is such that its columns contain a basis of the null space of the matrix N 1 and possibly some columns of the identity matrix. The process to get the matrix L 1 from T 1 can be described in the following way.

In the case the leading minor of size n 1r 1 of the matrix T 1 is not equal to zero, we obtain L 1 of size n 1 × (n 1r 1 ) by performing a Gaussian elimination by columns. In the case the leading minor of size n 1r 1 of matrix T 1 is equal to zero, we also perform a Gaussian elimination by columns and proceed as follows: if the first entry on the diagonal is nonzero then do nothing, otherwise insert a column on the left having a 1 at the first position and zero elsewhere. Then, if the second entry on the diagonal is non-zero do nothing, otherwise insert a column between the first and second column with a 1 at the second position and zero elsewhere. We continue like this and thus insert a column each time there is a zero element on the diagonal. In this way, we end up with a matrix L 1 of size where all the elements on the diagonal are nonzero.

n 1 × h 1 , h 1 ≥ n 1 -r 1 , of the form L 1 =                                     . . .
For the following steps, we will assume for simplicity that L 1 is of size n 1 × (n 1r 1 ). Notice that if h 1 > n 1r 1 , we only have to replace hereafter the number n 1r 1 with h 1 and the identity matrix I r 1 with I n 1 -h 1 .

The matrix L 1 can written in block-matrices as follows:

(i) If δ k-1 ≤ n 1 -r 1 and δ k > n 1 -r 1 for all k ≤ p -1 then L 1 = t 1 { t 2 { . . . t k { . . . t p {                                       L 1,1 0 . . . . . . 0 L 2,
                                      (6)
where L i,i , i = 1, 2, . . . , k -1 are nonsingular lower triangular matrices of size t i × t i and L p,k is a lower triangular matrix of size

t k × (n 1 -r 1 -δ k-1 ), so that t k = n 1 -r 1 -δ k-1
, and of full column rank.

(ii) If δ k-1 ≤ n 1 -r 1 and δ k > n 1 -r 1 only for k = p -1 then L 1 = t 1 { t 2 { . . . t p-1 { t p {                              L 1,1 0 . . . . . . 0 L 2,1 L 2,2 0 . . . 0 . . . . . . . . . . . . 0 L p-1,1 L p-2,2 . . . L p-1,p-1 0 L p,1 t 1 L p,2 t 2 . . . L p,p-1 t p-1 L p,p t p                              (7)
where L i,i , i = 1, 2, . . . , p -1 are nonsingular lower triangular matrices of size t i × t i and L pp is a lower triangular matrix of size t p × (n 1r 1 -δ p-1 ), so that t p = n 1r 1 -δ p-1 , and of full column rank.

Step 4. Construct a left triangular unimodular n 1 × n 1 matrix W (1) (t) as follows (i) If L 1 is of the form (6) then

W (1) (t) =                               L 1,1 0 . . . . . . 0 tL 2,1 L 2,2 0 . . . 0 . . . . . . . . . . . . 0 t k-1 L k,1 t k-2 L k,2 . . . L k,k 0 . . . . . . . . . . . . . . . t p-1 L p,1 t p-2 L p,2 . . . t p-k L p,k I r 1                              
where I r 1 is the identity matrix of size r 1 .

(ii) If L 1 is of the form (7) then Then, we define the unimodular polynomial matrix

W (1) (t) =                               L 1,
W 1 (t) =        W (1) (t) if n = n 1 , diagonal{W (1) (t), I n-n 1 } if n > n 1 .
Step 5. Compute the matrix

M 1 (t) = M 0 (t)Ω 1 W 1 (t) = M 1 0 + tM 1 1 + . . . + t s 1 M 1 s 1
where s 1 ≤ s and Ω 1 is a permutation matrix corresponding to the first step of this algorithm.

Step 6. Starting with j = 1, we repeat the steps ( 1)-( 5) for the matrix M j (t) until we find a matrix M l+1 (t) of full column rank. Then, we get the ∆W -1 decomposition

M l (t) = M(t)W(t) = [∆(t), 0]
where

W(t) = Ω l i=1 Ω i W i (t) is an n × n unimodular polynomial matrix, ∆(t) is a polynomial matrix of full column rank
and Ω is a permutation matrix corresponding to a last Gaussian elimination by columns.

Sketch of proof of the ∆W -1 decomposition algorithm. First, we see that the choice of the unimodular matrices W i (t) does not increase the degree of the matrix M(t) under transformation. Thus, the degree of ∆(t) is not greater than the degree of M(t). Second, at each loop k of the algorithm, the transformations eliminate (n kr k ) > 0 vector coefficients at the greatest degree in t of the columns of the polynomial matrix M k-1 (t), this for all k = 1, 2, . . . , l + 1. Therefore, after a finite number of steps, the resulting matrix will have zero columns and its size can be reduced by deleting these zero columns, so that n k < n k-1 . The matrices M k (t) and M k-1 (t) have at least r k identical columns whose vector coefficients at the greatest degree are linearly independent. Thus, r k+1 ≥ r k . Therefore, the number (n kr k ) decreases in a finite number of steps of the algorithm and finally, after the loop number l we get n l+1r l+1 = 0 and the algorithm stops here.

Finally, the matrix ∆(t) can be written under the form ∆(t) =[ ∆s,1 , 0, 0, . . . , 0]t s + [∆ s-1,1 , ∆s-1,2 , 0, . . . , 0]t s-1 + . . .

+[∆ s-p+2,1 , . . . , ∆s-p+2,p-1 , 0]t s-p+2 + [∆ s-p+1,1 , . . . , ∆ s-p+1,p-1 , ∆s-p+1,p ]t s-p+1 +[∆ s-p,1 , . . . , ∆ s-p,p-1 , ∆ s-p,p ]t s-p + . . . + [∆ 0,1 , ∆ 0,2 , . . . , ∆ 0,p ].
By construction, the matrix N l+1 = [ ∆s,1 , ∆s-1,2 , . . . , ∆s-p+1,p ] is of full column rank. By Lemma 1, we deduce that ∆(t) is of full column rank. .

Example 1. Let M(t) be an univariate polynomial matrix

M(t) :=               2t 2 + 3t + 1 t + 1 2t 2 + 2t 1 5t 2 -5t 2 + 1 2t + 1 3 2t -2 t t 0           t 2 t 2 1 -1 + t 3 -t 0 t 1 -t           =           0 0 0 1 0 0 0 0 0           t 3 +           1 1 0 0 0 0 0 0 0           t 2 +           0 0 0 0 -1 0 1 0 -1           t +           0 0 1 -1 0 0 0 1 0           is of full column rank because the matrix           0 1 0 1 0 0 0 0 -1          
is of full column rank by Lemma 1.

Remark 2. A Maple experimental program to perform the ∆W -1 decomposition of an univariate polynomial matrix have been implemented and is freely available at the URL: http://cgi.di.uoa.gr/ ~thanglb/.

The algorithm for extracting the regular part of a non square bivariate pencil of matrices

In the rest of this section, we provide an algorithm that extracts the continuous spectrum from a linearized bivariate pencil of matrices. We first state the main theorem and then give the algorithm.

Theorem 2 ( [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF][START_REF] Kublanovskaya | Spectral problems for pencils of polynomial matrices. methods and algorithms v[END_REF]). A m × n-pencil of polynomial matrices M(s, t) = A(t) -sB(t) is equivalent to a pencil of the following form

          M 1,1 (s, t) 0 0 M 2,1 (s, t) M 2,2 (s, t) 0 M 3,1 (s, t) M 3,2 (s, t) M 3,3 (s, t)           (8)

where

• the pencil M 2,2 (s, t) is a regular pencil that corresponds to the continuous spectrum of M(s, t),

• the pencil M 1,1 (s, t) is of full row rank and determines the one-dimensional eigenvalues of the form (0, t),

• the pencil M 3,3 (s, t) is of full column rank and determines the one-dimensional eigenvalues of the form (∞, t),

• the union of the discrete spectrum of the pencil M 1,1 (s, t) and M 3,3 (s, t) coincides with the discrete spectrum of M(s, t).

We now describe an algorithm for constructing a pencil of the form [START_REF] Busé | Torsion of the symmetric algebra and implicitization[END_REF]. Set ρ = rank A(t), A 1,1 (t) = A(t) and B 1,1 (t) = B(t).

Step 1.

i) Transform A 1,1 (t) into the form [∆ 0 (t), 0] by the ∆W -1 decomposition, that means A 1,1 (t)Q 0 (t) = [∆ 0 (t), 0]
where Q 0 (t) is an unimodular matrix. Then, compute

B 1,1 (t)Q 0 (t) = [ B 1 (t) ρ | B 2 (t) n-ρ ].
ii) Determine an unimodular matrix P 0 (t) such that

P 0 (t)B 2 (t) = B1,1 (t) 0
where B1,1 (t) has full row rank. At the end of ii), matrices A(t) and B(t) are represented under the form

P 0 (t)A 1,1 (t)Q 0 (t) = A 2,1 (t) 0 A 2,2 (t) 0 , P 0 (t)B 1,1 (t)Q 0 (t) = B 2,1 (t) B1,1 (t) B 2,2 (t) 0
where B1,1 (t) has full row rank and A 2,1 (t) A 2,2 (t) has full column rank. We have

P 0 (t)(A 1,1 (t) -sB 1,1 (t))Q 0 (t) = A 2,1 (t) -sB 2,1 (t) -s B1,1 (t) A 2,2 (t) -sB 2,2 (t) 0 .
iii) By permuting rows, we obtain the matrix

PP 0 (t)(A 1,1 (t) -sB 1,1 (t))Q 0 (t) = A 2,2 (t) -sB 2,2 (t) 0 A 2,1 (t) -sB 2,1 (t) -s B1,1 (t)
where P is a permutation matrix.

Step 2. If the matrix A 2,2 (t) is not of full column rank, we repeat the Step 1 for the pencil A 2,2 (t) -sB 2,2 (t) until, after k repetitions, we get a matrix A k+1,k+1 (t) which is of full column rank. Thus, we obtain the pencil

P(t)M(s, t)Q(t) = A k+1,k+1 (t) -sB k+1,k+1 (t) 0 A k+1,k (t) -sB k+1,k (t) M 3,3 (t)
where P(t), Q(t) are unimodular matrices.

If the pencil of the m 1 × n 1 matrix A k+1,k+1 (t) -sB k+1,k+1 (t) is not a regular pencil, in particular it is not a square matrix and not of full row rank, then we repeat the above procedure to the transposed pencil A t k+1,k+1 (t) -sB t k+1,k+1 (t). The steps consist in the following operations. Set Ã1,1 (t) = A k+1,k+1 (t), B1,1 (t) = B k+1,k+1 (t). i) Transform the transposed matrix Bt where B2 (t) = ∆t 0 (t). ii) Determine an unimodular matrix P0 (t) such that Ã1 (t) P0 (t) = Ā1,1 (t) 0 where Ā1,1 (t) is a ρ × q matrix of full column rank. At the end of ii), the pencil Ã1,1 (t)s B1,1 (t) is represented under the form

Q t 0 (t)( Ã1,1 (t) -s B1,1 (t)) P0 (t) = Ã2,1 (t) -s B2,1 (t) Ã2,2 (t) -s B2,2 (t) Ā1,1 (t) 0 .
iii) By permuting columns, we obtain the matrix

Q t 0 (t)( Ã1,1 (t) -s B1,1 (t)) P0 (t)C = Ã2,2 (t) -s B2,2 (t) Ã2,1 (t) -s B2,1 (t) 0 Ā1,1 (t)
where C is a permutation matrix.

If the matrix B2,2 (t) is not of full row rank, we repeat the above procedure to the pencil Ã2,2 (t)s B2,2 (t), say l times, until the matrix Bl+1,l+1 (t) is of full row rank. In this way, we obtain the regular pencil Ãl+1,l+1 (t)s Bl+1,l+1 (t).

At the end, we obtain the following pencil which is equivalent to M(s, t):

P(t)M(s, t)Q(t) =           M 1,1 (s, t) 0 0 M 2,1 (s, t) M 2,2 (s, t) 0 M 3,1 (s, t) M 3,2 (s, t) M 3,3 (s, t)          
where P(t), Q(t) are unimodular matrices.

The pencil M 2,2 (t) = Ãl+1,l+1 (t)s Bl+1,l+1 (t) is regular. The pencil

M 1,1 (t) =                  Āl,l (t) Ãl,l-1 (t) -s Bl,l-1 (t) . . . Ãl,1 (t) -s Bl,1 (t) 0 Āl-1,l-1 (t) . . . Ãl-1,1 (t) -s Bl-1,1 (t) 0 0 . . . . . . 0 . . . 0 Ā1,1 (t)                 
is of full column rank and its spectrum does not contain any part of the continuous spectrum of M(s, t), except for the one-dimensional eigenvalue of the form (∞, t). The pencil

M 3,3 (s, t) =                  -s Bk,k (t) 0 0 . . . 0 A k-1,k (t) -sB k-1,k (t) -s Bk-1,k-1 (t) 0 . . . 0 . . . . . . . . . . . . . . . A 1,k (t) -sB 1,k (t) A 1,k-1 (t) -sB 1,k-1 (t) A 1,k-2 (t) -sB 1,k-2 (t) . . . -s B1,1 (t)                 
is of full row rank and its spectrum does not contain any part of the continuous spectrum of M(s, t), except for the one-dimensional eigenvalue of the form (0, t).

Sketch of proof of Theorem 2

At the Step 1-i) of the algorithm, we can separate Q 0 (t) = [Q 0,1 (t), Q 0,2 (t)] where

A(t)Q 0,1 (t) = ∆ 0 (t) and A(t)Q 0,2 (t) = 0.
Therefore, the columns of Q 0,2 (t) form a basis of right polynomial solutions of A(t) and the finite spectrum of ∆ 0 (t) coincides with the finite spectrum of A(t). At the Step 1-ii), the unimodular matrix P 0 (t) is written under the form P 0 (t) = P 0,1 (t) P 0,2 (t) where P 0,1 (t)B 2 (t) = B1,1 (t) and P 0,2 (t)B 2 (t) = 0.

The rows of P 0,2 (t) form a basis of left polynomial solutions of B 2 (t) and the finite spectrum of B1,1 (t) coincides with the finite spectrum of B 2 (t). From

P 0 (t)(A(t) -sB(t))Q 0 (t) = A 2,1 (t) -sB 2,1 (t) -s B1,1 (t) A 2,2 (t) -sB 2,2 (t) 0 ,
we deduce that the two subspaces Q 0,1 (t) and P t 0,2 (t) form a pair of reducing subspaces (for instance, see [START_REF] Kublanovskaya | Spectral problems for pencils of polynomial matrices. methods and algorithms v[END_REF][START_REF] Stewart | On the sensitivity of the eigenvalue problems ax = λbx[END_REF]) for the pencil M(s, t) = A(t) -sB(t). By [15, Theorem 3.2], the union of the corresponding spectral characteristics of the blocks -s B1,1 (t) and A 2,2 (t) -sB 2,2 (t) gives the whole spectrum and the right and left minimal indices with respect to s of the original pencil M(s, t). For more details, we refer the interested reader to [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF][START_REF] Kublanovskaya | Spectral problems for pencils of polynomial matrices. methods and algorithms v[END_REF][START_REF] Stewart | On the sensitivity of the eigenvalue problems ax = λbx[END_REF]. Before giving an illustrative example, mention that it is also possible to give algorithms to extract the discrete spectrum of a linearized pencil of polynomial matrices. However, as we will not need it to treat the surface/surface intersection problem, we refer the interested reader to [START_REF] Kublanovskaya | Methods and algorithm of solving spectral problems for polynomial matrices and rational matrix[END_REF][START_REF] Kublanovskaya | Spectral problems for pencils of polynomial matrices. methods and algorithms v[END_REF] or [START_REF] Ba | Matrix-based implicit representations of algebraic curves and surfaces and applications[END_REF].

Example 3. Suppose given the bivariate linearized pencil of matrices M(s, t) = A(s) -tB(s) where

A(s) =           -s 3 -s 2 s 2 0 s 0 1 0 -s 2 -s + 1 -s -1 s 1           , B(s) =           -s 2 -s -s -1 s + 1 0 s + 1 1 1 0 1 + 2s 2 -1 1                -1 + s 1 -2 0 3s -2s 2 1 -2s -1 + 4s 0 s 2 0 0 0           and B 1 (s) := P 0 (s)B(s)Q 0 (s) =           -2 1 -1 1 -1 + 4s 1 -2s 1 + 2s 0 s + 1 0 0 0          
.

Therefore, we obtain the matrices

A 2 (s) := 3s -2s 2 1 -2s -1 + 4s s 2 0 0 , B 2 (s) := -1 + 4s 1 -2s 1 + 2s s + 1 0 0 .
Applying the ∆W -1 decomposition to the matrices A 2 (s) and B 2 (s), we compute the unimodular polynomial matrices

P 1 (s) := 1 0 0 1 , Q 1 (s) :=           1 0 0 0 1 2 -8s 0 1/2 2 -4s           such that A 3 (s) := P 1 (s)A 2 (s)Q 1 (s) = 3s -2s 2 1 2 0 s 2 0 0 and B 3 (s) := P 1 (s)A 2 (s)Q 1 (s) = -1 + 4s 3 2 -s 4 -12s + 8s 2 s + 1 0 0 .
At last, we can transform the pencil of matrices M(s, t) into the pencil

          -1 + s 1 -2 0 3s -2s 2 1 2 0 0 s 2 0 0 0           -t           -2 1 -1 1 -1 + 4s 3 2 -s 4 -12s + 8s 2 0 s + 1 0 0 0           where M 1 (s, t) := [s 2 ] -t[s + 1] is the regular part of M(s, t) and M 2 (s, t) := 1 -2 0 1 2 0 0 -t 1 -1 1 3 2 -s 4 -12s + 8s 2 0
is of full row rank and determines the discrete spectrum of M(s, t). Hence, the one-dimensional eigenvalue of M(s, t) is given by the zero locus of s 2t(s + 1) = 0 and we can easily see that the zero-dimensional eigenvalue of M(s, t) is given by the pair (s, t) = (1, 1).

Remark 3. A Maple experimental program corresponding to the above algorithm have been implemented and is freely available at the URL: http://cgi.di.uoa.gr/ ~thanglb/.

Algorithm and illustrative examples

Let us take again the setting and notation of Section 3. As a consequence of Theorem 1, the points in S 1 ∩ S 2 that are associated to points (s : t : u) ∈ P 2 such that u 0, are in correspondence with the spectrum of M(s, t, 1) and moreover, this spectrum is one-dimensional, it has no discrete component. Therefore, we can apply the results of Section 4 and we get the following algorithm:

Algorithm 1: Matrix representation of an intersection curve

Input: Two parameterized algebraic surfaces S 1 and S 2 such that the parameterization of S 1 has local complete intersection base points. Output: The intersection curve S 1 ∩ S 2 represented as a matrix determinant. 1. Compute a matrix representation of S 1 , say M(x, y, z, w) -see Section 2. 2. Substitute x, y, z, w by the parameterization of S 2 in the matrix M to get a matrix M(s, t) (set u = 1). 3. Compute the generalized companion matrices A(s) and B(s) associated to M(s, t) -see Section 4. 4. Return the regular pencil of matrices M 1 (s, t) = A 1 (s) -tB 1 (s) -see Section 4.

In comparison with [START_REF] Manocha | A new approach for surface intersection[END_REF], our algorithm returns a result of the same type: a determinant matrix representation of the intersection curve, but the class of parameterizations of surfaces for which step 1 can be performed is here dramatically extended. We end this paper by giving some illustrative examples.

Intersection of a sphere and a Steiner surface

Let S 1 be the sphere that we parameterized by φ 1 : P 2 → P 3 : (s : t : u) → (s 2 + t 2 + u 2 : 2su : 2st :

s 2 -t 2 -u 2 )
and let S 2 be the Steiner surface parametrized by φ 2 : P 2 → P 3 : (s : t : u) → (s 2 + t 2 + u 2 : tu : su : st).

The computation of a matrix representation of the sphere S 1 yields

          -y 0 z x + w 0 -y -x + w -z z x + w y 0           .
Therefore, the intersection locus S 1 ∩ S 2 is in correspondence with the spectrum of the polynomial matrix

M(s, t, u) =           -tu 0 su s 2 + t 2 + u 2 + st 0 -tu -s 2 -t 2 -u 2 + st -su su s 2 + t 2 + u 2 + st tu 0          
.

In order to apply our reduction algorithm on this matrix, we need to dehomogenize; for instance we choose here u = 1 (notice that the case u = 0 could also be treated as a curve/surface intersection problem as it is explained in [START_REF] Luu Ba | Curve/surface intersection problem by means of matrix representation[END_REF]). So, we want to compute the spectrum of

M(s, t) =           -t 0 s s 2 + t 2 + 1 + st 0 -t -s 2 -t 2 -1 + st -s s s 2 + t 2 + 1 + st t 0               
.

We get a curve of degree 6, as expected since it is the result on the intersection of a surface of degree 2 and a surface of degree 3. We could compute det(M 1 (s, t)) = -s 6 -2s 3 t 3 + t 2 s 2 + s 2 + 2stt 6 + t 2 + 1 that is the equation of the curve C (see Figure 1) that parameterizes S 1 ∩ S 2 (see Figure 2) through the regular map φ 2 . Notice that there are many methods to draw the intersection curve S 1 ∩ S 2 from the parametric curve C through the regular map φ 2 ; see for example [START_REF] Mantzaflaris | A subdivision approach to planar semi -algebraic sets[END_REF].

                        
.

By dehomogenizing with respect to the variable u, we consider

M(s, t) =                          -s 3 -t 3 0 -st 0 -st st 0 s + t 0 st -st 0 1 0 -s 3 -t 3 -st 0 0 0 0 1 0 0 0 s + t 0 -s 3 -t 3 1 0 0 -st 0 s + t 0 -st st 0 1 0 0 0 s + t 0 0 st 1 0 0 0 s + t 0 0 0 st
Its yields a plane curve of degree 6 whose implicit equation is det(M 1 (s, t)) = t 2 + 2st + s 2 t 2 + 2s 3 t 3st 5 + s 2ts 5 . This plane curve parameterizes S 1 ∩ S 2 through the regular map φ 2 .

Conclusion

Given two parameterized surfaces, this paper proposes a new method for computing an equation of a plane curve that is in correspondence with the intersection space curve of these two surfaces for very general parameterizations. This operation is the first step of the whole treatment of the intersection of two parameterized surfaces following an approach that has been introduced by Canny and Manocha [START_REF] Manocha | A new approach for surface intersection[END_REF]. Our results allow to remove the strong assumptions that was necessary to require on the surface parameterizations, making this approach applicable for two general surface parameterizations. In a future work, we plan to study the computational complexity of this algorithm which is difficult to determine because of the reduction of pencil of matrices based on Kublanovskaya decomposition.

Lemma 1 .

 1 n and the notation 0 stands for a zero block-matrix of appropriate size. Suppose given an univariate polynomial matrix M(t) of size m × n and an integer p such that 1 ≤ p ≤ s + 1 and (4) holds. If the matrix M = [M s1 , M s-1,2 , . . . , M s-p+1,p ] is of full column rank then the matrix M(t) is of full column rank.

  n 1 and all the columns of N 1 are nonzero columns.

Figure 1 :Figure 2 :

 12 Figure 1: The plane curve C corresponding with S 1 ∩ S 2

Recall that given two m × n matrices A and B, a (linear) pencil of matrices is a matrix-valued function A + λB which is defined over C.

Acknowledgements. The second author is partially supported by Marie-Curie Initial Training Network "SAGA" (ShApes, Geometry, Algebra).


Anthony Martin

Olivier Alibart

Daniel Barry Ostrowsky

Marc P De Micheli

Sébastien Tanzilli
email: sebastien.tanzilli@unice.fr

A quantum relay chip based on telecommunication integrated optics technology

Keywords: numbers: 42.50.Dv, 42.65.Lm, 42.82.Et, 03.67.Hk

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

The field of quantum information relies on the attractive possibility of exploiting the quantum realm to accomplish tasks not accessible to traditional information processing and communication systems [START_REF] Nielsen | Quantum computation and quantum information[END_REF]. This prospect has, over the two last decades, attracted the common interest of scientists from a wide range of disciplines including physics, mathematics, information theory, and engineering [START_REF] Zoller | Quantum information processing and communication[END_REF]. Quantum superpositions of states and entanglement are now seen as resources to treat quantum bits (qubits) of information [START_REF] Weihs | Photonic entanglement for fundamental tests and quantum communication[END_REF]. From the fundamental side, entanglement permitted, for instance, testing non-locality over long distances [START_REF] Marcikic | Distribution of time-bin entangled qubits over 50 km of optical fiber[END_REF][START_REF] Ursin | Entanglement-based quantum communication over 144 km[END_REF][START_REF] Hübel | Highfidelity transmission of polarization encoded qubits from an entangled source over 100 km of fiber[END_REF][START_REF] Dynes | Efficient entanglement distribution over 200 kilometers[END_REF]. From the more applied side, quantum key distribution offers a secure means to establish secret keys between distant partners, useful for one-time-pad encryption, with a security level unattainable with classical methods [START_REF] Gisin | Quantum cryptography[END_REF][START_REF] Dušek | Quantum cryptography[END_REF]. Despite encouraging results, no actual breakthrough, in terms of maximal distance separating the partners, has been achieved so far. Basically, inherent losses in fibre channels and dark-counts in the detectors prevent extending the distance to more than 200 km [START_REF] Takesue | Quantum key distribution over a 40-dB channel loss using superconducting single-photon detectors[END_REF]. A viable possibility for extending the distance is based on quantum relay schemes, where the basic idea is to break the overall channel into several shorter sub-sections [START_REF] Collins | Quantum relays for long distance quantum cryptography[END_REF]. Here another quantum communication protocol, known as quantum teleportation, lies at the heart of quantum relays [START_REF] Bennett | Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels[END_REF].

While these are seminal experiments, it is only through a technology, such as integrated optics, that one can progress towards practical, standardized, low cost, interconnectable, and reconfigurable elements. Similarly to the extraordinary technological developments achieved in fibre optical telecommunications, integrated optics has proven to be a powerful enabling technology for realizing guided-wave optical quantum devices [START_REF] Tanzilli | On the genesis and evolution of integrated quantum optics[END_REF], such as high efficiency entanglement sources [START_REF] Tanzilli | PPLN waveguide for quantum communication[END_REF][START_REF] Martin | A polarization entangled photon-pair source based on a type-II PPLN waveguide emitting at a telecom wavelength[END_REF] as well as elementary quantum functions, such as quantum interfaces [START_REF] Tanzilli | A photonic quantum information interface[END_REF] and memories [START_REF] Saglamyurek | Broadband waveguide quantum memory for entangled photons[END_REF]. Today's integration efforts are pushing one step further towards merging, onto the same chip, several elementary functions so as to achieve complex operations. For instance, Shor's quantum factoring [START_REF] Politi | Shor's quantum factoring algorithm on a photonic chip[END_REF] and two-photon quantum random walks [START_REF] Owens | Two-photon quantum walks in an elliptical direct-write waveguide array[END_REF] have been demonstrated using dedicated integrated quantum optical circuits. In the framework of long-distance quantum communication, we show in this paper how integrated optics on lithium niobate permits realizing a telecom-like quantum relay chip that could achieve the quantum relay function, in a compact, stable, efficient, and user-friendly fashion. Such a novel quantum relay circuit merges, for the first time, both nonlinear electrooptical and optical-optical effects, in view of offering a reliable way to achieve long distance quantum communication. Furthermore, as will be discussed in the following, integrated optics on lithium niobate offers the possibility to implement electro-optically controllable functions, such as photon routers and/or (de-)multiplexers. This paves the way for the design of next generation, i.e. showing reconfigurable capabilities, quantum optical circuits. We start by describing our optical device with which on-chip teleportation could be realized and briefly discuss about the extension of the maximum achievable distance in one-way quantum communication. Then, we present the classical characterizations of the two implemented nonlinear effects. Finally, we demonstrate the proof-of-principle of the quantum relay function, based on the so-called Hong-Ou-Mandel (HOM) two-photon interference effect which lies at the heart of the teleportation protocol [START_REF] Hong | Measurement of subpicosecond time intervals between two photons by interference[END_REF][START_REF] De Riedmatten | Teleportation in the quantum relay configuration[END_REF][START_REF] Halder | Photon-bunching measurement after two 25-km-long optical fibers[END_REF][START_REF] Aboussouan | High-visibility two-photon interference at a telecom wavelength using picosecond-regime separated sources[END_REF].

C2 + + + + + + _ _ _ _ _ _

PPLN zone pairs of electrodes

Quantum relay chip

A quantum relay chip based on integrated optics

Figure 1 depicts the chosen integrated optical design for merging all the necessary functions on the same chip for enabling the process of teleportation which lies at the heart of the quantum relay operation [START_REF] Collins | Quantum relays for long distance quantum cryptography[END_REF][START_REF] Aboussouan | High-visibility two-photon interference at a telecom wavelength using picosecond-regime separated sources[END_REF]. Let's suppose that Alice sends an unknown qubit a, for instance encoded on the time-bin observable [START_REF] Weihs | Photonic entanglement for fundamental tests and quantum communication[END_REF], carried by a telecom wavelength photon, travelling along a fiber quantum channel connected to port 1 of the relay chip. At the same time, a photon, from a pump laser pulse emitting in the visible range of wavelength, synchronized with the arrival time of qubit a, enters the nonlinear optical section of the chip (port 2). This section consists of a channel waveguide integrated on periodically poled lithium niobate (PPLN). Thanks to an appropriate choice of the poling period, this pump photon can be converted, by spontaneous parametric down-conversion (SPDC), into a pair of, say time-bin, entangled photons (b and c) whose wavelengths are identical to that of the photon carrying qubit a [START_REF] Tanzilli | PPLN waveguide for quantum communication[END_REF]. Then, the first 50/50 directional coupler (C 1 ) is used to separate the created pairs in such a way that photons a (sent by Alice) and b enter the second 50/50 coupler (C 2 ) from each port. Note that the afore mentioned synchronization requirement between a and b ensures that these photons enter C 2 simultaneously within their coherence time.

Here, C 2 plays the role of a Bell state measurement (BSM) apparatus, which makes the latter requirement a crucial feature for having this operation working properly. In this case, if conditions on the polarization states, central wavelengths, and coherence times are met, qubits a and b can be projected onto one of the four entangled Bell states identified when two detectors placed at the output of the chip (D a and D b in Figure 1) fire simultaneously and lead to a registered coincidence (&) [START_REF] De Riedmatten | Teleportation in the quantum relay configuration[END_REF]. As a result of this measurement, the qubit initially carried by photon a has been teleported to photon c that exits the chip at port C, without, theoretically, any loss in its quantum properties [START_REF] Bennett | Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels[END_REF]. This is made possible since qubits c and b are initially entangled, meaning, from the quantum point of view, that the key resource of entanglement has been consumed during the process. In addition, note that the initial qubit has not been cloned since photons a and b have been annihilated. As a consequence, the resulting electrical trigger from the measurement is not only the signature of the presence of the initial carrier at the relay chip location, but also of the departure of a photon carrying the same qubit that remains unknown. This allows triggering Bob's detectors at the end of the channel, therefore increasing the overall channel signal to noise ratio, and consequently the communication distance.

This "folded-version" of the usual quantum relay is well adapted to the pointto-point telecommunication approach, i.e., a classical heralding signal propagating through the channel along with the teleported qubit. Moreover, it still improves the distance of any one-way quantum communication protocol and can obviously be more straightforwardly integrated within a telecom-like optical circuit. Figure 2 provides a comparison between normalized bit rates as a function of the distance for direct, as well as quantum relay based, one-way quantum communication links. On one hand, it shows that a chip, ideal in terms of both coupling and propagation losses, could improve the distance up to a factor of 1.8. On the other hand, a realistic chip, featuring loss figures as described in the following section, provides an increase of the distance by a factor of 1.4. In addition, these are compared with the usual lossless quantum relay scheme [START_REF] Collins | Quantum relays for long distance quantum cryptography[END_REF].

Realization and classical characterization

From the technological side (see figure 1), the chip features a waveguide quantum circuit consisting of a photon-pair creation zone and two tunable couplers merged onto a 5 cmlong sample.

Generally speaking, the waveguiding structures are obtained by soft proton exchange (SPE) [START_REF] Chanvillard | Soft Proton Exchange on PPLN: a simple waveguide fabrication process for highly efficient non-linear interactions[END_REF]. This technique enables strong light confinement (δn ≃ 2.2 • 10 -2 ) over long lengths, associated with both low propagation losses (∼0.3 dB/cm) and very /ns associated with 10% detection efficiencies (obtainable from commercially available InGaAs avalanche photodiode modules), and a quantum teleportation fidelity of 0.8 (as obtained in [START_REF] De Riedmatten | Teleportation in the quantum relay configuration[END_REF]). This simulation proposes a comparison between a direct quantum communication link without any relay (red), and a standard quantum relay protocol based on the teleportation scheme (violet), together with its "folded-version" implemented using the actual relay chip (blue). In addition, the performance of a lossless relay chip is provided in order to show the potential improvement related to better technological fabrication of the chip (green). Absolute key rates can be obtained by multiplying the numbers on the y-axis by the pump laser repetition rate.

high conversion efficiencies when nonlinear optical processes are implemented using PPLN sections [START_REF] Tanzilli | PPLN waveguide for quantum communication[END_REF]. However, this technique leads only to an extraordinary index increase, meaning that only TM polarization modes can be guided in such structures. As a consequence, SPE waveguide devices cannot handle polarization qubits, as opposed to titanium in-diffused structures [START_REF] Martin | A polarization entangled photon-pair source based on a type-II PPLN waveguide emitting at a telecom wavelength[END_REF][START_REF] Zhong | High-quality fiber-optic polarization entanglement distribution at 1.3 nm telecom wavelength[END_REF].

Considering the photon-pair generation section, the SPDC process is ruled by energy and momentum conservation laws. In this waveguide configuration, the latter is achieved using the so-called quasi-phase matching technique which compensates periodically for the dispersion between the three interacting photons (pump, b and c). This allows phase-matching any desired wavelengths when the poling period is properly engineered. In our case, thanks to a poling period of 16.6 µm, the photon-pair source is designed to ensure the conversion of 766 nm pump photons into two degenerate photons at 1532 nm (telecom C-band). Photon-pair sources based on SPE:PPLN waveguides have been demonstrated to be highly efficient and excellent providers of photonic . SPDC from the nonlinear waveguide zone. Outputs A and B correspond to the top outputs where the BSM is to be performed while the C output is the bottom output for the teleported qubit. Faithful characterization of the nonlinear interaction is provided by the sum of these three outputs. The difference between the three outputs is due to unwanted broadband wavelength sensitivity of the couplers. This behavior is explained by irregularities in the fabrication process leading to asymetric waveguides. Moreover, usual Cerenckov effect is observed on the left side of the fluorescence peaks [START_REF] Ito | Cerenkov-type second harmonic generation from a LiNbO 3 waveguide with a periodic domain grating[END_REF].

entanglement [START_REF] Tanzilli | PPLN waveguide for quantum communication[END_REF][START_REF] Tanzilli | A photonic quantum information interface[END_REF][START_REF] Halder | High coherence photon pair source for quantum communication[END_REF]. For our chip, we used a 1 cm-long SPE:PPLN section which leads to the SPDC response shown in figure 3 when pumped by a picosecond regime laser at 766 nm and heated at a temperature of 80 ℃. One can see that the SPDC signal is distributed at the three output ports of the chip due to the presence of the two couplers. To characterize more completely the nonlinear interaction, the sum of these three contributions has been computed and added to the picture as the pink/square curve. We get here, as expected, degenerate paired photons around 1532 nm, and the obtained spectral FWHM is of 80 nm. The directional couplers C 1 and C 2 , represented in figure 1, consist of two waveguides integrated close to each other over a given length [START_REF] Papuchon | Electrically switched optical directional coupler: Cobra[END_REF][START_REF] Kogelnik | Switched directional couplers with alternating δβ[END_REF][START_REF] E L Wooten | A review of lithium niobate modulators for fiber-optic communications systems[END_REF]. If the spacing between the waveguides is sufficiently small, all the energy can be transferred from one to the other through evanescent coupling after a characteristic length. Afterwards, controllable decrease of the coupling ratio is achieved by detuning the propagation constant between the two waveguides by means of the nonlinear electro-optical effect. Numerical simulations have been carried out using the beam propagation method (BPM) in order to choose and optimize the bends, the spacing between the two waveguides, and the associated coupling length. Here the radius of the bends have to be carefully chosen since too small radii would introduce important losses while the opposite would lead to too long a chip. We selected 10 mm long sinusoidal bends, corresponding to geometrical losses lower than 1 dB regarding the propagation over the entire component. Note that the waveguides input/output spacing was imposed by external consideration since standard V-grooves with 250 µm separated fibers were used at both end facets to couple photons in and out of the chip. With the constraint of single mode behaviour in the bends, we selected couplers made of 5 µm-width waveguides separated by 4 µm capable of ensuring a total energy transfer after a 9 mm length. Electrodes, deposited on top of the two coupled waveguides with a silica buffer layer, are used to tune the coupling ratio from approximately 0:100 (transmission) to 100:0 (reflection). Figure 4 presents the characterization of the two couplers at 1532 nm in the classical regime with a narrowband laser (Yenista Tunics) and in the photon counting regimes with a 1 nm-bandwidth heralded single photon source at 1532 nm, available in our lab [START_REF] Alibart | High-performance guided-wave asynchronous heralded single-photon source[END_REF].

We see that the electro-optical control permits obtaining our necessary 50/50 coupling ratios for a voltage of around 30 V. This is higher than the expected low-voltage (< 10 V) performance for such a configuration but still shows that, despite fabrication errors, the coupling ratio can be tuned continuously. The reason for this higher voltage value is essentially due to the important thickness of the silica buffer, deposited inbetween the substrate and the metallic electrodes, used to reduce additional optical propagation losses due to metal loading. Moreover, note that slight misalignments between the electrodes and the couplers at the fabrication stage can also lead to increased control voltages. These results show that both obtained couplers fulfil the requirements, i.e., 50/50 ratios, necessary to implement on-chip quantum relay function.

Eventually, loss measurements at 1532 nm over the entire chip length have been performed and shown to be on the order of 9 dB between any couple of input to output fiber ports. These losses are in good agreement with the simulations we performed, taking into account input and output couplings (2×3 dB, for fiber-to-chip and conversely) and propagation losses over the entire chip (2.5 dB). Note that integrating segmented taper waveguides at all input/output ports could help maximizing the mode overlap between the fibers and the waveguides, and therefore reducing the coupling losses by more than 1 dB [START_REF] Castaldini | Soft-Proton-Exchange tapers for low insertion-loss LiNbO 3 devices[END_REF].

Proof-of-principle of the quantum relay function using the HOM effect

Photon coalescence (or two-photon interference) based on the HOM effect lies at the heart of quantum operations and is seen as the major first step towards achieving teleportation [START_REF] Hong | Measurement of subpicosecond time intervals between two photons by interference[END_REF][START_REF] Landry | Quantum teleportation over the Swisscom telecommunication network[END_REF]. Here, to demonstrate a proof of principle of a quantum relay function based on-chip BSM, we perform a HOM interference, or so-called HOM-dip, at the chip coupler C 2 between two independent photons, namely one external single photon and one photon out of the pair created on the chip.

To simulate the single photon coming from Alice's side, we use an external PPLN waveguide based source in the heralded single photon configuration, also producing degenerate paired photons at 1532 nm when pumped at 766 nm [START_REF] Aboussouan | High-visibility two-photon interference at a telecom wavelength using picosecond-regime separated sources[END_REF]. We select, within the created SPDC bandwidth, pairs of photons using a set of two fiber Bragg grating (FBG) filters. Such filters reflect the bandwidth of interest, which is collected through additional fiber optical circulators. These are set to select energy-matched pairs with wavelengths around 1530.0 nm (∆λ =200 pm) and 1534.0 nm (∆λ =800 pm) on both sides of degeneracy. This filtering solution based on standard telecom components provides a clever way to separate the photons deterministically at the output of the PPLN waveguide source and makes them available in separate single mode fibers. The shortest wavelength photons are directed, after polarization adjustment, to the input port 1 of the chip, while the complementary ones are not used for that particular measurement for obtaining reasonable overall coincidence rates. These photons are only used to monitor the stability of the experiment. Basically, such a single photon source features the same photon statistics as an attenuated laser.

As depicted in figure 5, we use a picosecond pump laser (Coherent MIRA 900-D) emitting 2.5 ps-duration, time-bandwidth limited (∆λ p = 250 pm) pulses, at the wavelength of λ p =766 nm, and at a repetition rate of 76 MHz. This laser is used to pump both the external PPLN waveguide source and the quantum relay chip to facilitate the synchronization procedure described in Sec. 2. The laser delivers mean power values of 1.5 and 7 mW to the single photon source and the on-chip PPLN section, respectively. The photon-pairs (b & c) out of the on-chip PPLN section are randomly separated at the first coupler C 1 . At the output of the chip, another set of filters, identical to the previous one, is used to post-select, on one hand, couples of photons b and a at 1530 nm through output ports A and B, and, on the other hand, the complementary photons c at 1534 nm through the port C of the chip.

+ + + + + + _ _ _ _ _ _ PPLN zone

Quantum relay chip

To observe the two-photon interference, or HOM-dip, at coupler C 2 , three-fold coincidences are recorded using three InGaAs-APD modules (idQuantique-201) placed at the output of the chip. Since the three detectors are not able to handle trigger rates above 1 MHz, they are triggered by an Si-APD placed in the path of an attenuated fraction of the pump beam (not represented in Figure 1) to obtain an average triple gate opening at 600 kHz, randomly selected from the 76 MHz laser repetition rate.

When considering two-photon interference requirements, indistinguishability in terms of energy is ensured by the filtering stages, while that associated with polarization states is ensured by the properties of the waveguide structures themselves, since they support TM modes only. The expected HOM-dip visibility is nevertheless limited by the time uncertainty of the two photons entering coupler C 2 , which reads [START_REF] Tapster | Quantum interference: experiments and applications[END_REF]:

V uncert max = 1 τuncert τc 2 + 1 , (1)
in which, considering our pulsed configuration, τ uncert and τ c represent the pulse duration of the pump laser and the interfering photons' coherence times, respectively. Note that τ uncert takes into account any broadening of the pump. Here, in the picosecond regime, the contribution of the dispersion over the chip length to the actual pulse duration is negligible. For this reason, the 1530 nm filters, at the joint outputs A and B, exhibit a bandwidth of 200 pm, to reach photon coherence times of 17.3 ps, corresponding to a maximal achievable visibility close to 100%. Note that the 1534 nm filters feature a 800 pm bandwidth, i.e., four times larger than the afore mentioned 200 pm bandwidth, to maximize the three-fold coincidence rate. Moreover, the visibility of the dip also strongly depends on the statistics of the two single photons entering both at one input of the coupler C 2 . The visibility of the HOM-dip is therefore given by:

V = P c max -P c min P c max , (2)
where P c max and P c min represent the probability of coincidence outside and inside the dip, respectively. For a low mean number of photons, these two probabilities are approximated by:

P c min = P 0,a P 2,b + P 2,a P 0,b (3)
and

P c max = P 1,a P 1,b + P 0,a P 2,b + P 2,a P 0,b , (4)
where P n,j represent the probability to have n photons in the coupler input arm j = a, b.

We can see that the maximal attainable visibility is limited by P c min , or in other words, by multiple pair events arising from one source (P 2,j ). The latter figure depends on the photon number distribution of the considered photon-pair generators.

In our experimental configuration, the paired photons are emitted by spontaneous parametric down-conversion. They are then filtered down to the time-bandwidth limit with respect to the pump pulse duration. The photon number distributions have been characterized for each source, and both feature, as expected, thermal photon-pair distributions [START_REF] Tapster | Photon statistics of pulsed parametric light[END_REF]. We define N a and N b as the average numbers of photon-pairs created per pump pulse out of Alice's and the chip generators, respectively. If we simply take into account two-fold coincidences between detectors D a and D b , a theoretical visibility of 33% can be reached when N a = N b , as described in [START_REF] De Riedmatten | Quantum interference with photon pairs created in spatially separated sources[END_REF]. To improve the visibility figure, three-fold coincidences have to be measured between the three detectors placed at the output of chip. Consequently, the on-chip generator distribution follows that of a single photon source exhibiting a thermal statistics in the heralded regime [START_REF] Tapster | Quantum interference: experiments and applications[END_REF][START_REF] Pittman | Violation of Bell's inequality with photons from independent sources[END_REF]. This permits reducing the probability P 0,b associated with no photon-pair events (see Eq. 3 and 4). Figure 6 presents the maximal achievable visibility obtained when solving Eq. 2 as a function of N a and N b in the three-fold coincidence regime. In this case, mean pump powers of 1.5 and 7 mW in front of Alice's and the chip generators, corresponding to N a = 0.05 and N b = 0.02, respectively, allow improving the theoretical visibility to 75%. Finally note that reaching 100% visibility is possible when P 0,a ≃ P 0,b ≃ 0, corresponding to the case where both photon sources are operated with thermal distributions and in the heralded regime [START_REF] De Riedmatten | Quantum interference with photon pairs created in spatially separated sources[END_REF].

Figure 7 represents the evolution of the effective three-fold coincidence rate, measured as a function of the path length difference between the two interfering photons.

The path length is adjusted using a retro-reflector (R) placed in front of the chip, as depicted in figure 5. When the two photons are made indistinguishable in terms of arrival times at the coupler C 2 , a reduction of 27%±10% in the raw three-fold coincidence rate is observed. After subtraction of the accidental events due to both dark-count/dark-count and photon/dark-count contributions, we reach a net visibility of 79%±25%, which perfectly matches the above theoretical description and what we expect from figure 6. Furthermore, a full width at half maximum of 6 mm is obtained, corresponding to a coherence time of about 20 ps, which is in good agreement with the photons' coherence time of 17 ps associated with the 200 pm bandwidth filters. Both the large error bars and the low raw visibility are essentially due to a nonoptimal detection scheme leading to a very low three-fold coincidence rate. These figures could be highly improved by the use of a new generation of InGaAs detector capable of being triggered at higher rates up to 100 MHz. Compared to our current detection scheme that allows exploiting less then 1% of the laser pulses, such modules would make it possible to attain a 2 order of magnitude improvement of the three-fold coincidence rate. This would enable the realization of the same experiment with a substantial reduction of both the error bars and the integration times. Eventually, this would allow taking in to account the heralding signal from Alice, permitting reaching the theoretical net visibility of 100%.

Conclusion & perspective

We have demonstrated that all the elements for implementing an integrated quantum relay circuit have been designed and merged onto a single chip. Each optical function has been tested separately, namely the photon-pair source and the photon routers. The on-chip source emits paired photons by SPDC within the telecom C-band, while the couplers show a 50/50 ratio when controlled using electro-optical means. Using such a chip, we also demonstrated a proof-of-principle experiment, based on the so-called HOM two-photon interference effect, which is seen as the major preliminary step towards achieving teleportation. We obtained in this quantum regime a HOM-dip at the second router of the chip featuring 79% net visibility using two independent single photons, one external and one out the on-chip created pairs. This result, together with the width of the dip, is in good agreement with the theoretical description associated with our experimental configuration. With our non ideal chip, presenting rather high overall losses, the achievable quantum communication distance could be possibly augmented by a factor of 1.4, whereas an optimized device could lead to a factor of 1.8. We believe that utilizing, for the first time, both nonlinear optical-optical and electro-optical effects provides a significant demonstration of the applicability of integrated optical technology on lithium niobate for quantum information treatment and applications. Current work now consists in improving the overall chip design to obtain much lower fiber-to-fiber losses regarding any input/output couple, which would permit realizing a true teleportation experiment. Future directions would lead to designing a wavelength demultiplexing module at C 1 location that would allows exploiting every created pairs in the nonlinear section. On the other hand, a suitable adaptation of the deposited electrodes on the routers would enable designing novel circuits, featuring reconfigurability capabilities, offering new perspectives in the field. On-chip and ondemand generation of various photon-number states dedicated to quantum logic gates operation could be envisioned [START_REF] Tanzilli | On the genesis and evolution of integrated quantum optics[END_REF].

Figure 1 .

 1 Figure1. Schematics of the quantum relay chip with its two electro-optically controllable couplers C 1 et C 2 . D a and D b are two detectors responsible for the Bell state measurement (BSM). At the end of the quantum channel, Bob's detector is triggered by the AND-gate (&) placed after these two detectors. The chip operation fits perfectly with the point-to-point telecommunication approach for which a classical heralding signal propagates through the channel along with the qubit.

Figure 2 .

 2 Figure2. Simulation of the normalized key rates as a function of the quantum communication distances for various one-way link configurations. Standard figures, used here, are fibre losses of ∼0.2 dB/km, detectors' dark-count levels of ∼10 -6 /ns associated with 10% detection efficiencies (obtainable from commercially available InGaAs avalanche photodiode modules), and a quantum teleportation fidelity of 0.8 (as obtained in[START_REF] De Riedmatten | Teleportation in the quantum relay configuration[END_REF]). This simulation proposes a comparison between a direct quantum communication link without any relay (red), and a standard quantum relay protocol based on the teleportation scheme (violet), together with its "folded-version" implemented using the actual relay chip (blue). In addition, the performance of a lossless relay chip is provided in order to show the potential improvement related to better technological fabrication of the chip (green). Absolute key rates can be obtained by multiplying the numbers on the y-axis by the pump laser repetition rate.

Figure 3

 3 Figure 3. SPDC from the nonlinear waveguide zone. Outputs A and B correspond to the top outputs where the BSM is to be performed while the C output is the bottom output for the teleported qubit. Faithful characterization of the nonlinear interaction is provided by the sum of these three outputs. The difference between the three outputs is due to unwanted broadband wavelength sensitivity of the couplers. This behavior is explained by irregularities in the fabrication process leading to asymetric waveguides. Moreover, usual Cerenckov effect is observed on the left side of the fluorescence peaks[START_REF] Ito | Cerenkov-type second harmonic generation from a LiNbO 3 waveguide with a periodic domain grating[END_REF].

Figure 4 .

 4 Figure 4. Characterization of the coupling ratios obtained with couplers C 1 and C 2 in both narrowband classical light (lines) and broadband single photon light (crosses).The difference in coupling performance between C 1 and C 2 for voltages < 40 V is simply due to irregularities in the fabrication process.

R

  FBG+circulator : [1530 nm, 200 pm] FBG+circulator : [1534 nm, 800 pm]

Figure 5 .

 5 Figure 5. Coalescence experiment based on one external PPLN waveguide based source and the quantum relay chip pumped by a single picoseconds laser. A silicon APD (Si-APD, not represented) is employed to trigger the four InGaAs-APDs as a laser clock random divider. D a , D b , and D c are used to record three-fold coincidences, while the non labelled detector is used to monitor the stability of the experiment. I: isolator; R: retro-reflector; C: circulator; &: AND-gate. The InGaAs-APDs feature 10% quantum efficiency and a dark-count probability of about 10 -5 ns -1 .

Figure 6 .

 6 Figure 6. Maximal visibility as function of the average number of photons N b generated in the chip and the average photon number N a dispatched by Alice's source.Regarding the experimental setup, mean pump powers of 1.5 and 7 mW in front of Alice's source and of the on-chip PPLN section lead to N a = 0.05 and N b = 0.02, respectively. The latter values allow reaching a theoretical visibility of 75% (where the white dashed lines cross each other) while maintaining a reasonable coincidence rate.

Figure 7 .

 7 Figure 7. Three-fold coincidence rate as a function of the path length difference between the two interfering photons. The Gaussian fit of the interference pattern shows a raw (net) visibility of 27%±10% (79%±25%).

Acknowledgement

The authors would like to thank G. Bertocchi and S. Tascu for their help in the chip manufacturing, P. Baldi for discussions, M. Al Khalfioui for the micro-soldering of the electrodes, and G. Sauder for his support in software development. The authors also acknowledge the CNRS, the University of Nice -Sophia Antipolis, the Agence Nationale de la Recherche (ANR) for the "e-QUANET" project (grant agreement ANR-09-BLAN-0333-01), the European ICT-2009.8.0 FET Open program for the"QUANTIP" project (grant agreement 244026), the Conseil Regional PACA, and the iXCore Science foundation, for financial support.