Yvette Marchand
email: yvette.marchand@univ-rouen.fr

Renaud Cazoulat
email: cafoulat@cnet.francetelecom.fr

Biological reef survey using spot satellite data classification by cellular automata method -Bay of Mont Saint-Michel (France)

Keywords: Cellular automata, Remote sensing, Mapping, Intertidal zone, Biological reef

A reef called ''Les Hermelles'' occurs in the intertidal zone of the Bay of Mont Saint-Michel (Normandy, France). The reef is composed of the sea-worm Sabellaria alveolata and thus, is one of the northernmost biological reefs in the world. To map Les Hermelles in the fi eld is diffi cult because of its great distance from the coastline and its brief exposure to the air. Consequently, the last map dates back to 1980. In 1984, mussel farms were developed around the reef. Since then, they are often regarded as the factor responsible for the perceived decline of the reef. The main goal of the study was to assess the possibility of mapping Les Hermelles using satellite imagery and if so, to give a rough idea about its recent evolution since the 1980 map. A multi-spectral SPOT image satellite was used for the tests. Areas of reef, sand, silt, mud and sea-water show similar spectral signatures. Moreover, these environments are often mixed within a single pixel. Consequently visual interpretation and the usual classifi cation approaches failed, showing interclass confusion. A new classification based on cellular automata appears to be promising. Applied to the example of Les Hermelles, this method was successful and showed a certain stability of the reef dynamic tendencies since 1980. Although the preliminary results have to be securely based on field data acquired close to the satellite-image date, they already confi rm the key role that sandbars play in the reef dynamics whereas the role of the mussel farms remains unclear if not null. The classification by cellular automata presents the advantage that no supervision is required, and that spectral and geographical information are both used together.

Introduction

The epicontinental shelves such as the English Channel show exceptional tidal amplitudes, often exceeding 10 m. The presence of the Cotentin peninsula (Normandy, France) increases the tidal amplitude within the Bay of Mont Saint-Michel, where the tidal range is particularly high, up to 15 m (Fig. 1). A reef of the sea worm Sabellaria alveolata, known as ''Les Hermelles'', occurs in the central part of the bay within the mediotidal zone (i.e. it does not emerges at every low tide.) Les Hermelles reef emerges at low tide only if the tide coefficient is greater than 70. The reef is one of the northernmost biological reefs in the world. To map it in the field is difficult because the period of exposure to air is short and it is far from the coastline (from 3 km to its closest part up to 5.5 km.) Consequently the last map that was made in the field dates back to 1980 [START_REF] Legendre | Application des donn! ees multispectrales spot " a la cartographie des s! ediments de la baie du Mont Saint-Michel (Bretagne et Normandie, France)[END_REF]. In 1984, mussel farms were developed around the reef. Since the reef is highly sensitive to the sea current and the sedimentary conditions, mussel farms are often suspected to be the factor responsible for the perceived decline of the reef. Considering the difficulty and highcost of field mapping, the main objective of this study was to assess the feasibility of mapping Les Hermelles using satellite imagery, and to give a general idea about its recent evolution. This paper presents the application of an original classification method using SPOT satellite data and the first results for the general reef evolution since the 1980 map.

Les Hermelles

Sabellaria alveolata is a polychaete annelid which is 2-5 cm long, sedentary (living in a cemented tube) and gregarious (from 15,000 to 60,000 worms/m 2 ). This, worm species catches food and mineral microparticules in the turbid sea-water using filaments in its mouth. Thus, its mouth plays a sorting role, rejecting some particles, conveying others whether as food or as material to build the living tube. The constructor organ cements the received sand grains with a phosphorous, calcium, magnesium and manganese compound, and places this material on the top of the living tube that increases in height [START_REF] Gruet | Recherches sur l'! ecologie des ''r! ecifs[END_REF][START_REF] Wilson | Sabellaria colonies at Duckpool, North Cornwall[END_REF].

The Sabellaria alveolata lives for 4-5 years and its sexual reproduction occurs from the end of its first year until its death. The development of the planktonic larvae lasts for 1.5-3 months before turning into worms. Many of them die during this period, or shortly after, if they do not find a suitable location to inhabit. The larvae loss is balanced by reproduction throughout the year and the large number of oocytes generated by each worm, around 350,000 per year. The new population needs a rigid substratum in which to settle, for example, rocks, pebbles, shells or ideally, an already established Sabellaria alveolata settlement.

Therefore, a Sabellaria alveolata reef may increase in mass, or decrease if recruitment to the worm population is reduced for a few years. Reef development is vertical as well as horizontal by concretion. The latter situation can also occur when a block of the reef falls apart and moves away where it becomes a new reef unit on which the new worm generation can settle. The tidal stream primarily controls a Sabellaria alveolata reef orientation. The more bi-directional the water mass flows, the more likely the reef is to be elongated in a mass flow perpendicular orientation. In the same way, the less bidirectional the water mass flow, the more round is the shape of the reef.

Les Hermelles on the low central tidal flat of the Bay of Mont Saint-Michel is a Sabellaria alveolata reef that appeared during the 18th century on an oyster shell accumulation in the ancient river bed of the Couesnon that changed its route around 1780 [START_REF] Larsonneur | La baie du mont Saint-Michel: un mod" ele de s! edimentation en zone temp! er! ee[END_REF]. Nowadays, the reef is not continuous but it spreads in 1 m high ''shrubs'' orientated NNE-SSW perpendicular to the currents, over 90 ha (Figs. 1 and2). The zones free of this worm within the reef boundary are inhabited by many animal species including the barnacle Balanus crenatus, the mussel Mytilus edulis, and crabs Macropipus puber, Carcinus maenas and Porcellana platycheles. On French marine maps, the reef bottom lies from about 2.50 m at the northeastern part to 4.50 m towards the southwest. Thus, as the Sabellaria alveolata shrubs are 1 m tall, the reef top lies at 3.50-5.50 m.

The turbidity of the Bay of Mont Saint-Michel is high, from 10 to 50 mg/l at high tide, and the reef acts as a huge water filter and breakwater [START_REF] Caline | Les r! ecifs " a Ann! elides (hermelles) en baie du mont Saint-Michel-! ecologie g! eomorphologie s! edimentologie implications g! eologiques[END_REF]. It is associated with a bank of shell sand called ''La Grande Bosse'' which grows in sheltered positions behind the reef. La Grande Bosse has its own dynamics it appears on the western part of the reef, increases and moves eastward and coastward. Finally, it splits from the reef and moves coastward, while another shell bar appears on the western part of the reef.

The evolution of ''Les Hermelles'' has been studied from 1947 to 1980 by aerial photography and by topographic fieldwork [START_REF] Legendre | Application des donn! ees multispectrales spot " a la cartographie des s! ediments de la baie du Mont Saint-Michel (Bretagne et Normandie, France)[END_REF][START_REF] Le Rhun | ! Etude physique de la baie du Mont Saint-Michel[END_REF][START_REF] Caline | Les r! ecifs " a Ann! elides (hermelles) en baie du mont Saint-Michel-! ecologie g! eomorphologie s! edimentologie implications g! eologiques[END_REF]. From 1947 to 1980, the eastern units were the most stable while the western ones were unstable. This was probably due to wandering channels responsible for general instability. Meanwhile, the central parts had extended to become contiguous and formed two units. Important mussel farms were developed around the reef over this period but especially later, in 1984, when huge mussel beds appeared on the reef's north side. Mussels are also filter feeders and so could compete against Salbellaria alveolata. Moreover, those installations slow down the currents and are often considered as the cause of mud deposition.

Since 1980 the reef has not been mapped and thus, its evolution has not been assessed since that time. However, the local population perceives a decline of the reef and looks at mussel farms as the factor responsible for this decline. The study brings into focus the hypothesis that the tendencies described for 1947-1980 are still going on, or the alternative hypothesis that the tendencies have changed since 1980 especially considering the presence of mussel beds.

Methods

Satellite scenes cover several thousands of square kilometres and their geometric distortions can be easily corrected. The HRV-XS sensor of the SPOT-3 satellite operates in three different spectral bands: Green (XS1 [0.50; 0.59] mm), Red (XS2 [0.61; 0.68] mm) and nearinfrared (XS3 [0.79; 0.89] mm). The spatial resolution of this sensor is 20 m  20 m and so, it is adequate for a general cartographic approach. Although, the same satellite in panchromatic mode (HRV-P) provides better spatial resolution (10 m  10 m) with just one single band ([0.51; 0.73] mm), such an image was not available. We used here a SPOT HRV-XS image recorded on 15 January 1995, 37 min before low tide while the tide coefficient was 70. Thus, the sea limit occurred at about 4 m deep (Fig. 1). Fig. 3 shows Les Hermelles extracted from the whole raw satellite data in visible (XS1) and near-infrared (XS3). Unfortunately, on the picture the sea still hides the deepest parts of the reef. For instance, unit D remains completely immersed. However, the shell sand ''La Grande Bosse'' and most of the reef units are readily visible. This handicap reveals the first great difficulty in Normandy that is to get altogether at the same time, high tide coefficient, low tide, cloud-free sky and satellite pass time. This satellite image was still the best we could use and therefore was selected to test the new mapping approach.

The choice of visual interpretation was rejected because although the emerged reef is readily visible on the SPOT picture, its boundaries are not obvious to delimit and this approach is subjective. Some popular classification methods, either unsupervised ones such as clustering algorithms, or supervised ones such as the maximum likelihood algorithm, were applied. These methods that are based on spectral signatures, led to significant confusion between the biological reef, sand, silt, mud and turbid water classes. Confusion occurs because the spectral signatures of these landscape elements are similar to one another, and because the classes are never pure: some silt always covers the reef, sea-water has a high sediment content and, mud and silt on the tidal flat remain soaked. In addition, considering the pixel size (20 m  20 m), a pixel may include the turbid sea-water, the wet sediment and patches of reef, and so be a mixed pixel [START_REF] Marchand | Cartographies s! edimentologiques et morphologiques par t! el! ed! etection de la baie du Mont Saint-Michel (ouest de la France)-Comparaison de capteurs et de m! ethodes de segmentation d'images[END_REF]Lhomer and Minoux, 1987). Thus, in this application spectral signatures are not enough for satisfactory classification.

Instead, we used a genetic algorithm, based on Artificial Life concepts for this purpose (Cazoulat and Victorri, 1994a;[START_REF] Cazoulat | Mod! elisation et simulation de la dynamique de population d'agents[END_REF][START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]. This approach allows the SPOT data to be analysed in both spectral and topological terms. The consideration of a spatial neighbourhood conceptually maintains continuity of structure in the form of edge and contiguity [START_REF] Walsworth | Image modelling of forest changes associated with acid mine drainage[END_REF]. The main advantage of the method is that neither spectral nor spatial supervision nor the number of the final categories, are required. The method is based on cellular automata, agents that will progressively spread over their ''land'', which is the satellite image itself. They classify the SPOT HRV-XS image, as they will create their own social system with different agent groups having their own integrity. Each agent group composes a final class, or region, on the classification result.

An agent is an autonomous entity that possesses a certain perception of its environment via an internal structure. The agent structure includes an internal state, sensors, effectors and an adaptation mechanism (Fig. 4). The sensors inform the agent about the environment. Meanwhile, the effectors act by reproduction, death, or moving. The adaptation mechanism links the perception from the first ones and the possible actions of the latter in a sensory motor loop. The agent organisation binds its structure and its environment by rules that lead to the emergence of the dynamics and social system [START_REF] Axerold | The evolution of cooperation[END_REF]Cazoulat and Victorri, 1994b).

The algorithm presents three phases: initialisation, expansion and erosion. For initialisation, the user puts the first agent (germ) anywhere on the land. All the agents will be descended from this germ and will receive the same internal structure including a region number and a reference value. The region number identifies the agent group. At this first step, the germ's region number is initialised with the number 1. The reference value is a digital number (DN) of the SPOT-XS pixel and its possible range is from 0 to 255. The germ's reference value is initialised with the current value of the pixel where it is put.

During the expansion phase, each agent, starting from the germ, regularly chooses at random one of its eight neighbour pixels. If this pixel is not yet inhabited, the agent duplicates itself on it. The new agent is either a clone or a mutant. A clone inherits its region number and reference value from its parent. A mutant is initialised as a germ for a new group. Therefore, it receives a new region number and its reference value is initialised with the DN of its current pixel on which it occurs within the SPOT image. At the end of this expansion step, the landscape is filled up with agents (Fig. 5a).

When just alive, the first action of the new agent is to calculate an Euclidean distance between its reference value and the DN of its current pixel on which it appears. Of course, this distance would be drawn for a mutant considering its initialisation. The distance is then compared to a threshold that is a tolerance. Unless the distance is smaller than this threshold, the new agent will die. Thus, this threshold defines the living domain of the agent. The user sets it through the graphic interface at the beginning of the process, but it can be changed during processing.

At the outset each agent region is a class that is geographically and spectrally constrained, like it would be if the conventional region-growing method were used. The region-growing method is offered as a tool in some software (e.g. Erdas Imagine): from one pixel selected by the user, the region grows incorporating those neighbouring pixels that are spectrally similar. Both methods present the great advantage of considering the geographical and spectral aspects within the classification process, in contrast to other supervised and unsupervised classification methods that are based only on spectral dimension (e.g. clustering, maximum likelihood methods). A major argument in support of the agent classification approach compared with the region-growing one is that it is able to build more than one region from the starting point. The other regions appear through the mutation process. The mutation rate as the threshold defining the agents' domain of life, is given at the beginning of the process but can be changed during processing. The mutation process introduces diversity without knowing a prior the number of classes or the class distributions over the SPOT image. This is probably the main argument in support of the method. The disadvantage of the method is, however, that some useless regions may be created, even when the picture is uniform (Fig. 5a).

The erosion phase arises at the last step, when agents have filled the SPOT image. It aims to erase small and useless regions. It should also be noted that the agent's internal structure includes a group cohesion variable. This component of the agent considers the size of the group and the fraction of the eight neighbours that belong to the same group. The bigger the region, the greater is the agent's group cohesion. Also, the more neighbours belong to the same group, the better is the agent's group cohesion. Thus, considering a group of agents occupying a region cohesion is highest at the centre of the region and lowest at the boundaries.

Iteratively, each agent repeatedly chooses at random one of its eight neighbour pixels and tries to duplicate itself, this continues until no pixel is free anymore. If an agent of the same group already occupies the chosen pixel then, the attempt to duplicate is over. Otherwise, a fight starts between the agent that tries to duplicate itself, (the attacker) and the agent of a different group that occupies the chosen pixel. Thus, the regions' boundaries are not only where the group cohesion values are the lowest, but they are also the conflict zones. An Euclidean distance is calculated for both agents, between their reference value and the chosen pixel DN. However, the inverse of each agent's group cohesion value weights this distance. Thus, high values of group cohesion reduce the effective distance, and the smaller it is the better. If the attacker does not have the smallest distance, it dies. Otherwise, the attacked agent dies and the attacker duplicates itself putting on the pixel either a clone or mutant. An important aspect of creating a clone is to increase the cohesion value of every single agent of the group and thus, the cohesion of the whole group. This weighting implies a social benefit of being in a group. The individual entities of the group get more powerful as the group cohesion increases and vice versa. Thus, the erosion phase tends to eliminate small regions unless they have a well-identified spectral signature (Fig. 5b). Meanwhile, the biggest regions increase in size up to the point at which this is no longer possible, considering the difference between their spectral signature and the DN of the surrounding pixels. Then, the number and the spatial distribution of the regions become stable improving the stability of the whole system during this erosion phase [START_REF] Dawkins | Good Strategy or Evolutionarily Stable Strategy, Sociobologie: Beyond nature/nurture[END_REF][START_REF] Lindgren | Cooperation and community structure in artificial ecosystems[END_REF][START_REF] Nowak | Evolutionary and spatial dynamics of the prisonner's dilemma-from simple rules to global complexity[END_REF]. Finally, the classification is complete when the classification is stable, and less than 5% of pixels change from one agent group to another in one iteration. Those changing pixels are located at the region boundaries where the group cohesion values are the poorest and the fights continue.

The classification is displayed in real time on a user interface termed the platform (Fig. 6). This platform was created first to visualise experimentations and simulations that were conducted about population evolution [START_REF] Bura | La norme PLAGES (PLAteforme G! en! erique d'Exp-! erimentations et de Simulations)[END_REF][START_REF] Cazoulat | Mod! elisation et simulation de la dynamique de population d'agents[END_REF]. This user interface is a control panel used for general purposes such as running or stopping the process, saving the result and changing some global parameters (number of channels used, tolerance threshold, mutation rate), and also for monitoring the internal structure of an agent. Only band XS1 was used although a multispectral classification is possible. Bands XS1 and XS2 show an important correlation (r > 0.75) and the high water absorption in the near infrared spectra induces no improvement by using band XS3 (Fig. 3). The classification of XS1 was conducted through the user interface in three steps. First, the mutation probability and the tolerance threshold were set respectively at 0 0 / 00 and 100 0 / 00 . This step led to only one agent group covering the wholeimage and resulted in its average spectral value. Second, the mutation probability was set at 1 0 / 00 while the tolerance was brought down to 3. During this step, many agents of the first and unique group died because their reference value was too far from the DN of their current pixel. Simultaneously, new agent groups had emerged. Third, the mutation probability remained at 1 0 / 00 while the tolerance was raised to 10. This step was the shortest and had no other goal than to fill the conflict zones prior to saving the result in a file.

The interpretation of the different regions in the result is similar to that of an unsupervised classification (e.g. clustering). The user bases his interpretation of the newly classified SPOT HRV-XS image, on his field knowledge, the spectral signature of the agent groups and their spatial distribution. As sand influences reef development, the two groups ''Sabellaria alveolata'' and ''Sand'' were both retained for the final representation (Fig. 7).

Initial results concerning the reef dynamic

A qualitative comparison between the 1980 map and the cellular automata classification of SPOT-XS1 image of 1995 leads to some comments about the reef dynamics (Fig. 8). At this stage, the differences between the two superimposed maps are assumed to be related to mostly either the sea-water mask on the deeper parts of the reef, or the evolution of the reef that is closely connected with the sand bars. However, the results are preliminary, giving only general tendencies for the different units of the reef. Unit A was described in 1980 as previously exposed to some anthropogenic degradation as it was a fishing zone [START_REF] Legendre | Application des donn! ees multispectrales spot " a la cartographie des s! ediments de la baie du Mont Saint-Michel (Bretagne et Normandie, France)[END_REF]. Between 1980 and 1995, unit A showed recovery and even expansion mainly along its north side. Meanwhile, the attached sand bars along its south side had moved towards the coastline. Unit B is the oldest part of the reef and occurs at the highest position on the tidal flat (+4.50 m). The sedimentation process has consequently filled-up the bay of Mont Saint-Michel, so this present high position implies a long daily exposed period for the worm Sabellaria alveolata. The shape of this map unit was described in 1980 as having deteriorated, with scattered and damaged Sabellaria alveolata shrubs. The initial results of the SPOT classification show firstly that the whole unit B continued to decline. Secondly, parcel B 3 that had likely fallen off, continued to be carried along by the currents towards the upper flat. This patch may disappear in future because of a long exposure to air. Unit C was not in good conditions in 1980: C 1 was sanded up in its central part and C 2 was just recovering from a mussel invasion. During the 1980-1995 period, the shell sand bar La Grande Bosse progressed from west to east, towards unit F and its extremity split and moved south, towards the coastline. Meanwhile a new shell sand bar was growing behind the southwestern part of unit C 1 . This evolution of La Grande Bosse is well known and has often been described [START_REF] Larsonneur | La baie du mont Saint-Michel: un mod" ele de s! edimentation en zone temp! er! ee[END_REF][START_REF] Legendre | Application des donn! ees multispectrales spot " a la cartographie des s! ediments de la baie du Mont Saint-Michel (Bretagne et Normandie, France)[END_REF]. Consequently, the unit expanded where it became free of sand and regressed where the new shell sand accumulation occurred (Fig. 8). Unit C balance seems positive taking into account that an assessment would be underestimated due to the fact that the sea covered at least the northern part of unit C 2 . Unit E decreased considerably due to complete sinking into the sand of unit E 2 although, the area of E 1 is likely underestimated due to the presence of the sea. Unit D as well as the more distant units G and H, could not be mapped as they were in the sea-water column at the time when the SPOT satellite recorded the data. Therefore, the corresponding pixels of the satellite image were associated with a sea region in the agent classification results. Unit F is a remarkably perfect and large tabular piece of Sabellaria alveolata, which is seldom observed. It was described in 1980 as the most stable part of the reef since 1947. Unfortunately, its northern fringe was immersed during the the SPOT-image acquisition in 1995. The map of the emerged part reveals again its good stability in 1995, and even an increase at its SW extremity.

Method discussion and conclusion

With respect to classification accuracy, [START_REF] Mumby | Coral reef habitat-mapping: how much detail can remote sensing provide?[END_REF] questioned ''ywhether an accuracy of (say) 40% is worthwhile when the alternative is no mapped information at all?'' The key issue of method assessment arises from this remark. Overall accuracy corresponds to ''the sum of correctly labelled test sites divided by the total number of test sites'' [START_REF] Green | Remote sensing techniques for mangrove mapping[END_REF]. Thus, in order to assess the accuracy of a Satellite image method, field data collected as close as possible to the satelliteacquisition day are needed.

In our study, the accuracy could not be assessed because of the lack of field data close to the date of SPOT image-acquisition, and thus it is more a qualitative evaluation of the results based on field knowledge, the 1980 map and old air photographs. There is no significant difference in spectral signatures between reef and sediment or sea as there often is between vegetation and water within mangrove, for example. Visual interpretation was tried by the author and it interpretation failed at the first attempt. The spectral-based classifications show such great confusion between the different expected classes in our study that no qualitative comparison with the 1980 map was possible. The cellular automata method has shown some promise and may outperform spectral-based clustering; at least it allowed a qualitative comparison. An advantage of the cellular automata method is that no spectral or geographic supervision is required.

Finally, the aim of this study was to assess the feasibility of mapping Les Hermelles using SPOT satellite data and to evaluate, its recent evolution since the 1980 map. At this stage, the cellular automata method was successful and appears to be a promising exploration. Unfortunately, some parts of the reef were under water at the image-acquisition time and therefore could not be mapped. However, the cellular automata method showed a stability of the reef dynamic tendencies since 1980, especially that its evolution remains linked with La Grande Bosse sand bar dynamics. The mussel farms developed on the north side of the reef in 1984 seemed not to modify the reef horizontal dynamics.

Fig. 1 .

 1 Fig. 1. Bay of Mont Saint-Michel as seen 15th January 1995.

Fig. 2 .

 2 Fig. 2. Hermelles reef.

Fig. 3 .

 3 Fig. 3. Hermelles reef from SPOT raw data.

Fig. 5 .

 5 Fig. 5. Result of expansion phase (A) and erosion phase (B).

Fig. 6 .

 6 Fig. 6. User interface simulation platform.

Fig. 7 .

 7 Fig. 7. Result of agent population classification.


Jérôme Bourdon

Cécile Méadel

Keywords: administrative research, France, audience measurement, ratings, television

Based on empirical research in France, this article proposes a sociological analysis of television audience measurement (TAM), an operation in which people from various backgrounds (statisticians, engineers, marketing experts) coexist to produce numerical representations of television audiences. These are a major, basic "currency" in the television industry and, more broadly speaking, in television culture. This analysis departs from prevalent conceptions of ratings as either "scientific" and therefore faithful representations of audience preferences, or, from a critical perspective, as apparatuses of surveillance and domestication. Focusing on the technology of peoplemeters, it analyzes ratings as the product of a highly complex socio-technical network, which produces robust representations of the audience, accepted by a wide range of social actors.

There have been some more sophisticated approaches to ratings. [START_REF] Smythe | Communications: Blindspot of Western Marxism[END_REF]Smythe ( , 1981) ) adopted a neo-Marxist approach to analyzed the part played by the "commodity audience" (measured by ratings) in the political economy of the media, inviting his colleagues to pay less attention to media text, for him a "free lunch" meant to attract audiences to the media in order to sell them to advertisers. This has triggered what is been known as the "blind spot" debate. However, like Smythe himself, most authors ultimately assumed that audiences are accurately "represented" by ratings, at least from a quantitative point of view. [START_REF] Meehan | Gendering the Commodity Audience: Critical Media Research, Feminism, and Political Economy[END_REF] has engaged the question of representation, which will be central to this paper -looking at the way in which and the reasons why the ratings industry selects and prioritizes certain categories of viewers against others. Outside this debate, [START_REF] Ang | Desperately Seeking the Audience[END_REF] has produced the main piece of work about the way broadcasting organizations deal with audience representation, with much skepticism about the representative value of ratings. In the US, [START_REF] Buzzard | Chains of gold: Marketing the ratings and rating the markets[END_REF][START_REF] Buzzard | The Peoplemeter Wars: A Case Study of Technological Innovation and Diffusion in the Ratings Industry[END_REF] has analyzed the history and the economy of TAM. Miller's seminal article [START_REF] Miller | Made-to-order and Standardized Audiences: Forms of Reality in Audience Measurement[END_REF] has not inspired much research. [START_REF] Napoli | Audience Measurement and Media Policy: Audience Economics, the Diversity Principle, and the Local People Meter[END_REF] has shown the political implications of changes in measurement methods for the representation of specific sections of the audience. Quite recently [START_REF] Balnaves | Rating the Audience. The Business of Media[END_REF], in an approach similar to our own, and with an international perspective, have examined the practices and conventions by which ratings are produced.

We do not consider the technical validity of ratings or its effects on culture. We treat the quantification of audiences as a socio-technical mechanism, which produces ratings in a way that can be effective for very different actors, inside the television industry as well as outside. Ratings may no longer be a "blind spot" for researchers, but they remain a black box [START_REF] Latour | Science in Action[END_REF], i.e. a techno-social mechanism that produces things routinely agreed upon and (almost) never questioned. Opening this black box might provide us with valuable insight into contemporary culture, the way it represents its audiences, and the way legitimacy is conferred (or not) upon specific cultural artifacts, especially through quantification (Herbst, 1993: 3)

1 .
Television audience measurement already has a long history [START_REF] Beville | Audience ratings: radio, television, and cable[END_REF][START_REF] Méadel | Quantifier le public[END_REF], with a variety of technologies used for representing, and calculating, audiences (face-to-face interviews, phone surveys, diaries, experiments with "passive" measurement…). We will focus on a specific apparatus, the "push-button audimeter", or peoplemeter (PM) and on the French market, although not on French specificity. The fieldwork is based on Médiamétrie, the organization that manages television audience measurement in France including analysis of some of its archives (see below) and interviews of professional actors. We have investigated 1) the way this organization which represents conflicting interests produces a sense of neutrality and validity, 2) the conception of the viewer embedded in the peoplemeter, still the "state of the art technology" for measuring viewing, although major changes are on the way [START_REF] Napoli | Audience Evolution: New Technologies and the Transformation of Media Audiences[END_REF], and 3) the recruitment and management of actual panel members who are supposed to fit this conception of the viewer.

MANAGING TAM: THE "NEUTRAL" ORGANIZATION Audience measurements are not an ordinary product on a market where consumers can choose the best and change easily: they are the standard by which to measure the value of the "product", namely Smythe's "commodity audience". The actors on the market need a single, accepted currency. This has nothing to do with the technical quality of the measurement work per se. Two measurers using different methods of sampling and different technologies will produce different figures. There have been some situations of coexistence of different figures, but never for long in situations where commercial competition prevails (Méadel, 2010, Balnaves and[START_REF] Balnaves | Rating the Audience. The Business of Media[END_REF].

In most Western countries, the professional literature generally considers that the best solution for managing TAM is the JIC, (Joint Industry Committee) which reflects this acute need for consensus. Various partners are invited to the table: public and private broadcasters, advertisers, publicists; they form a committee which puts out to tender a contract with different research companies. It seems that the term and the method were introduced in the seventies in the UK for various media (Baker, 2000), but the JIC as an international acronym spread in the eighties and the nineties, with commercial television and the rise of PMs. A working paper by the World Federation of Advertisers ( 2001) underlined the advantages of JICs over other methods such as purely commercial operations or "inhouse" ratings, arguing that the JIC model provides "good value for money" since all users share the costs, and that it is "the most reliable form of research since it has the largest number of interested parties who examine the technical procedure" (2001: 5). The WFA is willing to accept the relatively slow and cumbersome character of the JIC model, as it claimed that "reliability" has to come first. However, JIC is by no means the only model, and there are many ways to produce audience figures. In each national situation, the partners have to find their own way of insuring credibility and neutralizing "particular interests" (Syfret, 2001: 57).

When going in the market to find contractors, JICs need to strike a delicate balance: competition is scarce as investment costs are very high and the chances of profit not immediate, yet JICs are wary of monopolies. Since the eighties, the trend has been towards increased concentration and internationalization, and "it has been more difficult to find contractors for television audience measurement" (former scientific director, Médiamétrie). Today, there are three major international players in the field of TAM: AGB-Nielsen (a joint venture created in 2004 between former competitors), TNS (Taylor Nelson Sofres), and GfK Telecontrol.

In France, the situation seems to be entirely original: the subcontractor and the JIC are integrated in a single commercial company, Médiamétrie. This is a rather unusual company, enjoying a double monopoly, for both organizing and directly managing TAM. Therefore, the company has to work very hard at ensuring and maintaining its professional credibility. Born in 1985 from a public organization working for public television stations, Médiamétrie manages the panel, specifies the way PMs are built, and orders them from the manufacturers. While a JIC has few permanent employees, Médiamétrie has a whole building with five hundred employees and had a turnover of €58m in 2008. Its shareholders include major market players (TV, radio and advertisers). Médiamétrie does not call for tenders, which JICs do at least every few years. How can clients be sure that the measures are produced in a professional, "neutral" manner? The answer the company provides is threefold, based on science, control and consensus.

First, Médiamétrie presents itself as more of a Research and Development company than a commercial one, with much staff coming from schools of statistics and engineering, and a department of "analyses and scientific methods" (with a staff of 20), and another for "development of measurement systems" which, as several of our interviewees proudly emphasized, employs 15 people, mostly engineers. Second, like other audience measurement organizations, the organization stresses that it is tightly controlled, both for its technical work and for its management. Most of our interviewees, starting with the PR officer, emphasized the high number of controls, conducted by various audit firms. Some appeared at the birth of Médiamétrie, and are still active today, e.g. the CESP (Center for the Study of Advertising Media), a non-profit organization founded in 1964 by the advertising industries to carry out surveys, which regularly audits Médiamétrie (after having been its rival for a while). "It can go very far, they can follow our field agents, and they might decide to focus on a specific point like the problem of statistical weighting" (PR officer, Médiamétrie).

Third, and of particular importance, the organization emphasizes the role of consensus through "the partners' direct participation in making major decisions" (DG, Médiamétrie). Advertisers, agencies and broadcasters meet in the relevant committees (for television the "audimetric committee" whose minutes we have analyzed) and are actively involved in decision-making regarding the structure of the panel and the specifications of the PMs. Some information, however, has to be kept secret (see below). The chairman of the company technically has the right to vote but, in order to demonstrate his/her neutrality, never uses it and manages the committee so as to reach consensus.

To a large extent, this made our work difficult, as the minutes tend to exclude conflicts, which have been largely dealt with in advance. But we know of major crises, when consensus stopped working for a while and major efforts were needed to mend the situation. This sometimes happens when an unhappy TAM partner goes to the press to denounce some part of the (alleged) black box which, for a short while, will be considered as "biased", "malfunctioning", "defective". The unhappy partner tries to show that the "neutral" arbiter is "in fact" not the spokesperson of the public for the general good, but the hidden representative of one of the partners. This happened in 1987 when Médiamétrie CEO communicated some confidential information to persuade a new commercial channel of the validity of the sampling. Another broadcaster heard about it and went to the press (interview with a former head of research; see also [START_REF] Bourdon | Alone in a Desert of 50 Millions Viewers: Audience Ratings on French Television[END_REF]. The crisis was short lived, Médiamétrie's CEO was quick to apologize and strongly re-asserted confidentiality. The black box of TAM was closed again, and went back to the routine production of "reliable figures".

As this example shows, building consensus is not an easy task. All the partners essentially have to trust the organization in charge. They might want some criteria to be abided by for panel recruitment or renewal, but at some point, they must rely, continuously, on the technicians in the field. They are not supposed to know about the composition of the panel: confidentiality is crucial, as publicity would make distortion possible. The quality of the consensus depends on power relations within the television industry at a given moment, and on the relational skills of the who represent the mediator in charge of measurement. Although this has not relation to the technical and statistical quality of TAM, it is a crucial condition for the good functioning of the whole operation.

Is Médiamétrie, which produces television ratings, a faithful if not blind servant of the market, as opponents of ratings would have us think? This servant appears as very active, quite aware of the work it does, and engaged in intensive self-reflexive activity. Furthermore, this "market" is not just a commercial market. In France, the major public channels, which no longer broadcast advertisements in prime time are in the debates of the Médiamétrie committees. Finally, the "servant of the market" is also under surveillance in the press (at least in times of crisis), not to mention in the political world.

THE VIEWER ACCORDING TO PEOPLEMETERS: THE "NEUTRAL" MACHINE

Let us move to the technology used for television audience measurement. Médiamétrie uses a machine that is seen as the "standard technology" for measuring television audience. AGB in Italy and Telecontrol, a Swiss company with links to the national public-service broadcaster SSR and a partnership with German marketing company GfK, developed it first. In 1984, PMs were installed in the UK and Italy (by AGB). From there the peoplemeter quickly spread to Western Europe and the US [START_REF] Buzzard | The Peoplemeter Wars: A Case Study of Technological Innovation and Diffusion in the Ratings Industry[END_REF]. Médiamétrie introduced it in 1988.

The peoplemeter was first based on an audimeter (previously used in countries like France, the US and the UK). The audimeter is a setbox attached to TV sets in homes, which records, every second, if the TV is on and on what channel. The peoplemeter requires a special remote control, with a series of buttons. People have to press their own button when they watch TV (in fact not exactly "watching", as we shall see). During the night, the day's data is sent to Médiamétrie by phone line. This raw data (audience minute by minute, per channel) is then processed according to TV schedules and advertising slots. The processed data is made available to clients by 8 a.m.

The process might seem fairly straightforward. Our Médiamétrie interviewees also suggest that PMs should be recognized as a major "advance" or "progress" in the history of audience measurement. The measurement is made "in real time", and data is "processed automatically". "All they have to do is press a button. Think of when they used to have to fill in a diary a week later and try to remember, often with the assistance of someone who would naturally put pressure on them" (Director of Research, Public Television Station). PMs are also considered to be better than discontinuous methods used for other media, notably involving self-recall, which are widely claimed to artificially inflate audience sizes.

However, a number of questions have to be answered. PMs are set in homes, defined as the "main place of residence". This could be considered as a regression compared to phone surveys, which asked if specific individuals watched TV, regardless of place. Collective viewing in bars, cafes, camping sites, etc. is now overlooked. Frequent in the early days of television, it is still practiced "notably for major sports events in cafes, but this is out of the reach of peoplemeters" (Scientific Director, Médiamétrie). However, our interviewees saw vacation homes or, more precisely, "secondary residences" (used in France for vacations and week-ends) as more problematic. "10% of families have a secondary residence, and they spend on the average one week-end out of six there" (Scientific Director, Médiamétrie). The question of cost has been a major obstacle here. In the US, a group of broadcasters who reviewed the PM in 1989, in the days of its inception, suggested "measuring all sets including those on boats and in vacation homes" [START_REF] Gross | Ratings[END_REF](Gross, : 1348)), but to no avail.

Moreover, the PM measures viewing "in the room where the set is located" or, as one should qualify, "are" located: 50% of French households are equipped with more than one TV set in 2008 (Médiamétrie, 2009). This system neutralizes and naturalizes the notion of a "room". What about very big rooms? What about moving in and out of the room at short intervals? Do cleaners have to press the button (there are two buttons for visitors, yet cleaners are not considered as visitors by Médiamétrie)? What about weak separations within the same room (bookshelves in the center, folding screens)? One might say that these are "marginal situations", as one of our interviewees stressed. Yet together they raise interesting questions about what is actually being measured, and what is considered as both the statistical and social norm.

Let us accept that "being in a room" is a situation clear enough. A viewer is someone who lives in a home where someone (not necessarily the viewer him/herself) has decided to turn on the TV -unlike the viewer in a bar. This implies a level of "collective intentionality", however weak. You might have to press the button simply because someone else has decided to watch television. Imagine a home where there is only one set and where the head of the household wants to watch the news. Some people in the room are not happy about this, but are told to remain silent. Is pressing the button about indicating voluntary presence as acknowledging submission? This example makes the point clear: television watching is related to the "politics of the home" [START_REF] Morley | Family television. Cultural Power and Domestic Leisure[END_REF].

Without discussing power relations between family members, one could have started with the question of age. "Pushing a button" pre-supposes a subject able to decide to do so. From what age can this be performed? How is this decision justified? When asked, some of our Médiamétrie interviewees gave different answers: the age when one knows when to press (cognitive ability), the age when one can influence consumption and choose products (commercial influence), the reasonable age according to the different partners (social ability), etc. In the end, the age appears more as a result of set agreement between partners than justified by sociological and psychological considerations. The age varies, first, between the surveys for different media, which makes things complicated as Médiamétrie is now trying to combine them: "We have six media with six different viewer ages" (Scientific Director, Médiamétrie). With the rise of multichannel TV, the tendency has been to bring the age down for PM users. When the PM was introduced in 1988, the age was brought down from 12 years to six. However, a personal button from the age of 2 was included then and still is (which an adult is supposed to press for the child). Later, the age for autonomous decision was brought down to 4. And the age varies between countries. The extreme case is Australia, where the system even takes into account the presence of newborns… In short, television viewership according to the PM machine is located somewhere between pure intentionality (the viewer decides to watch, sits in front of the set for watching), and pure exposure (the viewer -person? baby? -happens to be in a room where a TV set is on). This is justified on the basis of simplicity: "People enter the living-room and the TV is on. They know they have to press the button; they don't have to ask themselves if they are watching television. In practice, it amounts to much the same thing…" (Former Scientific Director, Médiamétrie). This decision has many consequences. In the past, in studies by phone or using diaries, people were asked if they had "watched" or "were watching" television. This is no longer the case. Finally, the system measures a certain kind of relation to television, which is wholly congruent with the evolution of the public discourse on television (including the academic one). As access to television spread, multi-channel television and zapping supposedly made it more of a "background" medium with very different levels of attention (unlike the television of the early days). It could also be considered as a medium appealing to all ages (including infants). This change in the dominant conception was duly recorded in conventions on the use of PMs. It might be said that the PM has had a performative effect: both PM users and television professionals have come to consider it as enough for television viewers to agree to being exposed to a program (not to actively seek it), to qualify as viewers. It might thus have contributed to the new dominant view of the medium, based on weak, tangential relations, not on strong links.

THE "NEUTRALLY OBSERVED" SUBJECT: THE HARD WORK OF PANEL MEMBERS

In order to make sure the "viewer in the machine" has some relation to the real world, the viewer needs to be trained to behave in accordance with the prescriptions of the machine makers. As we will see the "real panel member" is as elusive as the "viewer in the machine", but for different reasons. First, they need to be recruited. Despite the transparency which measurers aim for, being a panel member has many implications. Panel members must accept the presence of an extra box with wires at home: "This is not trivial in a world where people have to manage a whole bunch of wires behind the set" (Mediamétrie Deputy DG); they have to get into a new habit which they will perform several times every day, several hundred (or even thousand) times in their lives. They must press for themselves as well as for little children, remind the guests (who have their own buttons) to press, answer the phone every now and then, and, once a year, be visited for a full control interview (to check for major changes in household composition, etc.).

It takes "three weeks of practice" to ensure the work is done properly. The word "training" is not used as it does not fit the idea of "neutrality", but it is appropriate. In addition, there are recall systems to remind panel members of what should be done: the machine beeps softly if nobody has pressed a button and the TV is on. When someone turns on the TV, a caption shows up on a small screen on the box asking for identification. When introducing the system, Médiamétrie used a variety of systems to check for validity, especially to assess the risk of people forgetting to press the buttons on their way in and out of the room: "We called people several times… We controlled what was happening abroad, in Italy where they had started earlier and in the UK, and received positive reports /…/. On the whole, there is a balance between people who forget to declare their presence, or to declare their absence: 2.5% of the panel in each case. Since then, Médiamétrie has kept on doing coincidental surveys of this kind" (former Scientific Director, Médiamétrie).

In the US, people are paid for being part of the panel [START_REF] Buzzard | Chains of gold: Marketing the ratings and rating the markets[END_REF]. In France, the approach is different: "This is not a commercial transaction; people should do it on a voluntary basis. If they get money, it might affect their behavior. The motivation is cultural, people have a feeling that they give their voice, that they are part of a democratic process" (former Executive Director, Médiamétrie). Yet the democratic process presents a paradox: the viewer-citizens are not supposed to express a specific opinion but to represent others by behaving as usual, as if they did not have a PM.

Here there is a delicate balance to be struck. Our interlocutors want some level of conscience, but not too much. "If they feel they have some power, if they involve themselves too much and think they can affect scheduling, it's a disaster. We have asked television channels not to refer to ratings in their campaigns, for fear it might influence panelists" (Executive Director, Médiamétrie). "Ideally, they should forget about the presence of the PM: the less they think about it, the less bias there will be, but they must remember enough, so that pressing the button becomes automatic" (Deputy DG, Médiamétrie). Do people easily agree? On this point it is difficult to enter the black box. Our interviewees from Médiamétrie give an acceptance rate of about 50%, but one expert at the CESP suggested 30%. We were not able to find out how these (rather high) figures are calculated: how many refuse when first contacted by phone? After an attempt to persuade them? No one seems able to define the exact composition of the population of "refusers". Our interviewees accept the idea that highly educated people are most likely to refuse. However, they add that people with the same characteristics are eventually recruited, and that this therefore "should not" affect representation. But in order to be sure of this, one would have to know what exactly characterizes people who refuse… There is another problem raised by methods of continuous measurement requiring the subjects' participation, "button-pushing fatigue" (as it was called in a broadcasters' 1989 Survey in the US, [START_REF] Gross | Ratings[END_REF]Gross, : 1348)). According to the Médiamétrie deputy DG, "there are two schools of thought here. The first one claims that people will get weary and stop reporting. The second says the opposite: in the beginning, it takes time to get used to it, but then it becomes a reflex, like turning the light on and off". This highlights a divergence in the way the role of panel members are defined, either as passive witnesses who are somewhat alien to their own practices, or as actors at the heart of the measure itself, whose substantial work is needed to ensure the proper functioning of the instrument. Economic concerns also played a part here: renewing the panel is costly, and it "might be tempting" to keep the same members "on board" for a long time. But this time the scientific approach is on the cost side: on the whole, scientists at the institute wish to show that quality lies with the "old" panelists, as opposed to the advocates of renewal who, based on common sense, say that people grow weary of this repetitive task and should be replaced by new," fresher" members.

CONCLUSION

Both critiques of ratings and its professional promoters would agree on the fact that the production of ratings is mostly a "technical question", and that a close examination of the work of measurers would allow us to decide about the "reliability" of figures. And they would conclude that those figures are, nowadays, "more reliable" than in the past, that they "reflect" better the "reality" of viewing. A close examination of TAM shows that the technology is by no means "simply measuring something out there". A complicated set of socio-technical conventions has to be agreed upon, which can change according to relations of the partners in the industry (public/private, big/small, advertisers/broadcasters…), the different stages in television history, the technology available and developed at those different stages. The audience can never be considered independently of the instruments used to "measure" it. Does the relativity of ratings to a certain organizational construct and to certain categories of knowledge make them "less precise", "less representative", or, horresco referens, "wrong"? This cannot receive a simple answer. At best, one could write that ratings give a decent approximation of television viewing as defined at a certain time in a certain context, under certain requirements, by and for certain actors. This is not only about "margins of error" (which, it is true, are often forgotten when presenting the results of ratings, or opinion polls). It is about a more fundamental question: what is considered as "television viewing". As we have seen, this simple act needs to be heavily qualified in order to be translated into figures. In many ways, the answer to the question of the "nature of viewing" given by measurers is tautological: "television viewing according to Médiamétrie is what Médiamétrie defines as television viewing at a given moment of history".

In sum, the kind of sociological research involved here is not meant to allow a judgment of the ratings industry from within, but to take one step backwards and to understand the kind of world (and the kind of television world) we belong to: a world which cannot consider the public (the public of culture, but also of politics, see Herbst 1993 ) without figures. The need for figures is such that the machines which produce figures, at a high cost, with different kinds of expertise (technological, statistical, social), have to be relied upon, and have to be trusted in a highly routinized way. The close examination of television audience institutions gives us a rare opportunity to unravel one of the ways we construct and naturalize this ubiquitous entity: the public of television.

This research and article were made possible by a research grant of the ANR (Agence nationale de recherche).We would also like to thank Médiamétrie, which generously gave us access to its archives.


Rémi Imbach
email: imbach@mathematik.uni-kl.dewww.mathematik.uni

Victor Y Pan
email: victor.pan@lehman.cuny.edu

Chee Yap
email: yap@cs.nyu.edu

Implementation of a Near-Optimal Complex Root Clustering Algorithm

) is near-optimal when applied to the benchmark problem of isolating all complex roots of an integer polynomial. It is one 4 of the first implementations of a near-optimal algorithm for complex roots. We describe some low level techniques for speeding up the algorithm. Its performance is compared with the well-known MPSolve library and Maple.

Introduction

The problem of root finding for a polynomial f (z) is a classical problem from antiquity, but remains the subject of active research to the present [START_REF] Emiris | Algebraic algorithms[END_REF]. We consider a classic version of root finding:

Local root isolation problem: Given: a polynomial f (z) ∈ C[z], a box B 0 ⊆ C, ε > 0. Output: a set {∆ 1 , . . . , ∆ k } of pairwise-disjoint discs of radius ≤ ε, each containing a unique root of f (x) in B 0 .

It is local because we only look for roots in a locality, as specified by B 0 . The local problem is useful in applications (especially in geometric computation) where we know where to look for the roots of interest. There are several variants of this problem: in the global version, we are not given B 0 , signifying that we wish to find all the roots of f . The global version is easily reduced to the local one by specifying a B 0 that contains all roots of f . If we omit ε, it amounts to setting ε = ∞, representing the pure isolation problem.

Our main interest is a generalization of root isolation, to the lesser-studied problem of root clustering [START_REF] Hribernig | Detection and validation of clusters of polynomial zeros[END_REF][START_REF] Niu | A verified method for bounding clusters of zeros of analytic functions[END_REF][START_REF] Giusti | On location and approximation of clusters of zeros of analytic functions[END_REF]. It is convenient to introduce two definitions: for any set S ⊆ C, let Z f (S) denote the set of roots of f in S, and let # f (S) count the total multiplicity of the roots in Z f (S). Typically, S is a disc or a box. For boxes and discs, we may write kS (for any k > 0) to denote the dilation of S by factor k, keeping the same center. The following problem was introduced in [START_REF] Yap | Analytic root clustering: A complete algorithm using soft zero tests[END_REF]:

Local root clustering problem: Given: a polynomial f (z), a box B 0 ⊆ C, ε > 0. Output: a set of pairs {(∆ 1 , m 1 ), . . . , (∆ k , m k )} where -∆ i 's are pairwise-disjoint discs of radius ≤ ε, -m i = # f (∆ i ) = # f (3∆ i ) for all i, and -Z f (B 0 ) ⊆ k i=1 Z f (∆ i ).
This generalization of root isolation is necessary when we consider polynomials whose coefficients are non-algebraic (or when f (z) is an analytic function, as in [START_REF] Yap | Analytic root clustering: A complete algorithm using soft zero tests[END_REF]). The requirement that # f (∆ i ) = # f (3∆ i ) ensures that our output clusters are natural [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF]; a polynomial of degree d has at most 2d -1 natural clusters (see [START_REF] Yap | Analytic root clustering: A complete algorithm using soft zero tests[END_REF]Lemma 1]). The local root clustering algorithm for analytic functions of [START_REF] Yap | Analytic root clustering: A complete algorithm using soft zero tests[END_REF] has termination proof, but no complexity analysis. By restricting f (z) to a polymomial, Becker et al. [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on the pellet test and newton iteration[END_REF] succeeded in giving an algorithm and also its complexity analysis based on the geometry of the roots. When applied to the benchmark problem, where f (z) is an integer polynomial of degree d with L-bit coefficients, the algorithm can isolate all the roots of f (z) with bit complexity O(d 2 (L + d)). Pan [START_REF] Pan | Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding[END_REF] calls such bounds nearoptimal (at least when L ≥ d). The clustering algorithm studied in this paper comes from [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF], which in turn is based on [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on the pellet test and newton iteration[END_REF]. Previously, the Pan-Schönhage algorithm has achieved near-optimal bounds with divide-and-conquer methods [START_REF] Pan | Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding[END_REF], but [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on the pellet test and newton iteration[END_REF][START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF] was the first subdivision algorithm to achieve the near-optimal bound for complex roots. For real roots, Sagraloff-Mehlhorn [START_REF] Sagraloff | Computing real roots of real polynomials[END_REF] had earlier achieved near-optimal bound via subdivision.

Why the emphasis on "subdivision"? It is because such algorithms are implementable and quite practical (e.g., [START_REF] Rouillier | Efficient isolation of polynomial's real roots[END_REF]). Thus the near-optimal real subdivision algorithm of [START_REF] Sagraloff | Computing real roots of real polynomials[END_REF] was implemented shortly after its discovery, and reported in [START_REF] Kobel | Computing real roots of real polynomials... and now for real[END_REF] with excellent results. In contrast, all the asymptotically efficient root algorithms (not necessarily near-optimal) based on divide-and-conquer methods of the last 30 years have never been implemented; a proof-of-concept implementation of Schönhage's algorithm was reported in Gourdon's thesis [START_REF] Gourdon | Algorithmique et Géométrie des Polynomes[END_REF]). Computer algebra systems mainly rely on algorithms with a priori guarantees of correctness. But in practice, algorithms without such guarantees are widely used. For complex root isolation, one of the most highly regarded multiprecision software is MPSolve [START_REF] Bini | Design, analysis, and implementation of a multiprecision polynomial rootfinder[END_REF]. The original algorithm in MPSolve was based on Erhlich-Aberth (EA) iteration; but since 2014, a "hybrid" algorithm [START_REF] Bini | Solving secular and polynomial equations: A multiprecision algorithm[END_REF] was introduced. It is based on the secular equation, and combines ideas from EA and eigensolve [START_REF] Fortune | An iterated eigenvalue algorithm for approximating roots of univariate polynomials[END_REF]. These algorithms are inherently global solvers (they must approximate all roots of a polynomial simultaneously). Another theoretical limitation is that the global convergence of these methods is not proven.

In this paper, we give a preliminary report about Ccluster, our implementation of the root clustering algorithm from [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF]. 1 has four timings τ X (for X = , g, u, s) in seconds: τ is the time for solving the local problem over a box B 0 = [-1, 1] 2 ; τ g is the time for the global problem over the box B 0 = [-150, 150] 2 (which contains all the roots). The other two timings from MPSolve (τ u for unisolve, τ s for secsolve) will be explained later. For each instance, we also indicate the numbers of solutions (#Sols) and clusters (#Clus). When #Sols equals #Clus, we know the roots are isolated. Subdivision algorithms like ours naturally solve the local problem, but MPSolve can only solve the global problem. Table 1 shows that MPSolve remains unchallenged for the global problem. But in applications where locality can be exploited, local methods may win, as seen in the last two rows of the table. The corresponding time for Maple's fsolve is also given; fsolve is not a guaranteed algorithm and may fail.

Overview of Paper

In Section 2, we describe the experimental setup for Ccluster. Sections 3-5 describe some techniques for speeding up the basic algorithm. We conclude with Section 6.

Ccluster local (B

0 = [-1, 1] 2 ) Ccluster global (B 0 = [-150, 150] 2 ) unisolve secsolve fsolve d (#Sols:#Clus) (depth:size) τ (s) (#Sols:#Clus) (depth:size) τ g (s) τ u (s) τ s (s) τ f (

Implementation and Experiments

The main implementation of Ccluster is in C language. We have an interface for Julia 5 . We based our big number computation on the arb6 library. The arb library implements ball arithmetic for real numbers, complex numbers and polynomials with complex coefficients. Each arithmetic operation is carried out with error bounds.

Test Suite We consider 7 families of polynomials, classic ones as well as some new ones constructed to have interesting clustering or multiple root structure. Timing Running times are sequential times on a Intel(R) Core(TM) i3 CPU 530 @ 2.93GHz machine with linux. Ccluster implements the algorithm described in [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF] with differences coming from the improvements described in Sections 3-5 below. Unless explicitly specified, the value of ε for Ccluster is set to 2 -53 ; roughly speaking, it falls back to asking for 15 guaranteed decimal digits. MPSolve For external comparison, we use MPSolve. It was shown to be superior to major software such as Maple or Mathematica [START_REF] Bini | Design, analysis, and implementation of a multiprecision polynomial rootfinder[END_REF]. There are two root solvers in MPSolve: the original unisolve [START_REF] Bini | Design, analysis, and implementation of a multiprecision polynomial rootfinder[END_REF] which is based on the Ehrlich-Aberth iteration and the new hybrid algorithm called secsolve [START_REF] Bini | Solving secular and polynomial equations: A multiprecision algorithm[END_REF]. These are called with the commands mpsolve -au -Gi -oγ -j1 and mpsolve -as -Gi -oγ -j1 (respectively). -Gi means that MPSolve tries to find for each root a unique complex disc containing it, such that Newton iteration is guaranteed to converge quadratically toward the root starting from the center of the disc. -oγ means that 10 -γ is used as an escape bound, i.e., the algorithm stops when the complex disc containing the root has radius less that 10 -γ , regardless of whether it is isolating or not. Unless explicitly specified, we set γ = 16. -j1 means that the process is not parallelized. Although MPSolve does not do general local search, it has an option to search only within the unit disc. This option does not seem to lead to much improvement.

Improved Soft Pellet Test

The key predicate in [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF] is a form of Pellet test denoted T G k (∆ , k) (with implicit f (z)). This is modified in Figure 3 by adding an outer while-loop to control the number of Graeffe-Dandelin iterations. We try to get a definite decision (i.e., anything other than a unresolved) from the soft comparison for the current Graeffe iteration. This is done by increasing the precision L for approximating the coefficients of f in the innermost while-loop. Thus we have two versions of our algorithm: (V1) uses the original T G k (∆ , k) in [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF], and (V2) uses the modified form in Figure 3. Let τV1 and τV2 be timings for the 2 versions. Table 2 shows the time τV1 (in seconds) and the ratio τV1/τV2. We see that (V2) achieves a consistent 2.3 to 3-fold speed up.

In (V2), as in [START_REF] Becker | Complexity analysis of root clustering for a complex polynomial[END_REF], we use T G 0 (∆ ) (defined as T G k (∆ , 0)) to prove that a box B has no root. We propose a new version (V3) that uses T G * (∆ ) (defined as T G k (∆ , d), where d is the degree of f ) instead of T G 0 (∆ ) to achieve this goal: instead of just showing that B has no root, it upper bounds # f (B). Although counter-intuitive, this yields a substantial improvement because it led to fewer Graeffe iterations overall. The timing for (V3) is τV3, but we display only the ratio τV1/τV3 in the last column of Table 2. This ratio shows that (V3) enjoys a 3.3-7.7 fold speedup. Comparing n3 for (V2) and (V3) explains this speedup.

T G k (∆ , k) f (z) is implicit argument Output: r ∈ {-1, 0 . . . , k} ASSERT: if r ≥ 0, then # f (∆ ) = r L ← 53, d ← deg( f ), N ← 4 + log 2 (1 + log 2 (d)) , i ← 0 f ←getApproximation( f , L ) f ←TaylorShift( f , ∆ ) While i ≤ N Let f be the i-th Graeffe iteration of f r ← 0 While r ≤ k j ← IntCompare( | f | r , ∑ k =r | f | k ,2 -L ) a While j = unresolved L ← 2L f ←getApproximation( f , L ) f ←TaylorShift( f , ∆ ) Let f be i-th Graeffe iteration of f j ←IntCompare( | f | r , ∑ k =r | f | k ,2 -L ) If j = true then Return r r ← r + 1 i ← i + 1 Return -1 a IntCompare( ã, b, 2 -L ) compares L-

Filtering

A technique for speeding up the evaluation of predicates is the idea of filters (e.g., [START_REF] Brönnimann | Interval arithmetic yields efficient dynamic filters for computational geometry[END_REF]). The various Pellet tests can be viewed as a box predicate C that maps a box B ⊆ C to a value7 in {true, false}. If C -is another box predicate with property that C -(B) = false implies C(B) = false, we call C -a falsehood filter. If C -is efficient relatively to C, and "efficacious" (informally, C(B) = false is likely to yield

C -(B) = false), then it is useful to first compute C -(B). If C -(B) = false, we do not need to compute C(B). The predicate C 0 used in Ccluster is defined as follows: C 0 (B) is true if T G * (∆ B ) returns 0 (then B contains no root of f ) and is false if T G * (∆ B ) returns -1 or k > 0 (then B may contain some roots of f ). We next present the falsehood filter C - 0 (B) for C 0 . Let f ∆ denote the Taylor shift of f in ∆ , f [i] ∆ its i-th Graeffe iterate, ( f [i] ∆ ) j the j-th coefficient of f [i] ∆ , and | f [i]
∆ | j the absolute value of the j-th coefficient. Let d be the degree of f . The assertion below is a direct consequence of the classical test of Pellet (see [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on the pellet test and newton iteration[END_REF][p. 12]) and justify the correctness of our filters:

(A) if | f [N] ∆ | 0 ≤ | f [N] ∆ | 1 + | f [N] ∆ | d then T G * (∆ ) returns -1 or k > 0. Our C - 0 filter computes | f [N] ∆ | 0 , | f [N] ∆ | 1 and | f [N]
∆ | d and checks hypothesis of (A) using IntCompare. | f

[N] ∆ | 0 and | f [N] ∆ | d can respectively be computed as (| f ∆ | 0 ) 2 N and (| f ∆ | d ) 2 N . | f [N]
∆ | 1 can be computed with the following well known formula:

( f [i+1] ∆ ) k = (-1) k (( f [i] ∆ ) k ) 2 + 2 k-1 ∑ j=0 (-1) j ( f [i] ∆ ) j ( f [i] ∆ ) 2k-j (1)
Obtaining | f

[N]

∆ | 1 with eq. ( 1) requires to know 2 N-1 + 1 coefficients of f ∆ , 2 N-2 + 1 coefficients of f . In particular, it requires to compute entirely the iterations f

[i]
∆ such that 2 N-i ≤ d, and it is possible to do it more efficiently that with eq. ( 1) (for instance with the formula given in definition 2 of [START_REF] Becker | A near-optimal subdivision algorithm for complex root isolation based on the pellet test and newton iteration[END_REF]).

Our C - 0 filter takes as input a precision L, the Taylor shift f ∆ of the L bit approximation of f and its i-th Graeffe iteration f

[i] ∆ such that 2 N-i ≤ d 4 and 2 N-(i+1) > d 4 . It computes | f [N] ∆ | 0 , | f [N] ∆ | d and the 2 N-j + 1 first coefficients of f [ j]
∆ for i < j ≤ N with eq. ( 1). Then it checks the hypothesis of (A) using IntCompare, and returns false if it is verified, and true otherwise. In practice, it is implemented within the procedure implementing T G * (∆ B ). Incorporating C - 0 into Version (V3), we obtain (V4) and the speed up can be seen in Table 3. Filtering with C - 0 becomes more effective as degree grows and this is because one has 2

Escape Bound

The ε parameter is usually understood as the precision desired for roots. But we can also view it as an escape bound for multiple roots as follows: we do not refine a disc that contains a simple root, even if its radius is ≥ ε. But for clusters of size greater than one, we only stop when the radius is < ε. MPSolve has a similar option. This variant of (V4) is denoted (V4'). We see from

Conclusion

Implementing subdivision algorithms is relatively easy but achieving state-of-art performance requires much optimization and low-level development. This paper explores several such techniques. We do well compared to fsolve in Maple, but the performance of MPSolve is superior to the global version of Ccluster. But Ccluster can still shine when looking for local roots or when ε is large.

Fig. 1 .

 1 Fig. 1. Left: the connected components isolating all roots of the Bernoulli polynomial of degree 100. Right: the connected components isolating all roots of the Spiral polynomial of degree 64.

(Figure 2

 2 Figure 2 for the natural ε-clusters of NestClu (3) (z).

Fig. 2 .

 2 Fig. 2. Left: 3 clusters of NestClu (3) found with ε = 1. Right: Zoomed view of 9 clusters of NestClu (3) found with ε = 1 10 . Note: The initial box is in thick lines; the thin lines show the subdivisions tree.

  bit approximations of real numbers a and b. It returns true (resp. false) only if a > b (resp. a < b). It returns unresolved when L is too small to conclude.

Fig. 3 .

 3 Fig. 3. T G k (∆ , k). | f | i is the absolute value of the coefficient of the monomial of degree i of f , for 0 ≤ i ≤ d.

[ 2 ]

 2 ∆ , . . . , and finally3 = 2 1 + 1 coefficients of f [N-1] ∆

Table 1 .

 1 Bernoulli Polynomials with five timings: local (τ ), global (τ ), unisolve (τ ), secsolve (τ ) and Maple's fsolve(τ f ).

	s)

Table 2 .

 2 Solving within the initial box [-50, 50] 2 with ε = 2 -53 with versions (V1), (V2) and (V3) of Ccluster. n1: number of discarding tests. n2: number of discarding tests returning -1 (inconclusive). n3: total number of Graeffe iterations. τV1 (resp. τV2, τV3): sequential time for V1 (resp. V2, V3) in seconds.

  N-i ≤ d 4 for smaller i (recall that N = 4 + log 2 (1 + log 2 (d)) ).

			V3		V4
			n3 τV3	n3 τV3/τV4
		d = 64	2291 2.61 2084	1.08
	Bern d (z)	d = 128 d = 256	4496 14.5 3983 8847 94.5 7714	1.13 1.19
		d = 512	15983 620 11664 1.42
		d = 767	19804 1832 13863 1.53
		(d, a) = (64, 14)	2080 2.41 1808	1.22
	Mign d (z; a)	(d, a) = (128, 14) (d, a) = (256, 14)	3899 12.1 3257 7605 88.3 6339	1.21 1.33
		(d, a) = (512, 14)	15227 674 10405 1.57
		d = 64	2140 3.27 1958	1.05
	Wilk d (z)	d = 128 d = 256	2240 10.0 1942 2414 36.6 2108	1.09 1.21
		d = 512	2557 129 1841	1.43
		d = 64	2670 4.43 2364	1.08
	Spir d (z)	d = 128 d = 256	5090 28.8 4405 9746 182 8529	1.07 1.10
		d = 512	19159 1340 14786 1.19
		(D, d) = (11, 66)	2065 2.87 1818	1.14
	WilkMul (D) (z)	(D, d) = (12, 78) (D, d) = (13, 91)	2313 3.95 2053 2649 5.89 2336	1.12 1.18
		(D, d) = (14, 105)	2892 8.56 2537	1.29
		(d, a, k) = (64, 14, 3) 2481 2.94 2145	1.13
	MignClu d (z; a, k)	(d, a, k) = (128, 14, 3) 4166 14.4 3555 (d, a, k) = (256, 14, 3) 7658 86.0 6523	1.16 1.27
		(d, a, k) = (512, 14, 3) 15044 650 10472 1.63
		(D, d) = (4, 27)	1628 0.77 1459	1.07
	NestClu (D) (z)	(D, d) = (5, 81) (D, d) = (6, 243)	4588 13.2 4085 13056 358 11824 1.26 1.12

Table 3 .

 3 Solving within the initial box[-50, 50]

2

with ε = 2 -53 with versions (V3), (V4) of Ccluster. n3: number of Graeffe iterations. τV3 and τV4: sequential time in seconds.

Table 4 .

 4 Table 4 that (V4') gives a modest improvement (up to 25% speedup) over (V4) whenlog ε = 53. This improvement generally grows withlog ε (but WilkMul[START_REF] Kobel | Computing real roots of real polynomials... and now for real[END_REF] (z) shows no difference). Solving within the box [-50, 50] 2 with versions (V4) and (V4') of Ccluster with three values of ε. τ53 (resp. τ530, τ5300): sequential time for (V4) and (V4') in seconds.

			(V4)			(V4')
	ε:	2 -53	2 -530	2 -5300	2 -53	2 -530	2 -5300
		τ53 (s) τ530/τ53 τ5300/τ53 τ53 (s) τ530/τ53 τ5300/τ53
	Bern 64 (z)	2.42	1.26	4.22	1.99	0.94	0.94
	Mign 64 (z; 14)	1.97	1.63	4.56	1.61	1.45	1.38
	Wilk 64 (z)	3.22	1.10	2.16	2.91	0.96	1.01
	Spir 64 (z)	4.09	1.33	5.25	3.05	0.95	0.95
	WilkMul (11) (z)	2.51	1.12	2.03	2.50	1.13	1.98
	MignClu 64 (z; 14, 3) 2.60	1.89	4.15	2.20	1.70	1.80
	NestClu 4 (z)	11.9	1.08	2.67	10.4	1.00	0.99

https://julialang.org/. Download our code in https://github.com/rimbach/Ccluster.

http://arblib.org/. Download our code in https://github.com/rimbach/Ccluster.jl.

We treat two-valued predicates for simplicity; the discussion could be extended to predicates (like T G * ) which returns a finite set of values.

Rémi's work has received funding from the European Unions Horizon 2020 research and innovation programme under grant agreement No. 676541. Victor's work is supported by NSF Grants # CCF-1116736 and # CCF-1563942 and by PSC CUNY Award 698130048. Chee's work is supported by NSF Grants # CCF-1423228 and # CCF-1564132. 4 Irina Voiculescu informed us that her student Dan-Andrei Gheorghe has independently implemented the same algorithm in a Masters Thesis Project (May 18, 2017) at Oxford University. Sewon Park and Martin Ziegler at KAIST,