Teodora Szasz

Adrian Basarab

Denis Kouamé

ℓ 1 -norm regularized beamforming in ultrasound imaging

Keywords: Ultrasound imaging, beamforming, inverse problems, beamspace processing, Laplacian priors, Basis Pursuit

, organized during the IEEE International Ultrasonics Symposium 2016 in Tours (France). Herein, we address beamforming in ultrasound imaging, by formulating it, for each image depth, as an inverse problem solved using Laplacian prior through Basis Pursuit (BP). This approach was evaluated for the four different categories proposed for the competition, using 1, 11, 75 plane waves, and for the best ultrasound image quality using the lowest number of steered plane waves. The proposed method results in considerable improvement in spatial resolution and contrast compared with DAS method proposed in the challenge.

I. INTRODUCTION

The proposed method (see [START_REF] Szasz | Beamforming through regularized inverse problems in ultrasound medical imaging[END_REF] and [START_REF] Szasz | Beamforming through regularized inverse problems in ultrasound medical imaging (to appear)[END_REF]), presents an ultrasound (US) beamforming (BF) technique using a linear inverse problem relating the raw data to the RF signals to be recovered. Numerical optimization routines have been employed to invert the resulting linear model based on standard regularization terms. ℓ 1 -norm has been employed to generate the results presented through the challenge on plane wave imaging in medical ultrasound [START_REF]Beamforming grid | Plane-wave Imaging Challenge in Medical Ultra-Sound[END_REF], organized during the IEEE International Ultrasonics Symposium 2016 in Tours (France). Our method was tested for the four categories of the challenge and the results will be presented in Section III.

Instead of using fixed (DAS) or adaptive (MV) apodization functions, we have recently proposed in [START_REF] Szasz | Beamforming through regularized inverse problems in ultrasound medical imaging (to appear)[END_REF] a new BF model for medical US imaging that takes into account the positions of the elements and reflectors in order to relate the desired signals to the raw data. This results in an inverse problem that we solve using Laplacian or Gaussian priors through Basis Pursuit (BP), respectively Least Squares methods. We were thus able to obtain two complementary results, one that produced sparse images and one generating smoother results [START_REF] Szasz | Beamforming through regularized inverse problems in ultrasound medical imaging (to appear)[END_REF]. This formulation also offered the possibility to highly reduce the number of US emissions during the scanning procedure, by integrating it with a beamspace processing technique [START_REF] Fuchs | Linear programming in spectral estimation. Application to array processing[END_REF]. Note that the same model was also applied in [START_REF] Szasz | Elastic-net based beamforming in medical ultrasound imaging[END_REF] and [START_REF] Szasz | Beamforming of ultrasound images modelled as stable random variables (regular paper)[END_REF], but with different regularization functions.

This work uses the method presented in [START_REF] Szasz | Beamforming through regularized inverse problems in ultrasound medical imaging (to appear)[END_REF]. The direct model presented in Section II is inverted through Basis Pursuit (BP) using ℓ 1 -norm regularization related to the Laplacian This work has been supported by the CIMI Labex, Toulouse, France, under grant ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02. distributed nature of the images. This approach gives the best results in terms of the image quality metrics used in the challenge and visual perception of the images.

II. PROPOSED ℓ 1 -NORM REGULARIZED BEAMFORMING

A. Direct model formulation

Considering an M -element US probe that is sequentially transmitting P US plane-wave beams, let the recorded signals after time-of-flight delay compensation be of N time samples length. For the p th emission and a given depth n, the model relating the received signal (raw data), y p ∈ C M ×1 to the desired signal x can be written as follows:

y p = (A H p A T )x + g p , (1)
where A p ∈ C M ×M and A T ∈ C M ×K are standard steering matrices relating the US probe element positions to the K lateral positions on the scanline. We denoted by x ∈ C K×1 the signal at depth n to be beamformed with the proposed method, by g p the additive white Gaussian noise affecting the raw data, and with (•) H the conjugate transpose.

To reduce the dimensionality and increase the quality of the raw data, we apply beamspace processing, a common tool in array processing used to reduce the computational complexity and to improve the signal-to-noise ratio (SNR) [START_REF] Malioutov | A sparse signal reconstruction perspective for source localization with sensor arrays[END_REF]. In our case, we use the DAS BF result instead of the raw data, for transforming our data into beamspace domain. Thus, we can reformulate (1), as:

y = Φx + g, (2)
where

Φ = A H A T , Φ ∈ C M ×K
, y is the DAS profile at depth n, x the signal of interest at depth n and g the Gaussian noise. Note that the resulting problem is ill-posed, thus requiring regularization in order to obtain a valid solution.

B. Model inversion

One solution, presented here, is to solve the BF problem in (2) by solving the following minimization problem:

x = argmin x ( y -Φx 2 2 + λ x 1 ), (3)
where λ is the regularization parameter balancing the tradeoff between the fidelity to the data and the regularization term. Herein, we used the well-known YALL1 to solve (3) [START_REF] Zhang | User-guide for yall1: Your algorithms for l1 optimization[END_REF], a software package dedicated to solve BP problems such as (3).

III. RESULTS AND DISCUSSION

This section presents the results obtained by our method on the datasets available through the challenge platform. Note that λ parameter was manually tuned to give the best numerical results.

A. Results using 1 plane-wave

Fig. 1 presents the results obtained with our method when 1 plane-wave was used.

B. Results using the lowest number of steered plane-waves that results to the best image quality

Hereafter, we present the results using three plane-waves that offer the best image quality metrics using the lowest number of steered plane-waves (see Fig. 2).

Table II presents the image quality metrics computed for Fig. 2.

C. Results using 11 plane-waves

Fig. 3 presents the results obtained with our method when 11 plane-waves were used.

Table III presents the image quality metrics computed for Fig. 3.

D. Results using 75 plane-waves

Fig. 4 presents the results obtained with our method when 75 plane-waves were used.

Table IV presents the image quality metrics computed for Fig. 4.

In Fig. 1(d), Fig. 2(d), Fig. 3(d) and Fig. 4(d), the values of λ were manually chosen to provide the best values of the axial and lateral resolution. However, we can observe that the speckle and the cyst-like structure are eliminated. Note that the proposed method can also maintain the speckle and the cyst-like structure, by lowering the value of λ. An example, when using 1 plane-wave, is presented in Fig. 5. In Fig. 5(b) are conserved both the speckle, the cyst-like structure, while in Fig. 5(c), the speckle is eliminated. The values of λ and image quality metrics for each case can be found in Table V.

IV. CONCLUSION

In this paper, we modeled US beamforming as an inverse problem regularized using ℓ 1 -norm minimization. This formulation offers the possibility to integrate in the BF process the advantages of both sparse and smooth solutions. We have shown that our approach applied to the datasets available through the challenge platform provides solutions with improved axial and lateral resolution, and contrast compared to DAS.

Fig. 1 .

 1 Fig. 1. Comparison of the proposed BF method ((b), (d), (f), (h)) with DAS BF ((a), (c), (e), (g)) for all challenge datasets, using 1 plane-wave.

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Comparison of the proposed BF method ((b), (d), (f), (h)) with DAS BF ((a), (c), (e), (g)) for all challenge datasets, using 3 plane-waves.

Fig. 4 (

 4 a): 0.40 0.56 Fig. 4(e): 15.36 Proposed -sim. Fig. 4(b): 0.11 0.15 Fig. 4(f): 23.34 DAS -exp. Fig. 4(c): 0.56 0.56 Fig. 4(g): 11.80 Proposed -exp. Fig. 4(d): 0.09 0.05 Fig. 4(h): 11.80

Fig. 5 .

 5 Fig. 5. The result of the proposed BF method for different value of λ, using 1 plane-wave. (a) DAS BF, (b),(c), (d), (e) proposed method with λ = 10, λ = 50, respectively λ = 100.

TABLE IV MEAN

 IV RESOLUTION SCORES (AXIAL & LATERAL) AND CONTRAST SCORES (DB) IN FIG. 4

	BF Method	Mean resolution (ax. & lat.)	Mean contrast (dB)
	DAS -sim.


Ghada Jaber
email: gjaber@irit.fr

Rahim Kacimi
email: kacimi@irit.fr

Zoubir Mammeri
email: mammeri@irit.fr

Exploiting Redundancy for Energy-Efficiency in Wireless Sensor Networks

Keywords: Wireless sensor networks, redundancy, fault tolerance, energy efficiency

Wireless Sensor Networks (WSNs) are used today in many applications that differ in their objectives and specific constraints. The common challenge in designing WSN applications comes from the specific constraints of sensors because of their limited physical resources such as weak computational capability, small memory capacity, and especially limited battery. In this paper, we consider sensor redundancy in WSN and we conduct an experimental study to better highlight the importance of its exploitation. We also implement OER 'Optimization of Energy based on Redundancy', a protocol that exploits redundancy in order to save energy. Moreover, we extend OER by a fault tolerance mechanism. Through extensive simulations, we show how OER combined with FTMOer outperforms traditional routing protocols that do not exploit redundancy.

I. Introduction

Wireless sensor networks (WSNs) are often characterized by a dense deployment in environments limited in terms of resources. Indeed, the limits are due to processing capability, storage, and especially energy because they are usually powered by batteries [START_REF] Rani | Multi-hop Routing in Wireless Sensor Networks: An Overview, Taxonomy, and Research Challenges[END_REF]. Recharging the batteries in a wireless sensor network is sometimes unfeasible mainly due to the location of the nodes. It is therefore recognized that the energetic limitation is an unavoidable issue in the design of wireless sensor networks. In fact, energy consumption plays an important role in the network lifetime, and it has become the major performance criterion for this type of networks. To increase the network lifetime, we should make compromise between different tasks at the node as well as in the network. Several research studies have appeared with a goal of optimizing the energy consumption of nodes through the use of conservation techniques to improve network performance and maximize its lifespan. The random deployment of networks can induce high spatial redundancy between nodes. Such a redundancy is a feature that is both cost effective and penalizing. Indeed, it can be used to improve detection reliability or accuracy of the data collected. But it generates greater data transfer and involves an additional traffic load.

In this paper, we are interested in redundancy in wireless sensor networks. Consequently, we implemented OER [START_REF] Diane | Energy Optimization in Redundant WSNs under Deterministic and Probabilistic Sensing Models (regular paper)[END_REF] in NS2 to show the benefits of exploiting the redundancy in terms of energy consumption. Besides, we extended it by a fault tolerance mechanism (FTMOer). Indeed, FTMOer finds a solution to notify the event even if is not detected by the representative node.

The reminder of this paper is organized as follows: In the next section, we discuss previous related work. The principle of redundancy, its types and its usefulness are described in Section III. Experimental study is explained in Section IV. Section V gives an idea about the protocol that we studied and implemented and explains our faulttolerant mechanism. Simulation results are presented in Section VI. Section VII summarizes the paper and concludes the paper.

II. Related Work

In [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF], Heinzelman et. al proposed a distributed clustering algorithm called LEACH for routing in homogeneous sensor networks. In LEACH, nodes self-configure into groups. Each group is controlled by an elected clusterhead. The cluster-head selection is based on the energy level of each node. In fact, it is chosen randomly and its role is assigned to different nodes to ensure fair energy consumption because the cluster-head consumes a lot of energy. The cluster-heads aggregate the data captured by other nodes in the cluster and send an aggregated packet to the base station. LEACH has two phases set-up and steady state. During the set-up phase, the cluster-heads are elected and groups are formed. During the steady state phase, the data is sent to the base station. However, although LEACH allows energy saving, therefore increasing the lifetime of the network, it has certain limitations. It is not suitable for large networks and it selects randomly the cluster-head which causes a concentrated distribution point in one place that generates a lot of isolated nodes. In addition, data aggregation might increase delay.

MR-LEACH [START_REF] Diane | Energy Optimization based on the Redundancy in WSNs (regular paper)[END_REF] uses a clustering technique based on the geographical proximity of nodes. This technique allows the grouping of nodes having the same measurement so that only representative nodes send their data. MR-LEACH is based on a LEACH-like architecture. Nodes are deployed randomly and densely. They observe the same physical phenomenon, generate a periodic monitoring traffic and send it to the base station via the cluster-head. MR-LEACH also has two phases. During the first phase of observation, groups are formed and every cluster-head collects readings from nodes. After that, the cluster-head analyzes the collected measurements and according to the geographical proximity of the nodes, it determines the groups of redundant nodes. After grouping, a single node sends its reading and the other nodes stop their transmission.

In [START_REF] Bahrami | DACA: data-aware clustering and aggregation in query-driven wireless sensor networks[END_REF], Bahrami et. al proposed DACA, a clustering approach that uses the correlation of data to form groups led by queries. Indeed, DACA selects the cluster-head nodes forming a request with three parameters (residual energy, the data value and the number of neighbors of each node) which reduces the number of groups, the number of transmissions and energy. DACA also operates a fusion method groups to prevent the formation of a single node which prolongs the network lifetime.

DDFC [START_REF] Gielow | Data similarity aware dynamic node clustering in wireless sensor networks[END_REF] has been developed to create and maintain a logical grouping of nodes with similar spatial values. Each node of a group must keep its aggregated data in its group to know when that group should be split or merged with another group. For DDFC, a group may have more than one cluster-head. DDFC defines three agents that perform its functions. Firefly agent allows synchronization of aggregated data and maintenance of groups. Indexing agent that assigns scores to each of the network nodes and the node with a maximum score is selected as the cluster-head. And adaptive agent adapts dynamically the interval between each frame, which provides stability. High density may cause instability in the network and the use of adaptive agent solves this problem.

III. Redundancy in WSNs

Most works offer improvements in terms of energy consumption without taking into account the redundancy measure that is also a source of unnecessary energy consumption. Redundancy is an inherent characteristic of WSNs that must be carefully considered to improve major aspects of their operation. Almost all sensor networks are deployed with a certain degree of redundancy. If it is not used in an intelligent way, redundancy will cause a waste of energy due to redundant transmissions and reception operations. There are several explanations in the literature that find that eliminating any redundancy helps to save a lot of energy and combining them is expected to save more. Sensor networks are characterized by a large number of nodes. So redundancy measure may result from densely deployed nodes. Several nodes can detect the same event and therefore the same measured value. It is hence necessary to consider mechanisms for the management of possible measurement redundancies. The challenge is the inclusion of redundant measurement in sensor networks for better improvement in energy consumption.

A. Types of redundancy

Redundancy is an inherent characteristic of WSNs. There are two types of redundancy: Spatial redundancy related to measurements detected by several sensors at the same time and Temporal redundancy related to identical measurements detected over time.

1) Spatial redundancy: Spatial redundancy is the possibility to obtain information for a specific location from different sources [START_REF] Curiac | Redundancy and its applications in wireless sensor networks: a survey[END_REF]. It is based on the geographical location of the sensor nodes and involves the replication of resources in the network coverage area. Spatial redundancy is used to improve the reliability of the measured data and to increase the safety level. Physical redundancy [START_REF] Shim | Method of detecting and isolating fault in redundant sensors, and method of accommodating fault in redundant sensors using the same[END_REF] is the most used technique to ensure the reliability of a system. It can measure a variable in a specific location using more than a sensor. So it is based on the deployment of multiple nodes that cover a specific area. This type of redundancy uses the aggregation of sensor measurements with similar data. When nodes are close to each other and redundancy exists in the detected data, the source nodes generate a large amount of traffic on the wireless channel that causes not only a waste of bandwidth but also a loss of battery power.

2) Temporal redundancy: Temporal redundancy may be defined as the achievement of a specific action more than once in time followed by a checking result to increase reliability [START_REF] Curiac | Redundancy and its applications in wireless sensor networks: a survey[END_REF]. It is used to improve the accuracy of measurements by the sensor nodes to withstand transient faults during detection and communication. There are cases where the use of temporal redundancy is tricky to be applied [START_REF] Curiac | Redundancy and its applications in wireless sensor networks: a survey[END_REF]. One of these situations is the use of sensors in the detection dynamic environments where the parameters are changing rapidly in time. Temporal redundancy can be attached either to the detection or communication or both at the same time.

• Temporal sensing redundancy: In an ideal scenario where the sensing is perfect, a high level of confidence in data measurement can be obtained using a single sensor [START_REF] Curiac | Redundancy and its applications in wireless sensor networks: a survey[END_REF]. In the real world detection devices sometimes have inaccurate measurements thus reading from a single sensor would not give reliable measurements. To improve the reliability of the whole system, we should increase redundancy using multiple reports from the same sensors.

• Temporal communication redundancy: Temporal communication redundancy is defined as sending the same package of data more than once skewed in time [START_REF] Curiac | Redundancy and its applications in wireless sensor networks: a survey[END_REF].

B. Usefulness of redundancy

Redundancy usefulness is summarized hereafter:

• Energy saving is one of the most important concerns in wireless sensor networks where nodes have limited battery power. Energy saving strategies exploit the spatial redundancy by defining subsets of active nodes in different time periods to allow nodes to save energy when they are in the idle mode. Thus they put as many redundant nodes as possible in sleep mode and they only use a few of the energy spent in active mode.

• The topology control is a method to save energy based on spatial redundancy which reduces the number of nodes involved in routing and forwards packets created by the other nodes without reducing network connectivity and coverage.

• Redundancy provides robust and faulty tolerance information when sensor nodes are faults or even malicious. Since the sensors are often deployed in harsh environments, erroneous damaged sensor readings may impact the accuracy of the readings of the sensor network. Hence several observation nodes in the same place and at the same time might ensure better monitoring of quality.

• As sensors may be deployed in harsh environments WSNs can be seriously affected by any type of sensor failure or malicious attacks. The security objectives in sensor networks require the development of specific approaches, most of them exploit redundancy.

Almost all sensor networks are deployed with a certain degree of redundancy and the redundancy is used only for robustness purposes.

IV. Experimental Study

In order to highlight how important is the exploitation of spatio-temporal redundancy in WSNs, we carry out an experimental study. The amount of information collected by sensors is very important. Thus, exploiting redundancy to reduce the number of transmissions with the same sensor readings leads to save energy and to maximize the network lifetime.

A. Experimental Set-up

Experiments were performed using Tmote Sky [START_REF]TmoteSkydatasheet[END_REF] devices. The platform produced by moteiv, is an ultra low power IEEE 802.15.4. The mote uses a Texas instrument MSP430 micro-controller running at 8MHz and 48k of flash memory. We deployed a network with 4 nodes: a base station and 3 nodes integrating humidity, light and temperature sensors. Each device operates on 2 AA batteries. The experiments were performed on the campus of the university between 8 am and 9 am in a cloudy day. A picture of the site is shown in Fig. 1. 3 sensors were placed on trees spaced with 35 feet. To collect the measurements, the base station was connected to a laptop. The network topology is a star one.

B. Experimental Results

As we mentioned before, the sensors measured temperature and humidity during more than one hour. The sensor readings are shown in Fig. 2.

During one hour, we collected more than 9000 samples per node. As depicted in Fig. 2., the sensors have almost the same readings. Consequently, they send redundant values. At the beginning, sensors present different measures due to the fact that they were in a box and that they take time (around 10 minutes) to measure the right temperature or humidity. In order to exploit this redundancy, we implement in the next section a protocol based on spatial redundancy.

V. Energy Optimization in Redundant WSNs

To exploit spatial redundancy in WSNs, we implement OER [START_REF] Diane | Energy Optimization in Redundant WSNs under Deterministic and Probabilistic Sensing Models (regular paper)[END_REF] an energy optimization protocol in redundant WSNs under deterministic and probabilistic sensing models to take benefit from measurement redundancy to optimize the energy consumption. We also improve it with FTMOer, a fault-tolerance mechanism.

A. Principle of OER

OER 'Optimization of Energy based on Redundancy' exploits redundancy in order to improve the network lifetime. It uses a clustering technique that allows the grouping of nodes detecting the same events like LEACH. Based on the probabilistic model of Elfes [START_REF] Elfes | Occupancy grids: A stochastic spatial representation for active robot perception[END_REF], it combines its geographic position and its probability to detect the same event in order to reduce the number of transmissions. In the Elfes model, the probability that a sensor detects an event over a distance x is expressed as follows:

P det(x) =      1 if x ≤ R exp -λ(x-R) β if R < x ≤ R max 0 otherwise (1)
The protocol has two main phases illustrated in Fig. 3. In the first phase, it determines and groups redundant nodes. During the second phase, it checks whether the resulting partitioning is the best to minimize an objective function which optimizes the energy. The process is repeated until an optimal partitioning is found. After the initialization phase, OER enters in the phase of detection and transmission. One representative node is active in the same redundant group. The representative nodes detect events and send their data to the sink. For the network partitioning, OER starts by choosing a random node that serves as the first event center area. Depending on the probability, it identifies redundant nodes in that region. After having formed the first group, the center moves to another node and other groups are formed. This process is repeated until each node becomes a group member. According to the Elfes detection model, a node detects an event held at a distance less than or equal to R.

OER uses a tabou search for partitioning, which minimizes the best overall energy consumption of the network. This research uses a partitioning algorithm to group the redundant nodes and evaluates the cost of partitioning. At the end of the search the optimal solution is obtained.

B. Fault Tolerance

Sensor data are sometimes incomplete and sometimes redundant. Indeed, the sensors can either do not detect the information or do not detect the right information. The errors in data can arise at different levels of the system and they are directly related to the data acquisition and processing. • Sensors: Sensor lifetime, its calibration, the degradation of the device or the installation errors are aspects that may impact the quality of data during the measurement. The resources of the sensor also represent a source of errors. The limitations of computing and storage capacity reduce the amount of processing performed within the sensors. This may cause a loss of information, miscalculation, the unavailability of the sensor or the sending of data to the central server without direct request.

• Environmental factors: Sensor networks are often deployed in hostile areas, therefore the operating conditions of a sensor or a sensor network can be affected by the environmental conditions. These factors have a significant impact on the performance of the sensors and therefore on the measures they realize.

• Measurement methods: Usually sensors measure only one element at a time because of its size, its energy and its processing capacity are limited. These aspects encourage the use of methods of measurement that economize in term of energy despite the reliability of precision and accuracy of the data.

• Communication: Once the data is measured, the sensors often use wireless communications to communicate the acquired data to a central node or a server. However, this communication may be damaged due to bad environmental conditions, interference, or congestion. Moreover, bad communication can lead to erroneous or missing data.

Since OER present some failures in detecting data, we thought about improving it by implementing a fault tolerance mechanism.

a) FTMOer 'Fault Tolerance Mechanism for OER':

An event is detected by one or m nodes of the same group. We have two instances of detection, deterministic and probabilistic. Deterministic detection where all nodes detect the event. And probabilistic detection where only k nodes (k<m) detect. And it is in the second case that we implement a fault tolerance mechanism. During a super frame, only one node sends its data. This representative node operates on 3 modes: -it detects and sends the data.

-it doesn't detect (eg. detection threshold not reached) and the other nodes won't react because it is not their turn. So the event is lost.

-it is faulty (eg. depleted battery) so it can not detect and the event is not notified. node.count ← 0; 4 : for each node ∈ Gp do //If the node has a probability < 1, then associate a listening node with a probability = 1.

:

if (node.P det = 1) then

:

for each node ′ ∈ Gp do 7 :

if ( node ′ .P det = 1 ) then 8 :

if (node ′ .count ≤ T hreshold) then

:

List N ode ← node ′ ; 10 :

node ′ .count++;
The idea proposed here is to improve fault tolerance of the OER protocol for the formation of redundant groups under the assumption of probabilistic detection model. After the formation of the groups, we know which node is to transmit the event in the super frame. So, we propose to associate a listening node to the representative node. Suppose that we have a representative node that sends its data, we begin by checking its detection probability P det .

If P det = 1, we are sure that the node detects the event and it will send its measurements to the cluster-head. Otherwise, if there is a risk that the node has not detected (when we relax the probability), we associate another node from the same group having a probability of detection equal to 1. For example when P det = 0.95, there is a risk of 5% that the node didn't detect. The associated node sends its data instead of the representative node. So at the beginning of each transmission, the associated nodes listen to see if they are working or not. This affects energy saving but we are sure that all the events occurred are notified to the sink. FTMOer listening node association is detailed in algorithm1.

VI. Evaluation

We evaluate the performance of OER and show the importance of the fault tolerance mechanism that we proposed to indicate that OER combined with FTMOer can save more energy. Our purpose is not to improve especially LEACH but is to highlight that our protocol is better than a protocol that does not exploit redundancy.

A. Simulation Set-up

For the implementation of OER, we chose to start with the code of LEACH and to make changes to suit OER requirements. For the clustering algorithm, we implement it in C++. The code is used to find a network partitioning and then propose a scheduling of transmissions that we inject in a NS2 simulation model.

We consider a wireless sensor network deployed on a surface of 100 × 100 m 2 . The number of nodes varies from 50 to 200. The nodes have the same radius detection. For the parameters of detection range we set the values of analog PIR [START_REF]PIRsensor[END_REF].

B. Evaluation metrics

We compare our scheme to LEACH. For this we performed simulations with the same parameters and metrics for both approaches. We are interested primarily in energy consumption since it is a key criterion for determining the network lifetime. The performance metrics that we chose are:

• Energy consumption: we measure the energy consumed by the whole network.

• Number of packets sent: to evaluate the fault tolerance mechanism, we measure the number of packets sent with and without FTMOer.

C. Simulation Results

We compare the energy consumption of the network for OER and LEACH under different network sizes. For LEACH, all nodes send their data periodically while for OER, only the representatives of the groups send their values to the cluster-head. As depicted in Fig. 4., OER consumes less energy than LEACH. We observe that during a super frame for 150 nodes, LEACH consumed 26.99J while OER consumed 12.59J. So it realized a gain of 14.4J. Thus, OER enables energy saving. Indeed, when the network density increases, the measurement redundancy increases and less nodes transmit data. With a high density, the size of the groups increases. Therefore the number of transmissions per node decreases over time and the network lifetime increases. Fig. 4. also illustrates a gap in terms of energy consumption between a deterministic detection model a the probabilistic detection model. Besides, we can note that energy consumption decreases when we relax probability because the size of each group increases. As shown in Fig. 5, with OER, the nodes send less packets than with LEACH because in LEACH all nodes send their data in turn. While, in OER only representative nodes per group send their data. Thus when the number of nodes increases, the number of nodes per group increases and less nodes send packets. We note also that when we relax the probability, the number of packet decreases. Because for example for a probability equal to 0.95, we have a risk of 5% that a node didn't detect the event. So, due to the probability of the Elfes model, larger groups with more nodes are formed and the number of packets sent decreases. a) Impact of including the mechanism of fault tolerance: Here we take the example of a node with a probability 0.95. We begin by checking if the node really detected the event or not. If there is a risk that it didn't detect, another node from the same group which detected the information will send instead of the representative node during this round. Fig. 6. presents the energy consumption for OER with and without the fault tolerance mechanism when we relax the probability to 0.95. For the energy consumption, we note that after including the fault tolerance mechanism, the nodes consume slightly more energy. This is due to We notice that after including the fault tolerance mechanism, more data were sent. In consequence, we lost slightly 10% in terms of energy but we win in term of reliability. For example for 100 nodes, during 50s, more than 9% of data were sent for a detection probability of 0.95. So the mechanism has ensured the transmission of data even detected at 95%.

VII. Conclusion

In this paper, we describe redundancy and its usefulness. By the experimental tests, we highlight the presence of redundancy in WSNs. We also present OER, a redundancy based routing protocol that minimizes global energy usage by exploiting redundancy and geographical localization. We demonstrate that OER with FTMOer outperforms LEACH in term of energy consumption.

As a future research work, we plan to implement OER and FTMOer on tmoteSky nodes for a biodiversity monitoring application at Toulouse university campus. Besides, we will address the problem of the temporal redundancy. Indeed, we believe that there is room for enhancement in terms of energy if the freshness of the sensor readings and their lifetime are considered.

Fig. 1 Fig. 2 :

 12 Fig. 1: Experimental setup

Fig. 3 :

 3 Fig. 3: Phases of OER

Algorithm 1 :

 1 Association of listening nodes input : P det : probability of detection Gp: group of nodes α: number of nodes with P det = 1 β: group size output : List N ode: associated listening nodes 1 : T hreshold ← ⌈ β-α α ⌉; 2 : for each node ∈ Gp do 3 :

Fig. 4 :

 4 Fig. 4: Energy Consumption (J)

Fig. 5 :

 5 Fig. 5: Number of packets sent

Fig. 6 :Fig. 7 :

 67 Fig. 6: Energy Consumption (J)

Acknowledgment

This work was supported by the neOCampus research grant [3].


Alexis Aubry
email: alexis.aubry@univ-lorraine.fr

Hind Bril

André Thomas
email: andre.thomas@univ-lorraine.fr

Mireille Jacomino
email: mireille.jacomino@grenoble-inp.fr

Product Driven Systems facing unexpected perturbations: how Operational Research models and approaches can be useful?

Keywords: Production Planning and Control, Product Driven Systems, Uncertainty, Robustness, Flexibility, Operational Research

Production planning and control and more generally taking a decision in the context of production systems often consider that input information are known, static and predictable. However, uncertainties on data and perturbations are recorded in the genetic of every production system. For instance, it is impossible to know exactly the level of the demand for a product, the availability of resources, etc. Dealing with this issue asks the question of the ability to take robust decisions against uncertainty (off-line) or the ability to be flexible (on-line). This paper proposes to analyze how Product Driven Systems -as reactive systems against unpredicted perturbations -can be part of operational research solution process against perturbations. Moreover, an overview of models and approaches for dealing with uncertainty in Operational Research is given and a first proposition is made for applying these elements into PDS as decision-makingagainst-perturbations engines.

Introduction

Since some years, Product Driven Systems (PDS) are becoming a credible way to control product flows on shop-floors and in supply chains thanks to Auto-ID and especially RFID technologies. PDS are defined as systems in which products are able to be active and are at the core of an enterprise architecture which integrates every actor in the company, from the central systems to the processes, products and also operators, into the same ambient information system [START_REF] Pannequin | Another Interpretation of Stigmergy for Product-Driven Systems Architecture[END_REF]. The Intelligent Product (IP) paradigm [START_REF] Wong | The Intelligent Product Driven Supply Chain[END_REF][START_REF] Morel | Manufacturing Enterprise Control and Management System Engineering: paradigms and open issues[END_REF] was a step further to the use of RFID-tagged products, and not only for identification objectives. IP has demonstrated the efficiency of speeding up and making more visible information flows in logistic operations [START_REF] Klein | Opportunities to reconsider decision making processes due to Auto-ID[END_REF]. Following, a new interpretation of the stigmergy concept was put forward in [START_REF] Pannequin | Another Interpretation of Stigmergy for Product-Driven Systems Architecture[END_REF], where the cooperation between production actors (products, resources and all used manufacturing appliances) was achieved thanks to attributes called informational pheromones and carried by RFID-tagged products. Products collaboration is a concept on which many researchers [START_REF] Yoshimura | System Design Optimization for Product Manufacturing[END_REF][START_REF] Wenyan | Collaborative Product Innovation Network: Status Review, Framework, and Technology Solutions[END_REF] have focused their works.

Thus, this Product Driven Systems (PDS) paradigm has been established and its relevance has been highlighted precisely to deal with new product flows control approaches, especially to react to unpredicted events occurring on the shop-floors and in the supply chains. Indeed, anybody with production or logistic experience knows that, often, a predicted plan or schedule cannot be exactly executed! Events occurring on the shop-floor, or in the supply chain lead to uncertainties in daily activities inducing needs for adjustments in plans. That is one of the main reasons that justify PDS.

On the other hand, in the previous decades, a lot of research teams have proposed a huge of models, built on exact approaches or on heuristics, useful to schedule or reschedule production and logistic activities. In the design or management of these various types of control systems, and particularly for production and logistic ones, a number of variables have to be frequently determined so as to optimize a given performance criterion. Optimization models are used to search for the best possible values of a vector of variables (e.g. number of resources, production planning in a manufacturing system and so on). In this context, operational research approaches are privileged approaches when dealing with optimization in production systems. However, in most dedicated works, the optimization model is built from data that characterize given and fixed environmental conditions (e.g., assumed nominal processing times, fixed transportation delays, exact amount of demand etc). However, in practice, perturbations can modify these values, and thus change the data that were initially assumed to be known and static. The expected values (also called reference instance in [START_REF] Espinouse | On the Robustness of Multi-Purpose Machines Workshop Configuration[END_REF] or base environmental scenario in [START_REF] Pierreval | Robust Simulation with a Base Environmental Scenario[END_REF]) are supposed to model the environment that the domain expert think relevant to characterize the actual operating conditions of the studied system. In practice, good or even optimal performances, achieved by the system in given conditions can be drastically deteriorated if these conditions change. For instance, a delivery delay, evaluated through an optimization model, can be considered as acceptable, with regards to the customer demand, if breakdowns occur at a given rate, but can become unsatisfactory if the breakdown rate increases. To deal with this issue, it is necessary to take the data uncertainty and the perturbations into account. Since several years, operational researchers are aware of this issue and have proposed some process and approaches to deal with uncertainty and perturbations.

The goal of this paper is to analyze how the PDS paradigm can be involved inside the process proposed by operational researchers to deal with perturbations and to identify the knowledge and information about operational research works dealing with scheduling under uncertainties and to highlight if some of them could be useful to deal with PDS re-scheduling acting in uncertain production and/or logistic environment. The rest of the paper is organized as follows. The section 2 is dedicated to present how optimization can take into account inherent uncertainties and perturbations and proposes a 3-steps solution process to deal with uncertainties and perturbations. The sec-tion 3 deals with the step 1 and more specifically on the concepts of robustness in operational research. The section 4 focuses on the step 2 and presents how the concept of Product-Driven-System can be a good candidate for implementing this step as a reacting system against perturbations. Moreover, this section proposes a first overview of the models and approaches coming from Operation Research that can be useful for implementing efficiently these types of system. Finally, a conclusion is given with some perspectives in the section 5.

2

Dealing with uncertainty: a full solution process

Classical optimization

Classically, solving an optimization problem consists in building a solution that optimizes a criterion (that is assumed to be a minimization criterion in this section without loss of generality) and satisfies some constraints assuming that the problem data are certain and sure. This particular string of data can be seen as a forecast instance that is used to compute . Getting an optimal solution is still a problem that is often hard. An optimal solution to the problem for an instance is denoted * and its corresponding performance is denoted * . Otherwise, the performance of a solution applied to an instance relatively to an optimization criterion is denoted . The classical way to solve an optimization problem without uncertainty is the predictive approach. An off-line algorithm builds an optimal solution * for the forecast instance , and guarantees an optimal performance for this instance only, valued by * . In practice, the real system is subject to perturbations such that the solution * is applied to the actual instance that may be different from the forecast instance , and * may even no longer be admissible. In the most optimistic case (when the solution remains admissible for ), the actual performance * can be "far" from the forecast performance * , and also far from the optimal value for , * . Then, a costly solution step may return a poor-quality solution.

A full solution process for dealing with uncertain context

There are two complementary ways for taking uncertainties into account. The first one is concerned with uncertainties that are explicitly depicted. Those uncertainties are somehow expected. The second way concerns unexpected perturbations which the system has undergone. Expected uncertainties can be taken into account more or less in an anticipative optimisation structure, that is the robust approach. Unexpected uncertainties have to be taken into account in a reactive procedure. In [START_REF] Billaut | Introduction to Flexibility and Robustness in Scheduling[END_REF], the generic structure for dealing with uncertainties is addressed. It is formally defined for addressing scheduling problems. It is composed of three steps.

Step 0: static problem definition.

Classic specifications of the optimisation problem are given along with the optimisation criterion z. Moreover,.when uncertainties are identified, it is necessary to produce a model of these uncertainties. Several possibilities exist. Uncertainties can be modelled as stochastic parameters [START_REF] Dauzère-Pérès | Service Level in Scheduling[END_REF] or parameters belonging to fuzzy intervals [START_REF] Dubois | Fuzzy Scheduling: Modelling Flexible Constraints vs. Coping with Incomplete Knowledge[END_REF] or belonging to a set of scenarios or instances [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF], [START_REF] Espinouse | On the Robustness of Multi-Purpose Machines Workshop Configuration[END_REF]. This set of instances can be a continuous or a discrete interval. A specific robustness criterion has to be defined related to the expected risk answering the question: "what must be guaranteed despite these perturbations?"

Step 1: calculation of a set of anticipative solutions by an off-line algorithm.

From the available knowledge about perturbations (the risk to be covered defined in step 0), one or more algorithms can be used to build a set of robust solutions guarantying a performance on the considered risk as defined in step 0. This set can include one or more solutions. Instead of computing an optimal solution for a single forecast instance, a global performance on the risk to be covered is addressed. Such solutions if they exist, are said to be robust for the considered risk.

Step 2: calculation of the applied solution by an on-line algorithm. The on-line algorithm uses the progressive knowledge about environment to implement a solution knowing the anticipative solutions. This solution can be chosen among the set of solutions calculated in step 1 or can result from a reactive adaptation of anticipative choices. The gap between the implemented solution and the anticipative one depends on the perturbations that occur: if they are included in the expected risk to be covered then the reactive procedure consists in choosing a solution among the robust previously computed solutions, otherwise all changes are possible. Moreover, this asks the question of the detection of the perturbation. In this dynamic procedure, the problem of guaranteed performance is open.

3

Step 1: taking robust decisions

What is robustness?

Developing robustness features for the decision to be made has appeared to be an efficient way of coping with deterministic uncertainties as in [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF]; [START_REF] Vincke | Robust Solutions and Methods in Decision-Aid[END_REF][START_REF] Perny | A Decision-Theoretic Approach to Robust Optimization in Multivalued graph[END_REF][START_REF] Kalaï | Robust 1-Median location Problem on a Tree[END_REF][START_REF] Roy | Robustness in Operational Research and Decision Aiding: A Multi-Faceted Issue[END_REF] even though researchers use different measures of robustness. [START_REF] Beyer | RobustOptimization -a Comprehensive Survey[END_REF] identifies several types of uncertainty involved in robustness optimization and several ways of formulating and addressing the corresponding problems in the field of parameter design. In [START_REF] Roy | Robustness in Operational Research and Decision Aiding: A Multi-Faceted Issue[END_REF], robustness is defined as a capacity for withstanding "vague approximations" and/or "zones of ignorance" to prevent undesirable impacts, notably the degradation of the properties to be maintained. What are exactly the so-called properties to be maintained and the considered "approximations" and "zones of ignorance" is strongly application dependent, and has led researchers to develop a large variety of robustness approaches. Many robustness definitions can be found in the literature.

The five following papers are devoted to such definitions: [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF], [START_REF] Kalaï | Robust 1-Median location Problem on a Tree[END_REF][START_REF] Roy | Robustness in Operational Research and Decision Aiding: A Multi-Faceted Issue[END_REF], [START_REF] Aubry | A Generic Off-line Approach for Dealing with Uncertainty in Production Systems Optimisation[END_REF][START_REF] Galand | OWA-based Search in State Space Graphs with Multiple Cost Functions[END_REF]. A lot of other papers are devoted to finding a robust solution for a given problem and explicitly proposing or not a measure of robustness. It is possible to sort the robustness definitions into two categories. The first category defines a robust solution as a solution that optimizes a robustness criterion. This point of view has the advantage that classical models and approaches used in Operational Research can be used for addressing this problem. The second category defines a robust solution as a solution that satisfies a condition (or a set of conditions). Such a vision for robustness allows practitioners to keep their solution processes and to check for the robustness of any solution with no restriction.

4

Step 2: React after the occurrence of perturbations

The product centric paradigm/Product Driven Systems

When perturbations don't concern directly data (like variation in demand) but are relative to specific events occurring on the shop-floor or in the supply chain, it is necessary to react on-line. As previously introduced, Product Driven Systems (PDS) are seen today as a good alternative to address this challenge. The idea is to deal directly with products whose information content is permanently bound to their material content and which are able to influence the decisions made about and for them. Therefore, productdriven control has an impact on decision-making procedures as well as on information exchange and storage. PDS are thus good candidates for covering the step 2.

Re-optimization or Online optimization

In the production step, an in-process product can manage its own manufacturing, dispatching or operating lists and priorities, according to the real state of the production system and possible dysfunctions occurring on the shop floor or modifications concerning the due dates or the demand volume. It can ask for specific production services to resources and communicate with the other products to negotiate priorities and production deadlines. In the logistic phase, active products in a system with safety constraints can supervise their own operations, triggering alarms when required by cooperating with other active components, thus improving the availability and maintainability of the system and obtaining an ambient system [START_REF] Parlikad | RFID-Based Product Information in End-of-life Decision Making[END_REF]. All these re-scheduling cases could be solved in a more reactive way in switching down from the centralize control system to PDS. Very quickly PDS could find, if exist, a feasible solution to do production or logistic activities remaining after the specific event. Obviously if no solution emerges at the operational level it would be still necessary to switch back to the centralize way to find an optimal solution. Ideally, to be the most possible reactive, this kind of process must be "on-line" to be sure that the real system won't change during the decision process as highlighted in [START_REF] Li | Fuzzy Decision-Making Method for Product Holons Encountered Emergency Breakdown in Product-Driven System: an Industrial Case -SOHOMA[END_REF].

The main issue for researchers is then to provide accurate mechanisms to define "online" the best switching dates (and/or the best switching decision-making levels) for control holons/agents so that they behave in a sense that the behavior of the hybrid architecture stays globally optimized despite disturbances. In this context, flexibility and resilience are two performance indicators that are interesting for evaluating a PDS.

4.3

Models and approaches for reacting after perturbations

Models.

Regarding Operational Research, two main models are used for modelling an optimization problem: graphs and mathematical programs. When dealing particularly with operations scheduling problems, it is easy to check that the mathematical programs are more used in this context. According to the type of the mathematical program (linear or not, with integer variables or not…), associated solution methods are existing for finding the optimal solution. And these methods are implemented in commercial tools like Cplex, Lingo. The efficiency of the methods for solving such models is particularly sensitive to the type of variables, the number of variables and the number of constraints.

When dealing with operations scheduling (and so re-scheduling), two subproblems must be solved. The first one concerns the allocation of operations to machines and the second one concerns the sequencing of these operations with possible precedence constraints to be satisfied. We can note that the allocation problem can be sometimes fixed a priori when only one machine is qualified for executing a given operation. We will see in the next paragraph that the fact that the allocation problem is fixed or not has an incidence on the solving method.

Solution approaches.

Classical Operational Research approaches for solving optimization problems can be split into two categories:  Exact methods: Branch and Bounds algorithms (for solving Mixed Integer Linear Programs), dedicated algorithms. These approaches have the advantage to be able to find the optimal solution but are often not efficient for real-sized problems.  Approximation methods: mainly heuristics and metaheuristics. These approaches have the advantage to be efficient even for real-sized examples and to be able to find good solution regarding the optimization criterion.

For identifying the relevant approaches for solving re-scheduling problems in the context of PDS, it is mandatory to take into account at least two inputs: the available time for finding the schedule and the type of decision to be taken.

The available time is clearly dependent of the duration of the unpredicted perturbation. In fact, if the time for taking the decision becomes bigger than the time for solving directly the perturbation, the re-scheduling becomes useless. For instance, imagine that a machine failed and that we can predict that the machine can be repaired with a given duration, this will fix the available time for finding a new schedule. It is precisely here that the PDS concept is the most useful because its application must help to evaluate this available time through the information that can give the product the closest from the production system. The product can help to detect the unpredicted perturbation and then the merged information coming from the different products is able to give an overall situation and then can help to decide which type of decision must be taken.

The type of decision to be taken concerns mainly if re-allocation is needed or not. If re-allocation is needed, that means that an integer variable is necessary for representing the allocation of each operation to one machine. That means that the mathematical program for modelling the problem becomes a Mixed Integer Linear Program (MILP). This type of problem is known to be NP-Complete: that means that no efficient solution method is known for solving efficiently a MILP.

According to several inputs, we define a first table giving the preferable solution methods depending on some criteria arbitrarily defined. To our best of knowledge, such a work has never been done such that the identified criteria/needs should be enriched and discussed. The first table is given in the next figure. Future works must be done to i) fill the gaps in the table, ii) better justifying the criteria in the table.

Conclusions

This paper investigates the product-driven systems as a candidate for reacting against perturbations and for taking part in a full solution process existing in the operational research context. Moreover, this paper is a first attempt to identify the solution approaches from operational researchers that are relevant for implementing a PDS.

Valuable efforts should still be done for better identifying the different situations that can occur when dealing with perturbations, and thus to associate the better solution approaches to deal with these situations.

Fig. 1 .

 1 Fig. 1. -Identified solution methods according to several criteria


Laurent Busé

Mohamed Elkadi
email: elkadi@math.unice.fr

André Galligo Galaad

A computational study of ruled surfaces

We study rational ruled surfaces and µ-bases which were recently considered in a series of articles by Chen and coworkers. We give short and conceptual proofs with geometric insights and ecient algorithms. In particular, we provide a method to reparameterize an improper parameterization and we also briey explain how to deal with approximate input data. Finally we provide an algorithmic description of self-intersection loci.

Introduction

During the XIX th (and the beginning of the XX th ) century, many articles were dedicated to the study of algebraic ruled surfaces (see e.g. [START_REF] William | The theory of ruled surfaces[END_REF]) and more generally of rational ones. In the last decade, there has been a renewed interest in the subject, mainly driven by applications in Computer Aided Design and Manufacturing. A series of papers by Chen and coworkers ( [START_REF] Chen | Reparameterization of a rational ruled surface using the µ-basis[END_REF][START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF][START_REF] Chen | The µ-basis of a rational ruled surface[END_REF][START_REF] Cox | The moving line ideal basis of planar rational curves[END_REF]) attracted our attention. The question they initially addressed is: given a parameterization of a ruled surface (or a curve), get an implicit equation represented by the determinant of a matrix of linear forms, with a special structure.

In this paper, we rely on classical algebraic geometry to revisit and improve the works of Chen et al. to give shorter proofs and geometric insights. We also provide more ecient algorithms and we consider the case of approximate data, which is an important issue for the aimed applications.

The paper is organized in two parts. In the rst one, we recall two classical geometric approaches on rational ruled surfaces and derive some consequences for simplifying parameterization of ruled surfaces with regards to properness and base points. In particular, we provide algorithms to reparameterize such surfaces in order to get proper parameterizations base point free. In the second part, we review the notion of µ-basis introduced in [START_REF] Chen | The µ-basis of a rational ruled surface[END_REF]; we provide shorter and more conceptual proofs of existence of a µ-basis and also reparameterization as in [START_REF] Chen | Reparameterization of a rational ruled surface using the µ-basis[END_REF].

On the way, we describe, analyze and compare dierent algorithms for computing such a µ-basis. Finally, we end this paper by applying these techniques to the computation of self-intersection loci of ruled surfaces.

In the following, K is assumed to be an innite eld, and P n denotes the projective space of dimension n over K. We are primarily interested by K = Q, R, C, however, except in the last section, the main results of this paper and the given proofs are valid on any eld, with the following re-interpretation if K is a nite eld. Some intermediate constructions in our proofs rely on taking generic elements in K but the nal result will always be rational on K. So, when K is a nite eld the construction should be made in the algebraic closure of K which is innite, and at the end, one goes back to K thanks to the rationality of the aimed result.

Rational ruled surfaces

An ane rational ruled surface is given by a parameterization φ :

K 2 → K 3 (s, t) → f 1,0 (s) + tf 1,1 (s) f 4,0 (s) + tf 4,1 (s) , f 2,0 (s) + tf 2,1 (s) f 4,0 (s) + tf 4,1 (s) , f 3,0 (s) + tf 3,1 (s) f 4,0 (s) + tf 4,1 (s) , (1)
where the f i,j 's are polynomials in K[s]. We set f i (s, t) := f i,0 (s) + tf i,1 (s) for i = 1, . . . , 4, and n 0 := max i=1,...,4 deg(f i,0 (s)), n 1 := max i=1,...,4 deg(f i,1 (s)). We denote by S the closed image of φ, i.e. the smallest algebraic (irreducible) variety in P 3 containing the image of φ and assume that it is a surface; this amounts to require that both vectors (f 1,0 (s), . . . , f 4,0 (s)) and (f 1,1 (s), . . . , f 4,1 (s)) are K[s]linearly independent. We assume moreover, for simplicity in the following discussions, that gcd(f 1 (s, t), . . . , f 4 (s, t)) is a (non-zero) constant. Without loss of generality, we can assume that n 1 ≥ n 0 , since otherwise we can reparameterize S by substituting t by 1/t ′ . For an algebraic and geometric study, we also consider the corresponding projective setting φ h :

P 1 × P 1 → P 3 (s : s; t : t) → (f h 1 : f h 2 : f h 3 : f h 4 )(s, s; t, t)
where, for i = 1, . . . , 4,

f h i (s, s; t, t) := ts n 1 -n 0 f h i,0 (s, s) + tf h i,1 (s, s), with f h i,1 (s, s) (resp. f h i,0 (s, s)
) being the homogenization of f i,1 (s) (resp. of f i,0 (s)) of degree n 1 (resp. of degree n 0 ). Note that S is also the image of φ h .

Hereafter, we will denote by deg(φ) (resp. deg(φ h )) the degree of the rational map φ (resp. φ h ) onto its image S. This invariant roughly corresponds to the number of points in the preimage of a generic point on S. In particular, if φ is generically injective, or equivalently if φ h is generically injective onto S, then deg(φ) = deg(φ h ) = 1 (we always have deg(φ) = deg(φ h )).

Base points and the degree formula

We give here a formula to compute the degree of the ruled surface S in terms of polynomials dening its parameterization. Recall that a base point of the parameterization φ h is a point in the parameter space P 1 × P 1 which annihilates the polynomials f h 1 , . . . , f h 4 . Since the base points are isolated by assumption, it is known that the quantity deg(S) deg(φ) equals 2n 1 minus the number of these base points counted with multiplicities; as t appears linearly, their multiplicities are given by the order of (s, s).

The point (∞, 0) ∈ P 1 × P 1 is a base point of multiplicity (at least) n 1 -n 0 and the other base points (including the possible increasing of the multiplicity of (∞, 0)) are counted as the degree of the gcd g h (s, s) of all the 2 × 2 minors

f h i,0 (s, s) f h i,1 (s, s) f h j,0 (s, s) f h j,1 (s, s) , 1 ≤ i < j ≤ 4. The degree formula is hence deg(S) deg(φ) = n 1 + n 0 -deg(g h (s, s)).
(

) 2
It is straightforward to turn this formula into an ane version which is more suited for eective computations, by counting separately the base points with s = 0.

Proposition 2.1: With the above notations, we have

deg(S) deg(φ) = max 1≤i<j≤4 deg f i,0 (s) f i,1 (s) f j,0 (s) f j,1 (s) -deg(g(s)),
where g(s) := gcd

f i,0 (s) f i,1 (s) f j,0 (s) f j,1 (s)
:

1 ≤ i < j ≤ 4 . Moreover, deg(g(s)) is
the number of base points, counted with multiplicities, of φ h which are at nite distance in s.

Plücker coordinates and properness

In this paragraph we interpret the ruled surface S in its Plücker coordinates; this will permit us to reparameterize properly S.

For almost all value of (s : s) ∈ P 1 , the image of φ h (s, s; -) is a line in P 3 that we denote by D (s:s) . Thus, S is the closure of ∪ (s:s)∈P 1 D (s:s) . This gives rise to a geometric approach on ruled surfaces initiated by Plücker, Grassmann and Cayley. The line D (s:s) is represented by its Plücker coordinates p i,j (s, s) :=

f h i,0 (s, s) f h i,1 (s, s) f h j,0 (s, s) f h j,1 (s, s) , 1 ≤ i < j ≤ 4,
which satisfy the quadratic relation Q := p 1,2 p 3,4 -p 1,3 p 2,4 + p 1,4 p 2,3 = 0. Any point of the quadric Q of P 5 (dened by the equation Q = 0) determines a unique line in P 3 . Therefore, a rational ruled surface can be viewed as a rational curve C on Q in P 5 , and this curve is given by the parameterization φ G : P 1 → Q ⊂ P 5 (s : s) → (p i,j (s, s)) 1≤i<j≤4 . Now, associated to the map φ G , which parameterizes a curve, we have the inclusion of function elds K(C) ֒→ K(s). By Luröth theorem [17, 10.2] there exists an intermediate eld K(σ), which admits constructive and algorithmic versions (see e.g. [START_REF] Homann | Parametric algebraic curves and applications[END_REF]), where σ = h(s) ∈ K(s) and such that p i,j (s, 1) = pi,j (σ) and (p i,j (σ)) 1≤i<j≤4 denes a proper parameterization of C. We refer to these papers for algorithms and implementations of this property, even in the real setting (K = R). This result is now going to be used to prove the following proposition. Proposition 2.2: An improper parameterization of a rational ruled surface can be replaced by a proper one via a change of parameterization in P 1 × P 1 :

(s, t) → (σ, τ ) := h(s), λ 1 (s) + tΛ 1 (s) λ 0 (s) + tΛ 0 (s)
where λ 0 (s),λ 1 (s),Λ 0 (s) and Λ 1 (s) are in K[s].

Proof: We take again the previous notation and x σ. Via the proper reparameterization of the curve C, all the lines D s such that h(s) = σ are equal in P 3 to a line ∆ σ . Solving a linear system, we nd two points M 0 (σ) and M 1 (σ) on ∆ σ with coordinates which are rational fuctions in σ. Hence, if h(s) = σ, any point of D s = ∆ σ can be written as a linear combination M 0 (σ)+τ M 1 (σ), with τ in P 1 . Expanding this relation, we nd four rational scalar functions λ 0 (s),

λ 1 (s), Λ 0 (s), Λ 1 (s), such that τ = λ 1 (s) + tΛ 1 (s), f 0 (s) = λ 0 (s)M 0 (h(s)) + λ 1 (s)M 1 (h(s)) and f 1 (s) = Λ 0 (s)M 0 (h(s)) + Λ 1 (s)M 1 (h(s)). ✷
Before ending this paragraph, let us make another remark regarding this interpretation of S in terms of its Plücker coordinates. We will consider in the sequel a generic plane section of the ruled surface S given by a proper parameterization without base points, except the trivial one (∞, 0) with multiplicity n 1 -n 0 . Consider a generic linear form, with coecients in K, Z 1 := aX + bY + cZ + dT.

Then, the section D :

{Z 1 = 0} of S satises t = af 1,0 (s) + bf 2,0 (s) + cf 3,0 (s) + df 4,0 (s) af 1,1 (s) + bf 2,1 (s) + cf 3,1 (s) + df 4,1 (s) ,
and hence (X, Y, Z) is proportional to the vector

(bp 1,2 + cp 1,3 + dp 1,4 , -ap 1,2 + cp 2,3 + dp 2,4 , -ap 1,4 -bp 2,4 -cp 3,4 ).
We see that the curve D is a projection on P 2 of the curve C ⊂ Q ⊂ P 5 attached to the ruled surface S. Moreover, as a, b, c, d are generic coecients, we can expect that D captures some of the features of C, hence of S. This will be the case as we will see in the next section.

Scrolls and base points

Another geometric point of view on rational ruled surfaces, initiated by Segre, is to consider them as projection of a surface in a higher projective space. Such a surface is nowadays denoted by F(n 0 , n 1 ) and called a scroll in

P N with N = n 0 + n 1 + 1.
It is obtained by considering two Veronese parameterized curves of respective degree n 0 and n 1 in P n 0 and P n 1 , respectively. Then, F(n 0 , n 1 ) is the union of the lines joining the points with same parameters in P N . Its parameterization is simply:

K 2 → P N (s, t) → (1 : s : s 2 : • • • : s n 0 : t : ts : ts 2 : • • • : ts n 1 ).
This gives rise to a natural and rened presentation of ruled surfaces in P 3 which will allow us to reparameterize φ without base points, except the trivial one (∞, 0) with multiplicity n 1 -n 0 .

Let us say that φ is of type ((n 0 , n 1 ), 1) if it satises (1) (recall that n 1 ≥ n 0 ). The couple (n 1 , 1) is the bidegree of the map φ h in the projective setting. By abuse of language, we will say that such a parameterization is base point free if the obvious base point is the only base point with the lowest possible multiplicity n 1 -n 0 . In this case, the degree of S is n 0 + n 1 . Proposition 2.3: Suppose that S is a ruled surface in P 3 given by a proper parameterization φ h : P 1 ×P 1 → P 3 of bidegree (n, 1) with m base-points, counted with multiplicities. Then, there exists a parameterization ψ of type ((n 0 , n 1 ), 1) of S which is base-point free and such that with 2n -m = n 0 + n 1 . Moreover the morphism of reparameterization Λ : P 1 × P 1 → P 1 × P 1 , which satises φ = ψoΛ, is such that for any s, Λ(s, t) = (σ, τ ) where τ is an homography in t with coecients depending only on s.

Proof: We proceed by induction. First suppose that among the m base-points of φ, there exist two points (s 1 , t 1 ) and (s 2 , t 2 ) such that t 1 = t 2 . We perform an homography on P 1 which sends t 1 to 0 and t 2 to ∞.

If s 1 = s 2 , then the new φ h writes φ h (s, t) = t(s -s 1 )V 1 (s) + (s -s 1 )V 2 (s)
, and simplifying by s -s 1 , the number n decreases strictly. If

s 1 = s 2 , the new φ h writes φ h (s, t) = t(s -s 1 )V 1 (s) + (s -s 2 )V 2 (s). We set t = (s -s 2 ).τ s -s 1
, and we can simplify by s -s 2 to get a smaller number n. Now, if all the remaining m 1 base points have the same rst coordinate t 1 , we send t 1 to 0. Then the new φ h writes φ h (s, t) = tV 1 (s) + g(s)V 2 (s), with deg(g) = m 1 . We set t = g(s).τ , so we can simplify by g(s), and we are done.

Finally, in all the performed changes of parameterizations we had the required property for Λ(s, t), property which is stable by composition. ✷ Proposition 2.4: With the notations of the previous proposition, the coecients of ψ belongs to the eld generated by the coecients of φ.

Proof: We take again the notations of the previous proposition and its proof. The change of parameterization Λ(s, t) leaves s unchanged. So, for a xed generic s, the images of the two parameterizations φ and ψ give the same line that we call D s . The Plücker coordinates of D s are the six 2 × 2 determinants p i,j =

f h i,0 f h j,1 -f h i,1 f h j,0 , with 1 ≤ i < j ≤ 4, considered in subsection 2.2.
As we have seen in subsection 2.1, their gcd has degree m. Dividing out by this gcd we get six polynomials in s of degree 2n -m, that we denote by p i,j .

Therefore X i = ψ i (s, τ ), for i = 1, . . . , 4, satisfy the four linear equations of the form p i,j X k + p j,k X i + p k,i X j = 0 corresponding to the vanishing of 3 × 3 determinants, and expressing that the point belongs to the line D s . We expand, in the case τ = 0 (respectively τ = ∞), these conditions into a (large) linear system in the coecients of ψ. The previous proposition says that this linear system admits a solution in the algebraic closure. By Cramer's rule, it also admits a solution in the eld of the coecients of φ.

✷

Notion of µ-basis

We begin with a review of the denition and some properties of a µ-basis of a rational plane curve that we will use in our approach to study and to construct a µ-basis of the ruled surface S.

µ-basis of a plane rational curve

The notion of µ-bases of a rational plane curve appears rst in the paper [START_REF] Cox | The moving line ideal basis of planar rational curves[END_REF]. It is useful in Computer Aided Geometric Design (see [START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF][START_REF] Sederberg | A direct approach to computing the µ-basis of planar rational curves[END_REF]).

Let C be a plane curve given by a parametric representation

ψ : (s, s) ∈ P 1 → g 1 (s, s) : g 2 (s, s) : g 3 (s, s) ∈ P 2 , (3)
where g 1 , g 2 , g 3 are homogeneous polynomials in K[s, s] of degree δ. We consider the rst module of syzygies

Syz(g 1 , g 2 , g 3 ) = {(h 1 , h 2 , h 3 ) ∈ K[s, s] 3 : h 1 g 1 + h 2 g 2 + h 3 g 3 = 0} ⊂ K[s, s] 3
which ts in the exact sequence of K[s, s]-modules

0 → Syz(g 1 , g 2 , g 3 ) → K[s, s] 3 → I := (g 1 , g 2 , g 3 ) → 0.
Let us denote by µ the smallest positive integer such that there exists a nonzero element of degree µ in Syz(g 1 , g 2 , g 3 ). It turns out that this syzygy module is free by Hilbert Syzygy Theorem ( [11, corollary 19.7]). The Hilbert-Burch Theorem [11, theorem 20.15] shows that it has rank 2, and Syz(g 1 , g 2 , g 3 ) is a graded free K[s, s]-module such that we have the following graded isomorphism (using standard notation) Of course a µ-basis of C is not unique; but if (p 1 , q 1 ) and (p 2 , q 2 ) are two dierent µ-bases such that deg(p i ) ≤ deg(q i ), for i = 1, 2, then there exist α, β in K * and a homogeneous polynomial h ∈ K[s, s] of degree deg(p 2 ) -deg(p 1 ) which satisfy p 1 = αp 2 , q 2 = βq 1 + hp 1 (see e.g. [START_REF] Cox | The moving line ideal basis of planar rational curves[END_REF]). Remark 3.2: Any basis (p, q) of Syz(g 1 , g 2 , g 3 ) such that deg(p) + deg(q) = d is a µ-basis of the parameterization (3) of C.

K[s, s](-µ) ⊕ K[s, s](-d + µ) ≃ Syz(g 1 , g 2 , g 3 ) ⊂ K[s, s] 3 , (4)
Let p := (p 1 , p 2 , p 3 ) and q := (q 1 , q 2 , q 3 ) be the two elements of a µ-basis of the parameterization (3) of C. It is possible to recover a parameterization of the curve C. Indeed, the Hilbert-Burch Theorem also says that there exists 0 = a ∈ K[s, s] such that

I = (g 1 , g 2 , g 3 ) = a p 2 q 2 p 3 q 3 , - p 1 q 1 p 3 q 3 , p 1 q 1 p 2 q 2 ,
where the ideal on the right hand side has codimension 2 and thus gives a reparameterization of C. Note that the polynomial a is equal, up to a multiplication by a nonzero constant in K, to the gcd of g 1 , g 2 and g 3 in K[s, s]. Now we assume that the polynomials g 1 , g 2 and g 3 are relatively prime and we discuss the computation of a µ-basis of the associated rational curve. Two algorithms to compute a µ-basis of a rational plane curve has been presented in [START_REF] Sederberg | A direct approach to computing the µ-basis of planar rational curves[END_REF] and [START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF]. They proceed by rewriting rules, they are similar to Gröbner basis computation for a module, and require O(d 2 ) arithmetic operations. Their strategy is to reduce a simple system of three generators of Syz(g 1 , g 2 , g 3 ) to a µ-basis of C which contains two elements. These algorithms do not seem well suited for computing with approximate data, encountered in Computer Aided Geometric Design. We have implemented the algorithm in [START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF] (their constant in O(d 2 ) is better than in [START_REF] Sederberg | A direct approach to computing the µ-basis of planar rational curves[END_REF]) in maple in order to compare it with the algorithm that we describe below. It turns out that there is an important increase of the size of the coecients during the computation; this will be illustrated by a table of experiments below. Now we present a simple and more ecient algorithm which relies on basic linear algebra: Input: Three homogeneous polynomials g 1 (s, s), g 2 (s, s), g 3 (s, s) in K[s, s] of the same degree δ ≥ 1. Output: A µ-basis (p, q) of the rational curve parametrized by [START_REF] Chen | Reparameterization of a rational ruled surface using the µ-basis[END_REF]. Strategy: Solve the linear system in the coecients of p and q with respect to the monomial basis.

The corresponding matrix is similar to a Sylvester one but with three blocks dened respectively by g 1 , g 2 , g 3 . This kind of structured matrix is called pseudo-Toeplitz and behaves nicely with respect to complexity of basic operations via Fast Fourier Transform, but also via a naive implementation as we will see.

The integer µ can be deduced from the rank of this matrix, whose size is at

most d + [ d 2 ] + 1 × 3 [ d 2 ] + 1)
. Similarly, we obtain q as a solution of a pseudo-Toeplitz system of size at most (2d -µ + 1) × 3(d -µ + 1). It is known that solving such linear systems requires O d(log d) 2 arithmetic operations (see [1]).

Our experiments rely on maple commands which are not optimized. We also implemented a oating point version using the maple Linear Algebra package.

The examples show that the coecients of µ-bases obtained by linear algebra are much shorter than the ones obtained by algorithms in ( [START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF][START_REF] Chen | The µ-basis of a rational ruled surface[END_REF]); and moreover their computation takes also less time, as indicated below. The use of oating point (double) is interesting because, in the generic cases, the error was smaller than 10 -9 . The polynomials involved in our experiments are dense and randomly generated.

In the following table, time is given in seconds, mdig is the maximum number of digits in the coecients of the computed µ-basis, -means that the computation is stopped after twenty minutes. The second array of this table is obtained using our algorithm and the third one using Chen We notice that the algorithm running with oating points is much faster, as it takes 3 seconds for degree 100.

The advantage of our approach based on linear algebra is to compute with approximate data. The input parameterization of the curve C is given by polynomials g 1 , g 2 , g 3 of a xed degree, but whose coecients are known with some imprecision; similarly to the situation in the univariate approximate GCD (see [START_REF] Corless | The singular value decomposition for polynomial systems[END_REF][START_REF] Ioannis | Numerical univariate polynomial GCD[END_REF][START_REF] Zeng | The approximate gcd of inexact polynomials[END_REF]). Here, we want to compute an approximate µ-basis of the parameterization (3). First, we test if g 1 , g 2 , g 3 are coprime; this can be done with certication and eciently using Rupprecht's algorithm (see [START_REF] Rupprecht | An algorithm for computing certied approximate GCD of n univariate polynomials[END_REF]). Otherwise, we divide by the approximate gcd and replace g 1 , g 2 , g 3 by approximate polynomials g1 , g2 , g3 which are coprime and dene the same curve (within the given precision). Then, as above we form the matrix with pseudo-Toeplitz structure and we adapt the argument in [START_REF] Ioannis | Certied approximate univariate GCDs[END_REF] using SVD to compute the number µ and a certied solution within the precision.

ψ

-→ g 1 (s, s), g 2 (s, s), g 3 (s, s) is exactly the intersection of S with the plane z = 0. Consequently, we obtain a K[s, s]-homomorphism

Φ : Syz K[s,s] (f h ) → Syz(g 1 , g 2 , g 3 ) (h 1 , h 2 , h 3 , h 4 ) → (h 1 , h 2 , h 4 )
which is injective (unless f h 3,0 = f h 3,1 = 0, in which case we change the section). Consider a generic projective plane Z 1 = aX + bY + cZ + dT = 0 in P3 . Then we change the coordinates such that Z 1 replaces Z. Since both polynomial vectors

(f h 1,0 , f h 2,0 , f h 3,0 , f h 4,0 ) and (f h 1,1 , f h 2,1 , f h 3,1 , f h 4,1
) are linearly independent over K[s, s], and by the genericity of coecients a, b, c, d, f h 3,0 and f h 3,1 are coprime. Now, Φ is an isomorphism. Indeed, let (h 1 , h 2 , h 4 ) ∈ Syz(g 1 , g 2 , g 3 ), then

s n 1 -n 0 (h 1 f h 1,0 + h 2 f h 2,0 + h 4 f h 4,0 )f h 3,1 = (h 1 f h 1,1 + h 2 f h 2,1 + h 4 f h 4,1 )f h 3,0 . Since gcd(f h 3,0 , f h 3,1 ) = 1, f h 3,0 divides h 1 f h 1,0 + h 2 f h 2,0 + h 4 f h 4,0 .
Then, there exists a homogeneous polynomial h ∈ K[s, s] such that The integer d involved in this proposition can be easily obtained from the parameterization of S using formula (2) or Proposition 2.1. Note also that, as we saw in the proof of this proposition, the study of a µ-basis of a ruled surface can be reduced to the study of a µ-basis of a generic plane section of this surface. This last remark is the cornerstone of our computational approach of µ-bases of ruled surfaces. Definition 3.4: A basis of the K[s, s]-module Syz K[s,s] (f h ) of minimal degree is called a µ-basis of the ruled surface S.

s n 1 -n 0 (h 1 f h 1,0 + h 2 f h 2,0 + h 4 f h 4,0 ) = hf h 3,0 , h 1 f h 1,1 + h 2 f h 2,1 + h 4 f h 4,1 = hf h 3,1 . So (h 1 , h 2 , -h, h 4 ) ∈ Syz K[s,s] (f h ).
An algorithm is proposed in [START_REF] Chen | The µ-basis of a rational ruled surface[END_REF] which gives an explicit way to compute a µbasis of the ruled surface S. It is based on rewriting rules on a known system of four generators of Syz K[s,s] (f h ). Here we give an ecient approach which reduces the study of µ-bases of S to µ-bases of an algebraic plane C via a plane section of the surface S. Then we lift the µ-basis of this curve C, computed by the method developed in the previous subsection, to a µ-basis of S.

Our geometric strategy is to lift a µ-basis (p, q) of a generic plane section C corresponding to z = η, given by three polynomials g 1 , g 2 , g 3 , of the ruled surface S in order to construct a µ-basis of S.

If p = (a 1 , b 1 , δ 1 ) and q = (a 2 , b 2 , δ 2 ), for i = 1, 2, let L i = a i (s)x+b i (s)y+δ i (s) be the associated moving lines to p and q. Consider the plane Π i dened by L i and the line D s obtained from the parameterization of S when the parameter t is xed, its equation is a i (s)x+b i (s)y+c i (s)z+d i (s) = 0. Since δ i (s) = ηc i (s)+d i (s), the equation of Π i is a i (s)x + b i (s)y + c i (s)(z -η) + δ i (s) = 0. Using a point in D s which does not belong to the plane section, we compute c i (s) and we deduce d i (s). See the illustrative Figure 1. We now describe the use of µ-bases to give an algebraic method, alternative to the one presented in subsection 2.3, in order to reparameterize a ruled surface.

D C L1 L2 PSfrag replacements C L 1 L 2 D s z = η
We follow [START_REF] Chen | Revisiting the µ-basis of a rational ruled surface[END_REF] but we shorten the proof. Proposition 3.5: Let (p, q) be a µ-basis of the rational ruled surface S. Denote by (p, q) a µ-basis of the ruled surface parameterized by p(s) + tq(s). Then p(s) + tq(s) is a base point free parameterization of S.

Proof: Set p := (p 1 , . . . , p 4 ) and q := (q 1 , . . . , q 4 ), and M φ the 2 × 4 matrix (f i,j (s)) i=0,1;j=1,...,4 , with the notation of (1). Consider the exact sequence

0 → Syz K[s] (f ) (p,q) ---→ K[s] 4 M φ --→ K[s] 2 .
On one hand, the usual duality (apply Hom(-, K[s])) gives the following upper sequence which is exact in the middle. On the other hand, a µ-basis associated to the ruled surface p(s) + tq(s), denoted here by (p, q), gives the lower exact sequence. Therefore this diagram shows that, for almost all the values of s, both lines (f 0 (s), f 1 (s)) and (p(s), q(s)) are the same; so we get exactly the same surface.

K[s] 2 0 B @ f 1,0 f 1,1 . . . . . . f 4,0 f 4,1 1 C A # # G G G G G G G G K[s] 4 " p 1 . . . p 4 q 1 . . . q 4 « / / K[s] 2 0 / / K[s] 2 0 B @ p1
The absence of base points in the second parameterization comes from the property of minimality of the degree in a µ-basis. ✷

Implicitization and inversion

By Proposition 2.2 we can assume that the ruled surface S is given by a proper parameterization. The following results show that a µ-basis of S can be used to derive an implicit equation (see also [START_REF] Chen | The µ-basis of a rational ruled surface[END_REF]Theorem 3]) and compute an inversion formula for the ruled surface S.

Proposition 3.6: Let (p, q) be a µ-basis of the ruled surface S. The resultant Res(P, Q) of polynomials P = p 1 (s)x + p 2 (s)y + p 3 (s)z + p 4 (s), Q = q 1 (s)x + q 2 (s)y + q 3 (s)z + q 4 (s) in the variable s is exactly the implicit equation S(x, y, z) of the surface S.

Proof: First, observe that this resultant is not identically zero; otherwise P and Q would have a common factor in K[s], which contradicts the fact that (p, q) is a µ-basis. By construction of µ-bases, it is obvious that Res(P, Q) vanishes on S, so any implicit equation S(x, y, z) of S divides Res(P, Q). Moreover, Res(P, Q) is a polynomial in x, y, z of degree at most deg(S)(= deg(S)), and we are done.

✷

The previous result states that the resultant of a µ-basis gives exactly the implicit equation. As it is shown in [START_REF] Busé | Inversion of parameterized hypersurfaces by means of subresultants[END_REF], some matrices (including the Sylvester one) whose determinant is exactly this resultant can be used to compute an inverse of the parameter s of φ by means of some minors of this matrix; then an inverse of t can be straightforwardly deduced. Moreover, an algorithm to test the properness of the parameterization can be derived from this matrix (see [START_REF] Busé | Inversion of parameterized hypersurfaces by means of subresultants[END_REF]).

Notice that recently, Proposition 3.6 has been extended by Marc [START_REF] Dohm | Implicitization of rational ruled surfaces with µ-bases. Accepted to appear in[END_REF] to the non-proper case, providing directly an implicitization formula without relying on Proposition 2.2.

Self-intersections points on a ruled surface

Let S be a ruled surface in P 3 given by a parameterization φ : P 1 × P 1 → P 3 of type ((n 0 , n 1 ), 1), which is base point free. Then S has degree d := n 0 +n 1 . We set S = ∪D s , as it is an union of lines. We denote by A the curve of singular points of S. A point M of A is either an image of a critical point of φ, i.e. a point where the jacobian matrix

D(φ) D(s, t)
is of rank smaller than 2, or it is a double point of the parameterization i.e. M = φ(s 1 , t 1 ) = φ(s 2 , t 2 ) with (s 1 , t 1 ) = (s 2 , t 2 ). A direct computation in a chart shows that, generically, there are only a nite number of points of the rst kind and they are in the algebraic closure of the set of the points of the second kind. Here after we suppose that we are in that situation.

We cut S by a generic plane of P 3 , we obtain an algebraic plane curve C of degree d = n 0 + n 1 which is the image of a curve of bidegree (1, d) in P 1 × P 1 , hence rational; therefore C is also rational. By the adjunction formula, C admits generically

(d -1)(d -2) 2
double points. These points are precisely the intersection points between the singular curve A and the considered generic plane. So the degree of A is

(d -1)(d -2) 2
. The curve A lies on the surface S and is the image by φ of an algebraic curve denoted B in P 1 ×P 1 . We denote by (a, b) the bidegree of the equation f (s, t) = 0 of B. As the inverse image by φ of a plane has bidegree (n 1 , 1), expressing twice the intersection number of A with a generic plane, we get the equality: For a xed generic s 0 , the integer b counts the number of t = t i such that f (s 0 , t i ) = 0. In other words, the line D s 0 cuts b other lines D s of the family. The condition "cuts" is equivalent to say that the two lines are coplanar, or to say that the determinant det M (s 0 , 0), M (s 0 , ∞), M (s, 0) -M (s 0 , 0) The self-intersection locus lies naturally in (P 1 ×P 1 ) 2 , but it is more convenient to represent it by one of its 2D projection. The projection usually considered is on the rst and second P 1 factors. This amounts to eliminate the 2 variables (s 2 , t 2 ) in the system of 3 equations expressing that φ(s 1 , t 1 ) = φ(s 2 , t 2 ), in order to get a polynomial of bidegree (a, b). As the degree in t 2 of these expressions is 1, we eliminate t 2 by a simple substitution, so it remains two equations. Then s 2 is eliminated via a resultant.

s -s 0 , M (
An alternative computation is to compute, as in the previous section, an implicit equation F of S, then its derivatives and substitute the parameterization in these expressions. Finally we keep the gcd of all the obtained expressions; it is a polynomial in (s, t) of bidegree (a, b). Another interesting projection is the one on the second and the fourth P 1 factors. The simpler elimination of the (linear) variables (t 1 , t 2 ), described just above with a determinant, provides a symmetric polynomial in (s 1 , s 2 ) of bidegree (d -2, d -2). We can express this condition as a polynomial of total degree d -2 in the the sum σ and the product π of s 1 and s 2 . Let us call T the plane curve dened by this last polynomial. Then, T is birationnally equivalent to C, and it is easier to study.

  with d := δ -deg gcd(g 1 , g 2 , g 3 ) = deg(ψ) deg(C), where deg(ψ) denotes the degree of the parameterization ψ and deg(C) the degree of the curve C. Definition 3.1: A basis (p, q) of Syz(g 1 , g 2 , g 3 ) is called a µ-basis of the parameterization (3) of C if deg(p) = µ and deg(q) = d -µ.

  It is clear that Φ preserves the grading. To conclude the proof we use the isomorphism (4) and the fact that deg(φ) deg(S) = deg(ψ) deg(C).✷

Figure 1 :

 1 Figure 1: Lifting of a µ-basis from a generic plane section

(d - 1 )

 1 (d -2) = n 1 .b + 1.a.

  s, ∞) -M (s 0 , ∞) s -s 0 vanishes. Counting the degree in s, we get b = (n 0 -1) + (n 1 -1) = d -2. We deduce that a = (d -1)(d -2) -(d -2)n 0 = (n 1 -1)(d -2). When n 0 = n 1 = n, then d = 2n, a = 2(n -1) and b = 2(n -1)2.

  -Wang algorithm.

	degree	9	19	31	40	50
	(time, mdig) (0.04, 27)	(0.2, 66)	(5, 106)	(13, 141)	(107, 178)
	(time, mdig)	(3, 500)	(110, 2500)	(900, -)	(-, -)	(-, -)

|. Then (h 1 , h 2 , h

) is a homogeneous syzygy in Syz(g 1 , g 2 , g 3 ). Note that the curve C : (s, s)

Acknowledgments

This work has been partially supported by the french ANR GECKO.

µ-basis of a ruled surface

The notion of µ-bases was generalized to the case of a ruled surface in both papers ( [START_REF] Chen | The µ-basis of a planar curve-properties and computation[END_REF][START_REF] Chen | The µ-basis of a rational ruled surface[END_REF]). The study of this notion for the parameterized ruled surface S is done through the graded

We denote by µ the smallest positive integer such that there exists a nonzero element of degree µ in Syz K[s,s] (f h ). We have the following proposition:

Proof: We construct the claimed isomorphism as follows. Let h = (h 1 , h 2 , h 3 , h 4 ) be a homogeneous syzygy in Syz K[s,s] (f h ). We easily deduce that

We multiply the rst line by f h 3,1 (s, s), the second one by f h 3,0 (s, s) and we substrate them to get h 1 |f h