C M Alrammal

G Hains

Intelligent Ordered XPath for Processing Data Streams

Data Streaming is a necessary and useful technique to process very large XML documents but poses serious algorithmic problems, various approaches and algorithms were implemented to fulfill this purpose. In this article we highlight and categorize the different important works in this domain. Furthermore, we present the critical parameters which affect the complexity of the streaming algorithms accompanied with examples. In the end, we propose a new approach for processing XML data streams using intelligent Ordered XPath that account for these critical parameters .

Introduction

The extensible markup language (XML) [START_REF]Extensible markup language (xml) 1[END_REF], has gone from the latest buzzword to an entrenched e-Business technology in record time. XML is currently being heavily pushed by the industry and community as the lingua franca for data representation and exchange on the Internet. It provides a much needed non-proprietary universal format for sharing hierarchical data among different software systems, and does so in a user-friendly manner. It is a verbose plain-text format, making it robust, platform-independent and legible to humans without additional tools. This popularity of XML has created several important applications like information dissemination, processing of the Scientific data, and real time news. Query Languages like XPath [START_REF] Clark | XML path language (XPath)[END_REF] and XQuery [START_REF] Boag | XQuery 1.0: An XML Query Language[END_REF] have been proposed for accessing the XML data, which provide a syntax for specifying which elements and attributes are sought to retrieve specific pieces of a document. Often, data is very large to fit into limited internal memory and in many cases it needs to be processed in real time during a single forward sequential scan. In addition, sometimes query results should be output as soon as they are found, in this case streaming fashion is the best approach to process the XML Data. The term data streaming is used to describe data items that are available for reading only once and that are provided in a fixed order determined by the data source. In the streaming model queries must be known before any data arrive, so queries can be preprocessed by building machines for query evaluation . Figure 1 illustrates a data stream processor. Due to the recursive nature of XML data, the single sequential forward scan of an XML streams, also the presence of descendant axes and the predicates in an XPath query, query evaluation process on XML streams raises different challenges compared to non-streaming environments, some of them are :

• During evaluation of XPath queries that contain predicates in streaming, we may encounter data that can be query solutions, before we reach the required data to evaluate the predicates1 in order to decide its satisfaction. Based on that, we need to record information about the potential answer nodes, as well as, their associated pattern matches to the query until the relevant data is encountered so that we can determine the predicate satisfaction and deciding their membership.

• The descendant axis traversal in a query and recursive structure of the XML document may cause an exponential number of pattern matches of sub-query from a single initial node. • The property of the existing XPath expression whose are unordered (predicates and axes)

will increase the number of buffered potential answer nodes before we encounter the required data to evaluate the predicate to decide its membership. In the worst case the buffering size will reach the document size.

Preliminaries

• Data Model of XML Streams An XML document can be seen as a rooted, ordered, labeled tree, where each node corresponds to an element, attribute or a value, and the edges represent (direct) elementsubelement or element-value relationships. The streaming XML data is modeled as a sequence of SAX [START_REF] Brownell | SAX2[END_REF] events extended with the depth of the event. An XML streaming algorithm accepts input XML document as SAX events, these events are: startElement(X) and endElement(X) which are activated respectively when the opening or closing tag of a streaming element is encountered and accept the name of the element X as input parameter.

• XPath

XPath [START_REF] Clark | XML path language (XPath)[END_REF] is a language that describes how to locate specific elements (and attributes, processing instructions, etc.) in a document, it treats an XML document as a logical ordered tree. XPath has a particular importance for XML applications since it is a core component of many XML processing standards such as XSLT [START_REF] Clark | XSL Transformations XSLT[END_REF] or XQuery [START_REF] Boag | XQuery 1.0: An XML Query Language[END_REF].

textitForward XPath [START_REF] Bar-Yossef | On the Memory Requirements XPath Evaluation over XML Streams[END_REF] is a fragment of XPath consists of queries that have only child, attribute, or descendant axes, it has different subfragments based on the manner of computing the predicates. Symmetric predicate is a predicate P if its evaluation on any document node X is independent of the order of X s children, also it is a predicate that does not contain positional function operators such as position() or last( Some queries can be rewritten to be SubSumption-free by eliminating redundant portions. They can be considered as subset of queries of Univariate XPath.

In this article we focus on Forward XPath. Figure 1.1 illustrates its grammar. A location path is a structural pattern composed of sub expressions called step. Each step consists of an axis (defines the tree-relationship between the selected nodes and the current node), a node-test (identifies a node within an axis), and zero or more predicates (to further refine the selected node-set). An absolute location path starts with a '/' or '//' and a relative location path starts with a './' or './/'. Our restriction to the downward axes in our XPath fragment is not absolute, we could cover more general axes than '/', '//' by using rewrite rules as shown in Olteanu paper [START_REF] Olteanu | XPath: Looking Forward[END_REF].

Concerning query evaluation process, usually two principle questions are asked. First, does our document D match the query Q?, in this case we determine whether there exists at least one match of Q in D. Second, which part or parts of the D match the Q?, it means outputting all nodes in an XML data tree D (answer nodes) whose satisfy a specified twig pattern Q at its result node. Different strategies and streaming algorithms were implemented for this purpose, we can categorize some of them based on the time of predicates evaluation in queries. Lazy streaming algorithm evaluates the predicates only when the closing tags of the streaming elements are encountered. While the Eager algorithm does that as soon an atom in a predicate is evaluated to true.

• Recursion In XML Data

Recursion occurs frequently in XML data in practice [START_REF] Choi | What are real DTDs like? International Workshop on the Web and Databases[END_REF], where some elements with the same name are nested on the same path in the data tree. In [START_REF] Bar-Yossef | On the Memory Requirements XPath Evaluation over XML Streams[END_REF], they define it as the recursion depth of an XML data tree D w.r.t the query node q in Q, denoted by r q , as the length of the longest sequence of nodes e 1 , ..., e r in D, such that (1) all the nodes lie on the same path (root-to-leaf), and (2) all the nodes match structurally the sub-pattern (q). To facilitate and clarify the meaning of Recursion, figure 2 where the single line edges represents child ('/'), the double line edges represents descendant('//'), single dashed line represents [./node()], double dashed line represents [.//node()] and the result node which is in this example the shaded node K. It is obvious from figure 2 that node C is not on the main path, this is why we do not consider it as a r q . If we have a look at table 1 clearly, both nodes A and B satisfy the definition of r q . Actually, r A = 3 represented by ( A 1 , A 2 , A 4 ), while r B = 2 represented by (B 7 , B 8 )

In our example, figure 2 the used XPath expression can be considered a simple one, for more complex XPath expression, see figure 3, it benefits from the grammar of figure 1.1. Moreover our Query is unordered (axes and predicate position), because node C in Q can be before node K or after.

• Document Depth

The depth of a document is the length of the longest root to leaf path in the tree representing the document d D . In our example in figure 2, document depth is the path from root node A 1 to the leaf node K 8

Large amount of work has been conducted to process XML documents in streaming fashion.

The different approaches to evaluate XPath queries on XML data streams can be categorized by the subset of XPath they support. In fact, most of them are automata based ( XPush [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF], XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF], SPEX [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF], XMLTK [START_REF] Avila-Campillo | XMLTK:An XML Toolkit for Scalable XML Stream Processing[END_REF]) or parse trees ( [10], [START_REF] Barton | Streaming XPath Processing with Forward and Backward Axes[END_REF], [START_REF] Bar-Yossef | On the Memory Requirements XPath Evaluation over XML Streams[END_REF], [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] ). All of them support a particular fragment of XPath called Forward XPath as it is defined in section 1.1 , other works use a subfragment of Forward XPath. YFilter [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF], XMLTK [START_REF] Avila-Campillo | XMLTK:An XML Toolkit for Scalable XML Stream Processing[END_REF] and X-Scan [START_REF] Ives | An XML Query Engine for Network-Bound Data[END_REF] support XPath queries containing the child and descendant-or-self axes and wildcards using finite state automata.

In [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF] authors seek to process efficiently large number of XPath expressions with many predicates per query on a stream XML data. Therefore, they propose to lazily construct a single deterministic pushdown automata ( a special deterministic stack machine) which is called "XPush Machine" for a given XPath filters, the input is a series of SAX events and the output is a set of filters that match the processed document. The used fragment of XPath is Forward XPath. Note that, the memory requirement for this technique is manageable and the cost of laziness is recovered later. An application example for this work is XML Message Brokers. AFilter [START_REF] Candan | AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering[END_REF] is an adaptable XPath query evaluation approach that needs a base memory requirement which is linear in query and data size. If more memory is provided to AFilter, it uses the remaining main memory for a caching approach to evaluate queries faster than with only the base memory. AFilter is mainly based on a lazy DFA and it supports wildcard, but does not support predicate filters. Similar to XPush [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF], it is designed to evaluate a large set of queries.

The approach presented in TurboXPath [START_REF] Josifovski | Querying XML Streams[END_REF] discusses how to handle the child and descendant or-self axes, predicates (including functions and arithmetics) and wildcards in XQuery using TurboXPath. The input query is translated into a set of parse trees. Whenever a matching of a parse tree is found within the data stream, the relevant data is stored in form of a tuple that is afterward evaluated to check whether predicate-and join conditions are fulfilled. The output is constructed out of those tuples the conditions of which have been evaluated to true. The used XPath fragment is a Forward XPath (child, descendant, self, axes, any node test (*), functions, arithmetic and structural predicates). Furthermore, it supports parent and ancestor axes. Important feature of TurboXpath, it avoids the translation of query into a finite state automata like [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF] which might degrade the query performance in scenarios where several independent queries are executed in parallel over different XML Stream. Another distinguishing feature its capability to process query trees constructed of several concatenated path returning tuples as result.

[2] builds a parse tree as well, it supports the parent and the ancestor axis in addition to that Forward XPath axis. This parse tree is used to 'predict' the next matching nodes and the level in which they have to occur, for example, consider the query //C/D and a matching of C in level 3. Then the next interesting matching would be a node D in level 4.

XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF] and SPEX [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF] propose a method for evaluating XPath queries over streaming data to handle closers, aggregation and multiple predicates. Their method is designed based on hierarchical arrangement of push-down transducers augmented with buffers. Automata is extended by actions attached to states, extended by a buffer to evaluate XPath queries. The main idea is that a nondeterministic push-down transducer (PDT) is generated for each location step in an XPath query, and these PDTs are combined into a hierarchical pushdown transducer in the form of a binary tree. In fact XSQ might buffer multiple physical copies of a potential answer nodes, because buffering space size is measured by the maximum of physical copies of a potential answer nodes buffered at the same time during the running time, therefore, it might has a higher cost, particularly with very deep recursion. The Considered fragment of XPath is XPath 1.0 including( closures, aggregations, and multiple predicates) except reverse axes and position functions (such as position() and last()). This technique eagerly evaluates queries and it is fully implemented thus give us the possibility to compare our algorithms with it.

The approach presented in [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF] uses a structure which resembles a parse tree with stacks attached to each node. These stacks are used to store XML nodes that are solutions to the parse tree nodes subquery (or to store XML nodes that are candidates for a solution in case of predicate filters).

In [START_REF] Chen | ViteX : a Streaming Xpath Processing System[END_REF] authors aim to achieve polynomial time complexity in both data and query size for evaluating XPath queries on streaming data, based on that, they propose ViteX System that is composed of four modules: 1. XPath Parser, it takes an XPath query Q as input and generates a tree representation of the query. 2. The TwigM builder, which constructs a TwigM machine according to the input query tree. 3. The SAX parser that takes an XML stream and outputs a sequence of SAX events. 4. As SAX events stream in, TwigM changes its state according to the current state and the input event, then it computes a set of XML fragments as solutions to Q. The idea is using an Encoding Technique, TwigM uses a compact data structure to encode patterns matches rather than storing them explicitly which is a memory advantage. After that, it computes query solution by probing the compact data structure in Lazy fashion without computing pattern matches. Notice that it supports queries with AN D operator only. [31] introduce a streaming XPath algorithm (QuickXScan), it evaluates XPath expression with predicates by one sequential Scan of XML data, it is based on the principles similar to that of attribute grammars. QuickXScan support the following forward axes: child, descendant, attribute, self and self-or descendant and the parent axes by transformation into forward axis [START_REF] Olteanu | XPath: Looking Forward[END_REF]. Authors, model an XPath query with a query tree. In structural join based algorithms, there is a nice solution of using compact stacks to represent a possibly combinatorial explosive number of matching path instantiations with linear complexity like [START_REF] Jiang | Holistic Twig Joins on Indexed XML Documents[END_REF], therefore, QuickXScan extends the idea of compact stacks in a technique called matching grid, which is used also in [START_REF] Ramanan | Evaluating an XPath Query on a Streaming XML Document[END_REF]. Again query representation can be considered as the best feature of this technique because it represents complex queries using a query tree, together with a set of variables and evaluation rules associated with each query node. Notice that in their paper they do not address the issue of streaming output.

In [START_REF] Chen | Expedite : A System for Encoded XML Processing[END_REF] they present a model of data processing in an information systems exchange environment, it consists of a simple and general encoding scheme for servers, and streaming query processing algorithms on encoded XML stream for data receivers with constrained computing abilities "binary encoding". The target XPath is a subset of Forward XPath that include: child, descendant, predicate and name tests. The EXPedite query processor takes an encoded XML stream and an encoded XPath query as input, and outputs the encoded fragment in the XML stream that matches the query. The idea of the query processing algorithm is taken from different proposed techniques [START_REF] Dehaan | A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding[END_REF], [START_REF] Grust | Accelerating XPath Location Steps[END_REF] for efficient query evaluation based on XML node labels for XML data stored in the database , in other words, the used algorithm evaluates queries based on XML labels ¡start, end, depth¿. For the time being, EXPedite encoder support only XML elements and character data, and the query processor support Twig queries In [START_REF] Bttcher | Evaluating XPath Queries on XML Data Streams[END_REF] a SAX Based approach is introduced to evaluate the XPath queries that support all axes of Core XPath. Starting from the XPath query, this approach generates a stack of automata that uses the SAX stream as input and generates the result of the query as an output SAX stream. Each input query is translated into an automaton that consists of only four different types of transitions. The small size of the generated automata allows for a fast evaluation of the input XML data stream within a small amount of memory. Note that their system supports the sibling axes, whereas other approaches like ( XMLTK [START_REF] Avila-Campillo | XMLTK:An XML Toolkit for Scalable XML Stream Processing[END_REF], AFilter [START_REF] Candan | AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering[END_REF], XPush [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF], XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF], SPEX [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF]) are limited to the parent-child and ancestor-descendant axes. time in the streaming environment and to show that algorithms are not only time-efficient but also space-efficient. Based on their experiments, both LQ and EQ algorithms show very similar time performance in practice. In non recursive cases, LQ and TwigM has the same buffering space costs, as well as, EQ and XSQ has the same case. EQ achieve the optimal buffering space performance, therefore it can be considered as the best performance representation between algorithms in the state of the art of their paper.

In comparison to all these approaches, we introduce the notion of an ordered and oriented Forward XPath taking in our consideration that attribute axis it can not be handled in a way similar to the child axis.

3 Motivations and Objectives

Complexity

Usually, the caching space costs of stream-querying algorithms depend on the number of elements cached in the run-time stack(s). It is bounded by the maximum document depth d D when queries do not involve *-nodes or the same name nodes and does not exceed (|Q|.d D ) in the worst case. Also time performance of stream querying algorithms can be measured by the following T p = t all -t input -t output , where t all is the total running time, t input is the reading time usually from the disk into memory also parsing the XML document, and t output is the taken time to output the result nodes from the memory to the disk. In practice complexity depends on the following :

• Structure of XML Document data Documents may have different structures, for instance, shallow XML documents (Wide) that does not include recursive elements. In this case the cashing space costs of the streamquerying algorithm is almost negligible. An example for this type of XML document is XMark [START_REF] Schmidt | Xmark:An XML Benchmark Project[END_REF] which is a famous benchmark dataset that allows users and developers to gain insights into the characteristics of their XML repositories. See table 2 which indicates the maximum depth of this dataset that reaches 12(not deep), and it has a large data size 113M.

While others are semi deep and recursive like Book dataset [START_REF] Diaz | Book : IBM XML Dataset[END_REF], actually it is a synthetic dataset, generated using IBM's XML generator, based on real DTD from W3C XQuery use case. As we can see from table 2, it has a size of 12 M which is not enormous and a maximum depth that reaches 22 which is quite deep enough comparison to its size.

It includes only one recursive element named section . In fact, different sections node can be nested on the same path in the data tree, therefore this kind of dataset(semi deep and recursive) increase the buffering space and processing time. We can find also document with narrow deep structure, an example TreeBank [START_REF] Suciu | Treebank:XML data repository[END_REF], here one can recognize the structure of the document from the Maximum depth in table 2, it is 36, moreover, the average depth which is 7.8 indicates that this document is narrow. The existence of these properties in the document will increase of costs of the stream-querying algorithms significantly .

• The XPath Expression (recursion).

Simple XPath expressions may not require huge buffering space size, see figure 2, while the existence of descendant axis '//', the wildcard * or the same name node in the expression will enormously increase the buffering space size and processing time particularly with deep and recursion XML document because we will be forced to buffer large number of potential answer nodes, an example of this XPath Expression type is //A[./B//*]//*[./A]/K see figure 3. We call this extension Complex XPath. The used methodology to evaluate the XPath expression may affect the buffering space size and processing time. For example, let us consider that we have the document D and the query Q //A[./F]/C figure 4. In Lazy approach, B = n or in other words B = |D| since the predicate of A is not evaluated until ¡/A i ¿ arrives. In this case all nodes starting from C 1 to C n have to be buffered, which will increase the buffering size remarkably. While in Eager approach B = 0 because the predicates of A is evaluated to be true the moment element ¡F ¿ arrives. Thus, each ¡C i ¿ can be flushed as a query result the moment it arrives and does not need to be buffered at all. Obviously this will improve the buffering space performance.

Figure 4: Lazy and Eager Approaches.

Note that B is the size of buffering space, which is measured by the maximum number of potential answer nodes buffered at a time during the running time. It is clear that Eager strategy has a better buffering space strategy, but both of them do not handle the problem of descendant axis and the complexity of unordered XPath expressions. Note that figure 4 is an example of a wide dataset.

Motivation Examples

• Descendant axis Problem In parse tree approach, an XPath query specifies a twig pattern Q to navigate an XML Document D. Document size |D| is the number of elements in the D, while query size is the number of nodes in Q. Query nodes are three types, we have the result node which specifies the output of the XPath, also axis nodes which are all non-result nodes on the main path of Q, that means on the path from the root to the result node. An important question is the order of the node H, actually in our example node H can be in different orders, might be before nodes G, I or after, and in a worst case it can be after node D ,which will increase the complexity (buffer space and processing time) remarkably, due to the fact that our XPath expression is unordered (axes and predicates position).

• Attributes Order Problem Another important point is the child and attribute axes. Both axes can not be handled in a similar way. The reason again relates to elements order. A simple example that prove the difference between both axes is the following: let us consider that we have the following XML Documents (f,g), figure

<A m='male' f='female'> <A f='female' m='male'> <B> </B> <C></C> <C> </C> <B></B> </A> </A> XML Document f XML Document g Obviously, in both documents attributes are unordered, just because attribute specification markup is unordered, which means, the order of attribute specifications in a start-tag or empty-element tag is not significant [START_REF]Extensible markup language (xml) 1[END_REF]. While it is not the same matter for elements. The order of elements in an XML document as determined by XML syntax is called document order. One can have other types of orders such as alphabetical and numerical, but document order is determined solely by XML syntax. Both [START_REF] Bar-Yossef | On the Memory Requirements XPath Evaluation over XML Streams[END_REF] and [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] do not consider this point, they do not treat explicitly the attribute axis @, considering that it can be handled in a way Similar to the Child Axis. This consideration affects the evaluation process of the XPath over the XML data stream.

• Buffering space size explosion Launching a complex unordered XPath expression that contain *-nodes and the same name nodes to search a narrow deep recursive XML Document affects the complexity by increasing both processing time and buffering space incredibly. In the worst case, it may result in buffering space size explosion. An example for that is launching complex XPath expressions to search the dataset Treebank in table 2 using XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF] . Moreover, in our case, XSQ may report too many path combinations and terminate the searching process. While using an ordered XPath expression will reduce remarkably the potential answer nodes which is a very good complexity investment for both time processing and buffering space size.

4 Aware-Metadata Schema and Ordered XPath

In this paper, we propose the idea of a new approach for processing XML data streams in order to prepare data to a reasoning task. Our processing relies on the structure of the document, the information that it contains, and the ordered XPath.

Metadata is data associated with objects which relieves their potential users of having full advance knowledge of their existence or characteristics. The term "meta" derives from the Greek word denoting a nature of a higher order. Information resources must be made visible in a way that allows people to tell whether the resources are likely to be useful to them. This is no less important in the online world, and in particular, the World Wide Web. Metadata is a systematic method for describing resources and thereby improving access to them. If a resource is worth making available, then it is worth describing it with metadata, so as to maximize the ability to locate it.

Ordered XPath has been investigated before in relational database. [START_REF] Choi | Efficient Support for Ordered XPath Processing in Tree-Unaware Commercial Relational Databases[END_REF] Presents a novel approach to efficiency evaluate ordered XPath queries in a relational databases. A scheme extends SUCXENT++ [START_REF] Prakash | Efficient Recursive XML Query Processing Using Relational Database Systems[END_REF] was proposed to support the processing of ordered axes and predicates while maintaining its original properties, their main focus is on the evaluation of the following, preceding, following-sibling, and preceding-sibling axes as well as position-based and range predicates.

In this article we define the ordered XPath as the following : it is a language that treats an XML document as logical ordered tree to locate specific elements (and attributes, processing instruction, etc... .) considering that it has ordered axes and predicate position.

To support ordered XPath Queries, the order information of nodes must be captured by the schema to process these queries efficiently. Figure 6 illustrates the order (ordered axes) of document D. In our state of the art we found many techniques and algorithms to process and evaluate XPath Expressions over XML Data streams. These techniques vary in the used fragment of XPath, but all of them use unordered XPath Expression. In section 3.2 we introduced very important motivations that explain the idea and complexity investment of ordered XPath to evaluate efficiently the axes and position predicates. Next we will present few examples to highlight the difference between using an ordered and unordered XPath expressions .

Ordered vs. Unordered XPath

The purpose of aware-metadata schema is to help us locating the part of XML document we search by providing information about the structure and the content of this document. Thus we can profit from the ordered XPath property to efficiently retrieve the required data that correspond to the XPath expression. Comparison examples between both ordered and unordered XPaths are as follows: Example 1: let us suppose that we use the dataset TreeBank which is narrow and deep, see table 2 and the Lazy strategy of figure 4. Though Eager strategy has a better performance on this example, we use the Lazy one in our example to illustrate the importance of ordered XPath. By using unordered XPath, the buffering space will be in the worst case B = |D| = 2437. Now using ordered XPath which is provided in information by user as follows (start after node order 1000 or interesting potential answer nodes are after node order 1000), this will reduce the worst case of buffering size to be B=1437, such information may be available for a user who can grossly locate the target of the query, for example "the section we search in is somewhere after page number 1000 in the book". In the same example imagine that ordered XPath was provided in information as follows (always search to right of the context node), here buffering size can be reduced remarkably because we will avoid buffering any potential answer node lie to the left of the context node. Example 2: in figure 6 if the XPath is provided in information by user as follows( start at the axis order 2 of node A 1 , then we do not need to buffer the following nodes: B 4 , B 5 , C 1 though they would otherwise match the query. Note that the position of the predicate node C is to the right(after) of the result node K( predicate position). Thus, we avoid to evaluate the predicate node C 5 .

Advantages of ordered XPath

It is true that sometimes by restricting the query to ordered XPath, our document may not satisfy the query. In this case relaunching the query with new information is necessary. In the same time, there are many advantages of ordered XPath that account for the critical complexity parameters. They are summarized as the following :

(1) XPath complexity: in both cases, simple XPath, see figure 2 or complex XPath see figure 3, the buffering size performance will be improved due to the property of the ordered (axes and predicates position) of XPath, while it is not the same case for unordered XPath.

(2) XML document structures: ordered XPath can be efficient with the different XML document structures. For example, the wide dataset like XMark, or the narrow recursive like TreeBank, as we saw in the examples of section 4.1.

(3) Query evaluation approach: it is as well, efficient with the various used approach of query evaluation like lazy and eager. In the same example of section 4.1, it is explained how to avoid the worst case of buffering size with Lazy. Note that Eager approach may has a better performance. So using ordered XPath with the Eager approach will also result in a better performance than using it with the Lazy one. Space saving come as we have shown, from reduced buffering, and for a given strategy Eager/Lazy ordering will decrease time simply by avoiding unnecessary buffering operations. We can conclude based on the previous examples, that the efficiency of ordered XPath does not only improve the buffering space, but also the processing time.

In this article we presented different approaches related to XPath expression evaluation process over XML data Stream, we categorized the different works by the sub-set of XPath they support into main two parts. First, Automata based, like ( XPush [START_REF] Gupta | Stream Processing of XPath Queries with Predicates[END_REF], XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF], SPEX [START_REF] Olteanu | An Evaluation of Regular Path Expressions with Qualifiers against XML Streams[END_REF], XMLTK [START_REF] Avila-Campillo | XMLTK:An XML Toolkit for Scalable XML Stream Processing[END_REF]). Second , parse trees like ( [START_REF] Chen | An Efficient XPath Query Processor for XML Streams[END_REF], [START_REF] Barton | Streaming XPath Processing with Forward and Backward Axes[END_REF], [START_REF] Bar-Yossef | On the Memory Requirements XPath Evaluation over XML Streams[END_REF], [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] ). Variant examples were introduced to explain the complexity of streaming algorithms, like query evaluation strategy, the XPath expression (recursion) and the structure of XML document data. Based on that the notion of the intelligent ordered XPath for processing efficiently large XML data streams was introduced.

Future Work

The process of writing an algorithm for the intelligent ordered XPath is under going, after that, experiments will be done to compare the performance of our algorithm with stream-querying systems like [START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF], XSQ [START_REF] Peng | XPath Queries on Streaming Data[END_REF] and [START_REF] Chen | ViteX : a Streaming Xpath Processing System[END_REF]

Figure 1 :

 1 Figure 1: Data Stream Processor.

Figure 2 :

 2 Figure 2: Recursion depth of D w.r.t Q.

  The used fragment of XPath is a Sub-fragment of Forward XPath {/, //, * , []}. TwigM achieves a complexity of Polynomial time O(|D||Q|(|Q| + d D .B) where B is the size of the candidate solutions. While for non-recursive dataset 2 TwigM has the complexity of O(|D||Q|). It has the same case like XSQ, because sometimes it might buffer multiple physical copies of a potential answer node at the same running time.

Figure 3 :

 3 Figure 3: Complex XPath

  Finally, predicate nodes which are all other nodes. For example let us suppose that we have the following XPath //A[./E]/B[./F]//C[./G/I and //H]/D[./J], which is illustrated in figure 5.

Figure 5 :

 5 Figure 5: Twig Pattern of an XPath Query Q.

Figure 3 . 2

 32 Figure 3.2 XML Documents

Figure 6 :

 6 Figure 6: Document Information Order

Table 1 :

 1 Nodes of Structural Matching of Q in D

	Path := GenericPath | GenericPath AttributeStep
	| AttributeStep
	GenericPath := GenericStep	| GenericPath GenericStep
	GenericStep := Axis NodeTest | Axis NodeTest '[' Predicate ']'
	AttributeStep := '@' NodeTest| '@' NodeTest '[' Predicate ']'
	Axis := '/' | '//'
	NodeTest := name | '*'
	Predicate := PredicatePath | PredicatePath CompOp constant
		| Predicate 'and' Predicate
		| Predicate 'or' Predicate
		| 'not(' Predicate ')'
	CompOp := '=' | '!=' | '>' | '>=' | '<' | '<='
	PredicatePath := '.' GenericPath | '.' GenericPath AttributeStep
		| AttributeStep
	Figure 1.1 Grammar of the Intelligent Forward XPath

Table 2 :

 2 They have implemented a prototype called XPA. The query processor decomposes and normalizes each XPath query, such Different Dataset Structures that the resulting path queries contain only three different types of axes, and then converts them into lean XPath automata for which a stack of active states is stored. The input SAX event stream is converted into a binary SAX event stream that serves as input of the XPath automata.In[START_REF] Gou | Efficient Algorithms for Evaluating Xpath over Streams[END_REF] authors propose two Algorithms to evaluate XPath over streams, algorithms accept XML Document as a stream of SAX events. Start and end element events are activated when the opening and closing tag of the streaming elements are arrived. Streaming algorithms are categorized into two classes, based on when they evaluate the predicate in the queries: 1. Lazy Streaming Algorithm (LQ), evaluation is occurred at the closing tag of the streaming element. 2. Eager Streaming Algorithm(EQ), evaluation is occurred if an atom in the predicate is evaluated to true. The used fragment of XPath called Univariate XPath, see section (1.1). The goal of both algorithms is to prove that Univariate XPath can be efficiently evaluated in O(|D||Q|)

		XMark	Book	TreeBank
	Structure	Wide	Semi deep+	narrow deep
		and Shallow and recursive and recursive
	Data Size	113M	12M	82M
	Nbr. of nodes	1666K	114K	2437K
	Max./Avg Depth 12/5.5	22/19.4	36/7.6

XML data may be processed in several different models, which require different query processing strategies like LAZY and EAGER

There are no nodes of a certain type can be nested in another nodes of the same type.

Acknowledgments

The first author is funded by a doctoral scholarship from INNOVIMAX and a CIFRE scheme from the French government.


On the complexity of real root isolation using Continued Fractions

Keywords:

Introduction

In this paper we deal with real root isolation of univariate integer polynomials, a fundamental problem in computer algebra as well as in many applications ranging from computational geometry to quantifier elimination. The problem consists in computing intervals with rational endpoints which contain exactly one real root of the polynomial and have such an interval for every real root. We use the continued fraction expansion of real algebraic numbers. Recall that such a number is a real root of an integer polynomial.

A major motivation is to explain the method's good performance in implementations, despite the higher complexity bounds which were known until now. Indeed, we show that continued fractions lead to asymptotic bit complexity bounds that match those recently proven for other exact methods, such as Sturm, Descartes and Bernstein subdivision algorithms. Using results from the metric theory of continued fractions we prove that the algorithm achieves an expected complexity of O B (d 4 τ 2 ), where d is the polynomial degree and τ bounds the coefficient bit size, thus we improve the previous known bound by a factor of dτ . Moreover, under the hypothesis that d = O(τ ), we present a variant of the algorithm with complexity O B (d 3 τ ).

Notation

In what follows O B means bit complexity and the O B -notation means that we are ignoring logarithmic factors. For a polynomial A = d i=1 a i X i ∈ Z[X], deg (A) denotes its degree. We consider square-free polynomials except if explicitly stated otherwise. By L (A) we denote an upper bound on the bit size of the coefficients of A (including a bit for the sign). For a ∈ Q, L (a) ≥ 1 is the maximum bit size of the numerator and the denominator. Let M (τ ) denote the bit complexity of multiplying two integers of bit size at most τ . Using FFT, M (τ ) = O B (τ lg c τ ) for a suitable constant c. V ar(A) denotes the number of sign variations in the coefficient list of A ignoring zero terms and ∆ the separation bound of A, that is the smallest distance between two (complex) roots of A.

Previous work and our results

Real root isolation of univariate integer polynomials is a well known problem and various algorithms exist for it. Moreover, there is a huge bibliography on the problem so we have to mention that we only scratch the surface of the existing literature and we encourage the reader to refer to the references.

Most exact subdivision based algorithms for real root isolation are based either on Descartes' rule of sign (Th. 1) or on Sturm sequences. Roughly speaking, the idea behind both approaches is to subdivide a given interval that initially contains all the real roots until it is certified that none or one real root is contained in the tested interval. Descartes' approach achieves this by repeatedly transforming the original polynomial and counting the sign variations in the coefficients' list, while Sturm's approach computes a signed polynomial remainder sequence and evaluates it over the endpoints of the interval of interest. Quite recently it was proven (c.f [START_REF] Du | Amortized bound for root isolation via Sturm sequences[END_REF][START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF][START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF] and references therein) that both approaches, the one based on Descartes' rule of sign (where the polynomials are represented either in the monomial or in the Bernstein basis) and the one based on Sturm sequences, achieve the same bit complexity bound, namely O B (d 4 τ 2 ) or O B (N 6 ), where N = max {d, τ }. Moreover, using Sturm(-Habicht) sequences in a pre-processing and a post-processing step [START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF] the bound holds for the non square-free case and the multiplicities of the roots can also be computed. If the degree of the polynomial is ≤ 4 then real solving can be performed in O [START_REF] Akritas | There is no "Uspensky's method[END_REF] or O B (τ ) [START_REF] Emiris | Computing with real algebraic numbers of small degree[END_REF].

The continued fraction algorithm (from now on called CF) differs from the subdivision based algorithms in that instead of bisecting a given initial interval it computes the continued fraction expansion for each real root of the polynomial. The first formulation of the algorithm is due to Vincent [START_REF] Vincent | Sur la résolution des équations numériques[END_REF], see also [START_REF] Akritas | There is no "Uspensky's method[END_REF][START_REF] Alesina | A new proof of Vincent's theorem[END_REF] for historical references. It was based on his theorem (Th. 4 without the terminating condition) where it was stated that repeated transformations of the polynomial will eventually yield a polynomial with zero (or one) sign variation, thus Descartes' rule (Th. 1 and Rem. 2) implies that the transformed polynomial has zero (resp. one) real root in (0, ∞). If one sign variation is attained then the inverse transformation can be applied in order to compute an isolating interval for the real root that corresponds to the original polynomial. Moreover, the integers, c i 's, used in the transformations correspond to the partial quotients of the continued fraction expansion of the real root. However, Vincent's algorithm is exponential [START_REF] Collins | Polynomial real root isolation using Descartes' rule of signs[END_REF]. He computed the c i 's in the transformation of Th. 4 by repeated shift operations of the form X → X + 1, thus if one of the c i 's (or even the sum of all) is of magnitude, say, 2 τ then an exponential number of steps must be performed.

Uspensky [START_REF] Uspensky | Theory of Equations[END_REF] extended Vincent's theorem by computing an upper bound on the number of transformations so as to isolate the real roots, but failed to deal with its exponential behavior. See also [START_REF] Cantor | A continued fraction algorithm for real algebraic numbers[END_REF][START_REF] Rosen | A continued fraction algorithm for approximating all real polynomial roots[END_REF] where the problem of approximating a real algebraic number is also considered. Using Vincent's theorem, Collins and Akritas [START_REF] Collins | Polynomial real root isolation using Descartes' rule of signs[END_REF] derived a polynomial subdivision-based algorithm using Descartes' rule of sign.

Akritas [START_REF] Akritas | An implementation of Vincent's theorem[END_REF][START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF] dealt with the exponential behavior of the CF algorithm, by computing the c i 's in the transformations as positive lower bounds of the positive real roots, via Cauchy's bound (for details, see sec. 3). He achieved a complexity of O B (d 5 τ 3 ) or O B (N 8 ), without using fast Taylor shifts [START_REF] Zur Gathen | Fast Algorithms for Taylor Shifts and Certain Difference Equations[END_REF]. However, it is not clear how this approach accounts for the increased coefficient size in the transformed polynomial after applying a map of the form X → b + X. Another issue is to bound the size of the c i . Refer to Eq. ( 1) which indicates that the magnitude of the partial quotients is unbounded. CF is the standard real root isolation function in Mathematica [START_REF] Akritas | Implementation of real root isolation algorithms in Mathematica[END_REF] and for some experiments against subdivision-based algorithms, also in Mathematica, the reader may refer to [START_REF] Akritas | A comparative study of two real root isolation methods[END_REF].

Another class of univariate solvers are numerical solvers, e.g [START_REF] Pan | Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding[END_REF][START_REF] Pan | Solving a polynomial equation: Some history and recent progress[END_REF][START_REF] Schönhage | The fundamental theorem of algebra in terms of computational complexity[END_REF], that compute an approximation of all the roots (real and complex) of a polynomial up to a desired accuracy. The complexity of these algorithms is O B (d 3 τ ).

The contributions of this paper are the following: First, we improve the bound of the number of steps (transformations) that the CF algorithm performs. The proof of this is INRIA achieved through Th. 6. Second, we bound the bit size of the partial quotients and thus the growth of the transformed polynomials which appear during the algorithm. For this we use the hypothesis of the continued fraction expansion of real numbers and a standard average case analysis. We revisit the proof of [START_REF] Akritas | An implementation of Vincent's theorem[END_REF][START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF] so as to improve the overall bit complexity bound of the algorithm to O B (N 6 ), thus matching the current record complexity for exact real root isolation. From a theoretical perspective, we present a variant of the CF algorithm which, under the hypothesis that d = O(τ ), has expected complexity O B (N 4 ), thus matching the complexity of the numerical algorithms. The extension to the non square-free case uses the techniques from [START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF]. Finally, we present our efficient open-source C++ implementation of the O B (N 6 ) algorithm and illustrate it on various data sets, including polynomials of degree up to 1000 and coefficients of 8000 bits. Our software seems comparable to, and some times faster than the root isolation implementations that we tested, including rs1 , which seems to be one of the fastest available software for exact real root isolation. We also tested a numeric solver, namely aberth [START_REF] Bini | Numerical computation of polynomial zeros by means of Aberth's method[END_REF][START_REF] Bini | Design, analysis, and implementation of a multiprecision polynomial rootfinder[END_REF], which is very efficient in practice but needs special tuning in order to produce the correct number of real roots. We believe that our software contributes towards reducing the gap between rational and numeric computation, the latter being usually perceived as faster.

Part of this work appeared in [START_REF] Tsigaridas | Univariate polynomial real root isolation: Continued fractions revisited[END_REF]. The rest of the paper is structured as follows. The next section sketches the theory behind continued fractions. Sec. 3 presents the CF algorithm and Sec. 4 its analysis. We conclude with experiments using our implementation, along with comparisons against other available software for univariate equation solving.

Continued fractions

We present a short introduction to continued fractions, following [START_REF] Van Der Poorten | An introduction to continued fractions[END_REF] which, although is far from complete, suffices for our purposes. The reader may refer to e.g [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Bombieri | Continued fractions of algebraic numbers[END_REF][START_REF] Van Der Poorten | An introduction to continued fractions[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF]. In general a simple (regular) continued fraction is a (possibly infinite) expression of the form

c 0 + 1 c 1 + 1 c 2 + . . . = [c 0 , c 1 , c 2 , . . . ],
where the numbers c i are called partial quotients, c i ∈ Z and c i ≥ 1 for i > 0. Notice that c 0 may have any sign, however in our real root isolation algorithm c 0 ≥ 0, without loss of generality. By considering the recurrent relations

P -1 = 1, P 0 = c 0 , P n+1 = c n+1 P n + P n-1 , Q -1 = 0, Q 0 = 1, Q n+1 = c n+1 Q n + Q n-1 ,
it can be shown by induction that R n = Pn Qn = [c 0 , c 1 , . . . , c n ], for n = 0, 1, 2, . . . and moreover that

P n Q n+1 -P n+1 Q n = (-1) n+1 , P n Q n+2 -P n+2 Q n = (-1) n+1 c n+2 . If γ = [c 0 , c 1 , . . . ] then γ = c 0 + 1 Q0Q1 -1 Q1Q2 + • • • = c 0 + ∞ n=1 (-1) n-1
Qn-1Qn and since this is a series of decreasing alternating terms it converges to some real number γ. A finite section R n = Pn Qn = [c 0 , c 1 , . . . , c n ] is called the n-th convergent (or approximant) of γ and the tails γ n+1 = [c n+1 , c n+2 , . . . ] are known as its complete quotients. That is γ = [c 0 , c 1 , . . . , c n , γ n+1 ] for n = 0, 1, 2, . . . . There is a one to one correspondence between the real numbers and the continued fractions, where evidently the finite continued fractions correspond to rational numbers.

It is known that Q n ≥ F n+1 and that F n+1 < φ n < F n+2 , where F n is the n-th Fibonacci number and φ = 1+ is the golden ratio. Continued fractions are the best (for a given denominator size), approximation. This is as follows:

1 Q n (Q n+1 + Q n ) ≤ γ - P n Q n ≤ 1 Q n Q n+1 < φ -2n+1 .
Let γ = [c 0 , c 1 , . . . ] be the continued fraction expansion of a real number. The Gauss-Kuzmin distribution [START_REF] Bombieri | Continued fractions of algebraic numbers[END_REF][START_REF] Richtmyer | Continued fraction expansions of algebraic numbers[END_REF] states that for almost all real numbers γ (meaning that the set of exceptions has Lebesgue measure zero) the probability for a positive integer δ to appear as an element c i in the continued fraction expansion of γ is

P rob[c i = δ] = lg (δ + 1) 2 δ(δ + 2)
, for any fixed i > 0.

(

) 1
The Gauss-Kuzmin law induces that we can not bound the mean value of the partial quotients or in other words that the expected value (arithmetic mean) of the partial quotients is diverging, i.e

E[c i ] = ∞ δ=1 δ P rob[c i = δ] = ∞, for i > 0.
Surprisingly enough the geometric (and the harmonic) mean is not only asymptotically bounded, but is bounded by a constant, for almost all γ ∈ R. For the geometric mean this is the famous Khintchine's constant [START_REF] Khintchine | Continued Fractions[END_REF], i.e. lim n→∞ n n i=1 c i = K = 2.685452001... which is not known if it is an irrational number, let alone transcendental. The reader may refer to [START_REF] Bailey | On the Khintchine Constant[END_REF] for a comprehensive treatment of Khintchine's means. The expected value of the INRIA bit size of the partial quotients is a constant for almost all real numbers, when n → ∞ or n sufficiently big [START_REF] Khintchine | Continued Fractions[END_REF][START_REF] Richtmyer | Continued fraction expansions of algebraic numbers[END_REF]. Following closely [START_REF] Richtmyer | Continued fraction expansions of algebraic numbers[END_REF], we have:

E[ln c i ] = 1 n n i=1 ln c i = ln K = 0.98785..., as n → ∞, ∀ i > 0. Let L (c i ) b i , then E[b i ] = O(1). (2)
A real number has an (eventually) periodic continued fraction expansion if and only if it is a root of an irreducible quadratic polynomial. The set of real algebraic numbers is countable and has Lebesgue measure zero, thus there is chance that Gauss-Kuzmin distribution and Khintchine's law do not hold for it. However, "There is no reason to believe that the continued fraction expansions of non-quadratic algebraic irrationals generally do anything other than faithfully follow Khintchine's law" [START_REF] Brent | A Comparative Study of Algorithms for Computing Continued Fractions of Algebraic Numbers[END_REF]. Moreover, various experimental results [START_REF] Bombieri | Continued fractions of algebraic numbers[END_REF][START_REF] Richtmyer | Continued fraction expansions of algebraic numbers[END_REF][START_REF] Rosen | A continued fraction algorithm for approximating all real polynomial roots[END_REF] support the conjecture. It is a major open problem to find an irreducible integer polynomial such that the continued fraction expansions of its real roots do not follow the conjecture or to prove the conjecture.

For the largest digit that can appear in the partial quotients of a rational number the reader may refer to [START_REF] Hensley | The largest digit in the continued fraction expansion of a rational number[END_REF].

For our analysis we rely on the conjecture that Gauss-Kuzmin's distribution and Khintchine's law hold for the set of real algebraic numbers. If it can proven that the partial quotients of the continued fraction expansion of real algebraic numbers are bounded this will lead to an improvement of our complexity bounds.

The CF algorithm

Theorem 1 (Descartes' rule of sign) The number R of real roots of A(X) in (0, ∞) is bounded by V ar(A) and we have R ≡ V ar(A) mod 2.

Remark 2 In general Descartes' rule of sign obtains an overestimation of the number of the positive real roots. However, if we know that A is hyperbolic, i.e has only real roots or when the number of sign variations is 0 or 1 then it counts exactly.

The proof of Th. 1 follows from the following theorem which is due to Budan: Theorem 3 (Budan) [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Mignotte | Mathematics for computer algebra[END_REF] Let a polynomial A, such that deg(A) = d and let a < b, where a, b ∈ R. Let A a , resp. A b , be the polynomial produced after we apply the map X → X + a, resp. X → X + b, to A. Then the following hold: The CF algorithm depends on the following theorem, which dates back to Vincent's theorem in 1836 [START_REF] Vincent | Sur la résolution des équations numériques[END_REF]. The inverse of Th. 4 can be found in [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Collins | Real zeros of polynomials[END_REF][START_REF] Mignotte | Mathematics for computer algebra[END_REF]. It is a very interesting question whether the one and two circle theorems (c.f [START_REF] Krandick | New bounds for the Descartes method[END_REF] and references therein), employed in the analysis of the Descartes/Bernstein algorithm [START_REF] Collins | Polynomial real root isolation using Descartes' rule of signs[END_REF], can also be applied and possibly improve the complexity of the CF algorithm. The version of the theorem that we present is due to Alesina and Galuzzi [START_REF] Alesina | A new proof of Vincent's theorem[END_REF] and improves the conditions of all the previous versions [START_REF] Akritas | There is no "Uspensky's method[END_REF][START_REF] Akritas | An implementation of Vincent's theorem[END_REF][START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Uspensky | Theory of Equations[END_REF].

1. V ar(A a ) ≥ V ar(A b ), 2. #{γ ∈ (a, b)|A(γ) = 0} ≤ V ar(A a ) -V ar(A b ), and 3. #{γ ∈ (a, b)|A(γ) = 0} ≡ V ar(A a ) -V ar(A b ) mod 2. Algorithm 1: CF(A, M ) Input: A ∈ Z[X], M (X) = kX+l mX+n , k, l, m, n ∈ Z Output: A list of isolating intervals if A(0) = 0 then 1 OUTPUT Interval( M (0), M (0)) ; 2 A ← A(X)/X; 3 CF(A, M ); 4 V ← Var(A); 5 if V = 0 then return ; 6 if V = 1 then 7 OUTPUT Interval( M (0), M (∞)); 8 return ; 9 b ← PLB(A) // PLB ≡ PositiveLowerBound ; 10 if b > 1 then A ← A(b + X), M ← M (b + X) ; 11 A 1 ← A(1 + X), M 1 ← M (1 + X) ; 12 CF(A 1 , M 1 ) // Looking for real roots in (1, +∞); 13 A 2 ← A( 1 1+X ), M 2 ← M ( 1 1+X ) ; 14 CF(A 2 , M 2 ) //
Theorem 4 [START_REF] Alesina | A new proof of Vincent's theorem[END_REF] Let A ∈ Z[X] be square-free and let ∆ > 0 be the separation bound. Let n be the smallest index such that

F n-1 F n ∆ > 2 √ 3 ,
where F n is the n-th Fibonnaci number. Then the map X → [c 0 , c 1 , . . . , c n , X], where c 0 , c 1 , . . . , c n is an arbitrary sequence of positive integers, transforms A(X) to A n (X), whose list of coefficients has no more than one sign variation.

Notice that in the previous theorem the conditions do not depend on the degree of the polynomial. Moreover, a similar theorem holds for non square-free polynomials but we will not use it for the analysis of the CF algorithm. The extension of Vincent's theorem to the INRIA non square-free case is due to Wang [START_REF] Wang | A method for isolating roots of algebraic equations[END_REF], see also [START_REF] Chen | A new algorithm for the isolation of real roots of polynomial equations[END_REF] and for an improved version and historical references see [START_REF] Alesina | A new proof of Vincent's theorem[END_REF].

Theorem 5 [START_REF] Alesina | A new proof of Vincent's theorem[END_REF][START_REF] Wang | A method for isolating roots of algebraic equations[END_REF] Let A ∈ Z[X], not necessarily square-free, with deg(A) = d and let ∆ > 0 be the separation bound. Let k be the smallest index such that

F 2 k-1 ∆ > 1, m be the smallest integer such that m > 1 2 log φ d and n = k + m. Then the map X → [c 0 , c 1 , . . . , c n , X], where c 0 , c 1 , . . . , c n is an arbitrary sequence of positive integers, transforms A(X) to A n (X), that has V ar(A n ) ≥ 0 sign variations. If V ar(A n ) > 0 then A n has a unique positive real root of multiplicity V ar(A n ).
The previous extension of Vincent's theorem implies that Descartes' rule of sign can be used to isolate the real roots of non square-free polynomials and to compute their multiplicities, contrary to what it is believed up to now. Moreover, Th. 5 implies that Descartes' rule of sign can be used for polynomials with multiprocessing floating point and/or interval coefficients. We plan to report on the consequences of Th. 5 in a future work. Of course the obstacle to all the previous remarks is that we have to perform iterations up to the theoretical separation bound, which is a very bad overestimation of the actual one.

In our analysis we will assume that the input polynomial is square-free, except if explicitly stated otherwise, since we compute the multiplicities of the real roots differently. Thus we will rely on Th. 4 to isolate the positive real roots of a square-free polynomial A. In order to isolate the negative roots we perform the transformation X → -X, so in what follows we will consider only the positive real roots of A.

Vincent's variant of the CF algorithm goes as follows: A polynomial A is transformed to A 1 by the transformation X → 1 + X and if V ar(A 1 ) = 0 or V ar(A 1 ) = 1 then A has 0, resp. 1, real root greater than 1 (Th. 1). If V ar(A 1 ) < V ar(A) then (possibly) there are real roots of A in (0, 1), due to Budan's theorem (Th. 3). A 2 is produced by applying the transformation X → 1/(1 + X) to A. If V ar(A 2 ) = 0 or V ar(A 2 ) = 1 then A has 0, resp. 1, real root less than 1 (Th. 1). Uspensky's [START_REF] Uspensky | Theory of Equations[END_REF] variant of the algorithm (see also [START_REF] Rosen | A continued fraction algorithm for approximating all real polynomial roots[END_REF]) at every step produces both polynomials A 1 and A 2 probably, as Akritas states [START_REF] Akritas | There is no "Uspensky's method[END_REF], because he was unaware of Budan's theorem. In both variants, if the transformed polynomial has more than one sign variations, we repeat the process.

We may consider the process of the algorithm as an infinite binary tree in which the root corresponds to the original polynomial A. The branch from a node to a right child corresponds to the map X → X + 1, while to the left child to the map X → 1 1+X . Notice that a sequence of c transformations X → 1+X followed by one of the type X → 1/(1+X) is equivalent to two transformations, one of the type X → c+1/X followed by X → 1+X. Thus Vincent's algorithm (and Uspensky's) results to a sequence of transformations like the one described in Th. 4, and so the leaves of the binary tree that we considered hold (transformed) polynomials that have no more than one sign variations, if Th. 4 holds. Akritas [START_REF] Akritas | An implementation of Vincent's theorem[END_REF][START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF] replaced a series of X → X + 1 transformations by X → X + b, where b is the positive lower bound (PLB) on the positive roots of the tested polynomial. This was computed by Cauchy's bound [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF]. This way, the number of steps is polynomial and the complexity is in O B (d 5 τ 3 ).

RR n 6059

However, it is not clear whether or how the analysis takes into account that the coefficient bit size increases after a shift. Another issue is to bound the size of the b's.

For these polynomials that have one sign variation we still have to find the interval where the real root of the initial polynomial A lies. Consider a polynomial A n that corresponds to a leaf of the binary tree that has one sign variation. Notice that A n is produced after a transformation as in Th. 4, using positive integers c 0 , c 1 , . . . , c n . This transformation can be written in a more compact form using the convergents

M : X → P n X + P n-1 Q n X + Q n-1 , (3)
where Pn-1 Qn-1 and Pn Qn are consecutive convergents of the continued fraction [c 0 , c 1 , . . . , c n ]. Notice that (3) is a Möbius transformation, see [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF] for more details. Since A n has one sign variation it has one and only one real root in (0, ∞), so in order to obtain the isolating interval for the corresponding real root of A we evaluate the right part of Eq. ( 3) once over 0 and once over ∞. The (unordered) endpoints of the isolating interval are Pn-1

Qn-1 and Pn Qn . The pseudo-code of the CF algorithm is presented in Alg. 1. Notice that the Interval function orders the endpoints of the computed isolating interval and that PLB(A) computes a lower bound on the positive roots of A. The initial input of the algorithm is a polynomial A(X) and the trivial transformation M (X) = X. We need the functional M in order to keep track of the transformations that we perform so that to derive the isolating intervals. Notice that Line 15 is to be executed only when V ar(A 1 ) < V ar(A 2 ), but in order to simplify the analysis we omit this, since it only doubles the complexity.

The complexity of the CF algorithm

The complexity of the CF algorithm depends on the number of transformations and the cost of each. However, special care should be taken since after each transformation the bit size of the polynomial coefficients increases.

Let disc(A) be the discriminant and lead (A) the leading coefficient of

A. Mahler's measure of a polynomial A is M(A) = | lead (A) | d i=1 max {1, |γ i |},
where γ i are all the (complex) roots of A [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF][START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Mignotte | Polynomials: An algorithmic approach[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF]. Moreover M(A) ≤ 2 τ √ d + 1. We prove the following theorem, which is based on a theorem by Mignotte [START_REF] Mignotte | Mathematics for computer algebra[END_REF], thus extending [START_REF] Davenport | Cylindrical algebraic decomposition[END_REF][START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF].

Theorem 6 Let A ∈ Z[X], with deg(A) = d and L (A) = τ . Let Ω be any set of k couples of indices (i, j) such that 1 ≤ i < j ≤ d and let the non-zero (complex) roots of A be 0 < |γ 1 | ≤ |γ 2 | ≤ • • • ≤ |γ d |. Then 2 k M(A) k ≥ (i,j)∈Ω |γ i -γ j | ≥ 2 k-d(d-1) 2 M(A) 1-d-k disc(A)
Proof. Consider the multiset Ω = {j|(i, j) ∈ Ω}, where |Ω| = k. We use the inequality

∀ a, b ∈ C |a -b| ≤ 2 max {|a|, |b|}, (4)
INRIA and the fact [START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Mignotte | Polynomials: An algorithmic approach[END_REF] that for any root of A, 1 M(A) ≤ |γ i | ≤ M(A). In order to prove the left inequality

(i,j)∈Ω |γ i -γ j | ≤ 2 k j∈Ω |γ j | ≤ 2 k max j∈Ω |γ j | k ≤ 2 k M(A) k .
Recall [START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF]

that disc(A) = lead (A) 2d-2 i<j (γ i -γ j ) 2 .
For the right inequality we consider the absolute value of the discriminant of A, i.e

| disc(A)| = | lead (A) | 2d-2 i<j |γ i -γ j | 2 = | lead (A) | 2d-2 (i,j)∈Ω |γ i -γ j | 2 (i,j) / ∈Ω |γ i -γ j | 2 ⇔ | disc(A)| = | lead (A) | d-1 (i,j)∈Ω |γ i -γ j | (i,j) / ∈Ω |γ i -γ j |
We consider the product (i,j) / ∈Ω |γ i -γ j | and we apply d(d-1)

2

-k times inequality (4), thus

(i,j) / ∈Ω |γ i -γ j | ≤ 2 d(d-1) 2 -k |γ 1 | 0 |γ 2 | 1 • • • |γ d | d-1 ( j∈Ω |γ j |) -1 ≤ 2 d(d-1) 2 -k M(A) d-1 | lead (A) | 1-d M(A) k (5)
where we used the inequality

|γ 1 | 0 |γ 2 | 1 • • • |γ d | d-1 ≤ |M(A)/ lead (A) | d-1
, and the fact [START_REF] Mignotte | Mathematics for computer algebra[END_REF] that, since ∀i,

|γ i | ≥ M(A) -1 , we have j∈Ω |γ j | ≥ |γ 1 | k ≥ M(A) -k . Thus we conclude that (i,j)∈Ω |γ i -γ j | ≥ 2 k-d(d-1) 2 M(A) 1-d-k | disc(A)|.
2 A similar theorem but with more strict hypotheses on the roots first appeared in [START_REF] Davenport | Cylindrical algebraic decomposition[END_REF], see also [START_REF] Johnson | Algorithms for Polynomial Real Root Isolation[END_REF], and the conditions were generalized in [START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF]; namely in order for the bound [START_REF] Davenport | Cylindrical algebraic decomposition[END_REF][START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF] to hold the sets of indices i and j should be rearranged such that they form an acyclic graph where each node has out-degree at most one. The bound of Th. 6 has a factor 2 d 2 instead of d d in [START_REF] Davenport | Cylindrical algebraic decomposition[END_REF][START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF][START_REF] Johnson | Algorithms for Polynomial Real Root Isolation[END_REF], which plays no role when d = O(τ ) or when the notation with N is used. Moreover, we loosen the hypotheses of the theorem and thus all the proofs concerning the number of steps of the subdivision-based solvers [START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF][START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF] are dramatically simplified. Possibly a more involved proof of Th. 6 may eliminate this factor using [START_REF] Mignotte | On the Distance Between the Roots of a Polynomial[END_REF].

Remark 7 There are two simple, however crucial, observations about Th. 4. When the transformed polynomial has one sign variation, then the interval with endpoints Pn-1

Qn-1 = [c 0 , c 1 , . . . , c n-1 ] and Pn Qn = [c 0 , c 1 , . . . , c n ] (possibly unordered) isolates a positive real root of A, say γ i . Then, in order for Th. 4 to hold, it suffices to consider, instead of ∆, the quantity |γ i -γ ci |, where γ ci is the (complex) root of A closest to γ i . When the transformed polynomial has no sign variation and [c 0 , c 1 , . . . , c n ] is the continued fraction expansion of the (positive) real part of a complex root of A, say γ i , then again it suffices to replace ∆ by |γ i -γ ci |.

Theorem 8

The CF algorithm performs at most O(d 2 + dτ ) transformation steps.

Proof. Let 0 < |γ 1 | ≤ |γ 2 | ≤ • • • ≤ |γ k |,
k ≤ d be the (complex) roots of A with positive real part and let γ ci denote the root of A that is closest to γ i .

We consider the binary tree T generated during the execution of the CF algorithm. The number of steps of the CF algorithm corresponds to the number of nodes in T , which we denote by #(T ). We use some arguments and the notation from [START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF] in order to prune the tree.

With each node v of T we associate a Möbius transformation M v : X → kX+l mX+n , a polynomial A v and implicitly an interval I v whose unordered endpoints can be found if we evaluate M v on 0 and on ∞. Recall that A v is produced after M v is applied to A. The root of T is associated with A, M (X) = X (i.e k = n = 1, l = m = 0) and implicitly with the interval (0, ∞).

Let a leaf u of T be of type-i if its interval I u contains i ≥ 0 real roots. Since the algorithm terminates the leaves are of type-0 or type-1. We will prune certain leaves of T so as to obtain a certain sub-tree T ′ where it is easy to count the number of nodes. We remove every leaf that has a sibling that is not a leaf. Now we consider the leaves that have a sibling that is also a leaf. If both leaves are of type-1, we arbitrary prune one of them. If one of them is of type-1 then we prune the other. If both leaves are of type-0, this means that the polynomial on the parent node has at least two sign variations and thus that we are trying to isolate the (positive) real part of some complex root. We keep the leaf that contains the (positive) real part of this root. And so #(T ) < 2 #(T ′ ). Now we consider the leaves of T ′ . All are of type-0 or type-1. In both cases they hold the positive real part of a root of A, the associated interval is

|I v | ≥ |γ i -γ ci | (Rem. 7)
and the number of nodes from a leaf to the root is n i , which is such that the hypothesis of Th. 4 is satisfied. Since n i is the smallest index such that the hypothesis of Th. 4 holds, if we reduce n i by one then the inequality does not hold. Thus

F ni-2 F ni-1 |γ i -γ ci | ≤ 2 √ 3 ⇒ φ 2ni-5 |γ i -γ ci | < 2 √ 3 ⇒ n i < 2 - 1 2 lg |γ i -γ ci |.
We sum over all n i to bound the nodes of T ′ , thus

#(T ′ ) ≤ k i=1 n i ≤ 2k - 1 2 k i=1 lg |γ i -γ ci | ≤ 2k - 1 2 lg k i=1 |γ i -γ ci |. (6)
In order to apply Th. 6 we should rearrange k i=1 |γ i -γ ci | so that the requirements on the indices of roots are fulfilled. This can not be achieved when symmetric products occur and thus the worst case is when the product consists only of symmetric products i.e k/2 i=1 |(γ j -γ cj )(γ cj -γ j )|. Thus we consider the square of the inequality of Th. 6 taking k

2 instead of k and disc(A) ≥ 1 (since A is square-free), thus k i=1 |γ i -γ ci | ≥ 2 k 2 -d(d-1) 2 M(A) 1-d-k 2 2 -lg k i=1 |γ i -γ ci | ≤ d 2 -d -k + (2d + k -2) lg M(A) (7)

INRIA

Eq. ( 6) becomes #(T

′ ) < 2k + d 2 -d -k + (2d + k -2) lg M(A). However, for Mahler's measure it is known that M(A) ≤ 2 τ √ d + 1 ⇒ lg M(A) ≤ τ + lg d, for d ≥ 2, thus #(T ′ ) ≤ 2k + d 2 -d -k + (2d + k -2)(τ + lg d). Since #(T ) < 2 #(T ′ ) and k ≤ d, we conclude that #(T ) = O(d 2 + d τ + d lg d). 2

Real root isolation

To complete the analysis of the CF algorithm we have to compute the cost of every step that the algorithm performs. In the worst case every step consists of a computation of a positive lower bound b (Line 10) and three transformations, X → b + X, X → 1 + X and X → 1 1+X (Lines 11, 12 and 14 in Alg. 1). Recall, that inversion can be performed in O(d). Thus the complexity is dominated by the cost of the shift operation (Line 11 in Alg. 1) if a small number of calls to PLB is needed in order to compute a partial quotient. We will justify this in Sec. 4.2. In order to compute this cost a bound on

L (c k ) b k , 0 ≤ k ≤ m i is needed, see Eq. (2).
For the analysis of the CF algorithm we will need the following:

Theorem 9 (Fast Taylor shift) [48] Let A ∈ Z[X], with deg(A) = d and L (A) = τ and let a ∈ Z, such that L (a) = σ. Then the cost of computing B = A(a + X) ∈ Z[X] is O B (M d 2 lg d + d 2 σ + dτ ). Moreover L (B) = O(τ + dσ).
b i ] = O(h) Since h ≤ #(T ) = O(d 2 + dτ ) (Th. 8), the (expected) worst case cost of step h is O B (M d 2 lg d + dτ + d 2 (d 2 + dτ ) ) or O B (d 2 (d 2 + dτ )).
Finally, multiplying by the number of steps, #(T ), we conclude that the overall complexity is

O B (d 6 + d 5 τ + d 4 τ 2 ), or O B (d 4 τ 2 ) if d = O(τ ), or O B (N 6 ), where N = max {d, τ }.
Now let us isolate, and compute the multiplicities, of the real roots of A in ∈ Z[X], which is not necessarily square-free, with deg(A in ) = d and L (A in ) = τ . We use the technique from [START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF] and compute the square-free part A of A in using Sturm-Habicht sequences in

O B (d 2 τ ). The bit size of A is L (A) = O(d + τ ).
Using the CF algorithm we isolate the positive real roots of A and then, by applying the map X → -X, we isolate the negative real roots. Finally, using the square-free factorization of A in , which can be computed in O B (d 3 τ ), it is possible to find the multiplicities in O B (d 3 τ ).

The previous discussion leads to the following theorem. The same complexity bound can be achieved for non square-free polynomials if instead of using Sturm-Habicht sequences in order to compute to the square-free part of the polynomial and compute the multiplicities, we rely on Th. 5.

Rational roots and PLB (Positive Lower Bound) realization

This section studies a way to compute a lower bound on the positive roots and presents its efficiency and accuracy. It seems that this is the standard approach in CF algorithms, though it is seldom, if at all, discussed.

There are two issues that we have to discuss further. The first one concerns the rational numbers. If the polynomial A has (only) rational real roots then their continued fraction expansion neither follows the Gauss-Kuzmin distribution nor Khintchine's law. However, recall that if p q is a root of A then p divides a 0 and q divides a d , thus in the worst case L (p/q) = O(τ ) and so the rational roots are isolated fast among themselves. Treating them as real algebraic numbers leads to an overestimation of the number of iterations.

The second issue concerns the number of calls of function plb that must be applied in order to compute a partial quotient. We made the assumption that this number of calls is small. In practice this is always the case, except when the polynomial has only rational real roots, of great magnitude, well separated and we are interested in the practical complexity. In this case function PLB must be applied many times in order to compute a partial quotient. Richtmyer et al. [START_REF] Richtmyer | Continued fraction expansions of algebraic numbers[END_REF] in order to overcome this situation perform a small number of Newtonlike iterations in order to get a good approximation of the partial quotient. In [START_REF] Akritas | Implementation of real root isolation algorithms in Mathematica[END_REF], see also [START_REF] Akritas | An implementation of Vincent's theorem[END_REF][START_REF] Akritas | A comparative study of two real root isolation methods[END_REF], the problem was solved partially by applying the map X → bX, where b is the computed positive root bound, when b ≥ 16. This is what we do in our implementation.

The assumption that the number of calls to plb is small enough, is strengthened by (1), since it implies that the probability that a partial quotient is of magnitude ≤ 10 is ∼ 0.87. This is why in practice the partial quotients are of very small magnitude. Moreover, the relation

γ - P n Q n < 1 c n+1 Q 2 n ,
implies that the appearance of a partial quotient of an extra-ordinary big magnitude means that the previous approximation of the algebraic number was extremely good.

However, the previous discussion does not provide a theoretical explanation. We will use results about the tightness of the positive root bounds in order to support our assumption.

Recall that a lower bound on the positive roots of a polynomial is computed as the inverse of the upper bound on the positive roots of the reciprocal polynomial. Thus in what follows we will consider only upper bounds for the positive roots. The bound that we will consider,

INRIA

and that we also use in our implementation of plb, is

B 2 (A) := 2 max a k <0 a k a d 1 d-k , (8)
where 0 ≤ k < d, which is due to [START_REF] Kioustelidis | Bounds for the positive roots of polynomials[END_REF], see also [START_REF] Johnson | Algorithms for Polynomial Real Root Isolation[END_REF][START_REF] Knuth | Seminumerical Algorithms, volume 2 of The Art of Computer Programming[END_REF]. Notice that B 2 is a bound for the positive roots only and not a bound for all the (complex) roots of the polynomial. For such bounds, the reader may refer to e.g [START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Mignotte | Polynomials: An algorithmic approach[END_REF][START_REF] Van Der Sluis | Upper bounds for the roots of polynomials[END_REF]. For other bounds on the positive roots the reader may refer to [START_REF] Hong | Bounds for absolute positiveness of multivariate polynomials[END_REF][START_REF] Kioustelidis | Bounds for the positive roots of polynomials[END_REF][START_REF] Stefanescu | New bounds for the positive roots of polynomials[END_REF].

If instead of B 2 , we compute a bound B 1 , taking into account all the coefficients then from [START_REF] Van Der Sluis | Upper bounds for the roots of polynomials[END_REF] B 1 is at most d times the biggest root of A. Since B 2 is a smaller bound we can conclude that γ ≤ B 2 ≤ B 1 ≤ d • γ. A similar result can be obtained if we consider the bound of Hong [START_REF] Hong | Bounds for absolute positiveness of multivariate polynomials[END_REF] or any other bound that guarantees that it is O(d) times away from the biggest root, see e.g [START_REF] Henrici | Applied and computational complex analysis[END_REF][START_REF] Mignotte | Mathematics for computer algebra[END_REF][START_REF] Mignotte | Polynomials: An algorithmic approach[END_REF].

Last, but not least, we have to mention that the implementation of B 2 requires O(d) arithmetic operations [START_REF] Akritas | Elements of Computer Algebra with Applications[END_REF][START_REF] Krandick | Isolierung reeller nullstellen von polynomen[END_REF][START_REF] Van Der Sluis | Upper bounds for the roots of polynomials[END_REF] and as van der Sluis [START_REF] Van Der Sluis | Upper bounds for the roots of polynomials[END_REF] says for B 1 and thus for B 2 , this bound "is to be recommended among all" because of its simplicity and the good quality of its results.

If b is the computed positive root bound and γ is the closest positive real root of A to it, which we are trying to isolate, then, from the previous discussion, it holds that b ≤ γ ≤ d b.

Recall that the lower bound on the positive roots is obtained as an upper bound on the positive real roots of the reciprocal polynomial. One integer in the interval [b, d b] is the partial quotient of γ that we actually want to compute. We can perform binary search based on Budan's theorem (Th. The previous discussion implies that at every step of the algorithm we must perform, additionally O(lg d) shift operations, instead of at most 2 that we assumed, in order to compute a partial quotient. Thus, the complexity of the algorithm should be multiplied by a factor lg d, which does not change the bound O B (d 6 + d 4 τ 2 ).

In practice the tightness of the positive root bounds is usually very good.

Better complexity bounds

A closer look to the proof of Th. 8 reveals that in order to derive the number of steps of the CF algorithm we do not depend on an interval that initially contains all the real roots.

Notice that this dependence is intrinsic for the subdivision algorithms [START_REF] Eigenwillig | Almost tight recursion tree bounds for the descartes method[END_REF][START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF]. This will allow us to improve the complexity of the CF algorithm by spreading away the roots. We consider the square-free polynomial A and we apply the homothetic transformation X → X/2 ℓ(d+τ ) , where ℓ is a constant specified by [START_REF] Brent | A Comparative Study of Algorithms for Computing Continued Fractions of Algebraic Numbers[END_REF]. The transformed polynomial, say C, has bit size O(τ + ℓd 2 + ℓdτ ) and its roots β j are the roots of A multiplied by 2 ℓ(d+τ ) , i.e

β i = 2 ℓ(d+τ ) γ i , (9)
where γ i are the roots of A and 1 ≤ i ≤ d. Evidently it suffices to isolate the real roots of C.

We will use the notation of the proof of Th. 8. Let k 1 be the number roots of C with positive real part and k 2 those with negative real part. Notice that k 1 + k 2 = d. Following the proof of Th. 8, see Eq. ( 6), the number of steps that the CF algorithm must perform in order to isolate the real roots of C is

#(T ′ ) ≤ k1 i=1 n i + k2 j=1 n j ≤ 2k 1 - 1 2 k1 i=1 lg |β i -β ci | + 2k 2 - 1 2 k2 j=1 lg |β j -β cj | ≤ 2d - 1 2 lg d i=1 |β i -β ci |. (10)
If we consider the product term of the previous equation and (9) then

d i=1 |β i -β ci | = 2 ℓd 2 +ℓdτ d i=1 |γ i -γ ci |.
Combining the previous equation with [START_REF] Bailey | On the Khintchine Constant[END_REF] we have

-lg d i=1 |β i -β ci | ≤ d 2 + (3d -2)τ -2d -2 lg d + 3d lg d -ℓ d 2 + dτ . (11)
We want to specify the value of ℓ in such way so as to eliminate the quantities of the form d 2 and dτ from Eq. [START_REF] Bombieri | Continued fractions of algebraic numbers[END_REF]. By elementary calculus we see that ℓ should be

ℓ = (3d -2)τ + d 2 -2d dτ + d 2 . ( 12
)
If we make the assumption that d = O(τ ) then, using this result and combining Eq. ( 10) and ( 11 The previous variant of the CF algorithm has small practical interest because applying the homothetic transformation X → X/2 ℓ(d+τ ) to the polynomial increases its bit size a lot.

INRIA

However, to the best of our knowledge this is the first complexity bound, even using average case analysis, that matches the complexity bounds of the numerical algorithms [START_REF] Pan | Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding[END_REF][START_REF] Pan | Solving a polynomial equation: Some history and recent progress[END_REF][START_REF] Schönhage | The fundamental theorem of algebra in terms of computational complexity[END_REF].

We conjecture that the expected complexity of the subdivision solvers, i.e Descartes/Bernstein and Sturm is also the same, but we will report on this in a future work.

Implementation and experiments

We have implemented the cf algorithm in synaps2 [START_REF] Mourrain | SYNAPS, a library for symbolic-numeric computation[END_REF], which is a C++ library for symbolicnumeric computations that provides data-structures, classes and operations for univariate and multivariate polynomials, vector and matrices. Our code will be included in the next major public release of synaps. The implementation is based on the integer arithmetic of gmp3 (v. 4.1.4) and uses only transformations of the form X → 2 β X and X → X + 1 to benefit from the fast implementations that are available in gmp. However, our implementation follows the generic programming paradigm, thus any library that provides arbitrary precision integer arithmetic can be used instead of gmp.

We restrict ourselves to square-free polynomials of degree ∈ {100, 200, . . . , 1000}. Following [START_REF] Rouillier | Efficient isolation of polynomial's real roots[END_REF], the first class of experiments concerns well-known ill-conditioned polynomials namely: Laguerre (L), first (C1) and second (C2) kind Chebyshev, and Wilkinson (W) polynomials. We also consider Mignotte (M1) polynomials X d -2(101X -1) 2 , that have 4 real roots but two of them very close together, and a product X d -2(101X -1) 2 X d -2((101 + 1 101 )X -1) 2 of two such polynomials (M2) that has 8 real roots. Finally, we consider polynomials with random coefficients (R1), and monic polynomials with random coefficients (R2) in the range [-1000, 1000], produced by maple, using 101 as a seed for the pseudo-random number generator.

We performed experiments against rs4 , which seems to be one of the fastest available software for exact real root isolation. It implements a subdivision-based algorithm using Descartes' rule of sign with several optimizations and symbolic-numeric techniques [START_REF] Rouillier | Efficient isolation of polynomial's real roots[END_REF]. Note that we had to use rs through its maple interface. Timings were reported by its internal function rs_time().

We also test aberth [START_REF] Bini | Numerical computation of polynomial zeros by means of Aberth's method[END_REF][START_REF] Bini | Design, analysis, and implementation of a multiprecision polynomial rootfinder[END_REF], which a numerical solver with unknown (bit) complexity but very efficient in practice, available through synaps. In particular, it uses multi-precision floats and provides a floating-point approximation of all the complex roots. Since aberth is a numerical solver it approximates the roots up to a desired accuracy. Even though we tuned aberth to search for roots on the real axis only, unfortunately, we were not always able to tune its behavior in order to produce the correct number of real roots in all the cases, i.e to specify the output precision.

In synaps, there are several univariate solvers, based on Sturm sequences, Descartes' rule of sign, Bernstein basis, etc (see [START_REF] Emiris | Real Algebraic Numbers: Complexity Analysis and Experimentation[END_REF] for details and experimental results). cf is clearly faster than all these solvers, therefore we do not report on these experiments. In particular, the large inputs used here are not tractable by the Sturm-sequence solver in synaps, and this is also the case for another implementation of the Sturm-sequence solver in core 5 . So, in Table 1, we report experiments with cf, rs, aberth, where the timings are in seconds. The asterisk (*) denotes that the computation did not finish after 12000s. The experiments were performed on a 2.6 GHz Pentium with 1 GB RAM, and our code was compiled using g++ 3.3 with options -O3 -DNDEBUG.

For (M1) and (M2), there are rational numbers with a very simple continued fraction expansion that isolate the real roots which are close. These experiments are extremely hard for rs. On (M1), aberth is the fastest and correctly computes all real roots, but on (M2), which has 4 real roots close together, it is slower than cf. cf is advantageous on (W) since, as soon as a real root is found, transformations of the form X → X + 1 rapidly produce the other real roots. We were not able to tune aberth on (W). For (L), (C1) and (C2), cf is clearly faster than rs, while we were not able to appropriately tune aberth to produce the correct number of real roots. The polynomials in (R1) and (R2) have few and well separated real roots, thus the semi-numerical techniques in rs are very effective. To be more specific, rs isolates all roots using only 63 bits of accuracy (this information was extracted using the function rs_verbose( 1)). However, even in this case, cf is comparable to rs. aberth is even faster on these experiments (see Table 1). We have to mention as F. Rouillier pointed out to us that rs can about 30% faster in (L), (C1) and (C2) if we use it with the (non-default) option precision=0.

We finally tested a univariate polynomial that appears in the Voronoi diagram of ellipses [START_REF] Emiris | The predicates for the Voronoi diagram of ellipses[END_REF]. The polynomial has degree 184, coefficient bit size 903, and 8 real roots. cf solves it in 0.12s, rs in 0.3s and aberth in 1.7s.

In short, CF is complete, simple to use and is at least as efficient as the state of the art. There are ways to improve our solver. First, instead of exact integer arithmetic we may use semi-numerical techniques like those in rs [START_REF] Rouillier | Efficient isolation of polynomial's real roots[END_REF]. These techniques may be based on interval arithmetic.

Initially

  A has degree d and bit size τ . Evidently the degree does not change after a shift operation. Each shift operation by a number of bit size b h increases the bit size of the polynomial by an additive factor d b h , in the worst case (Th. 9). At the h-th step of the algorithm the polynomial has bit size O(τ + d h i=1 b i ) and we perform a shift operation by a number of bit size b h+1 . Th. 9 states that this can be done in O B M d 2 lg d + d 2 b h+1 + d(τ + d h i=1 b i ) or O B M d 2 lg d + dτ + d 2 h+1 i=1 b i . Now we have to bound h+1 i=1 b i . For this we use Eq. (2), which bounds E[b i ]. By linearity of expectation it follows that E[ h+1 i=1

Theorem 10

 10 Let A ∈ Z[X] (not necessarily square-free) such that deg(A) = d > 2 and L (A) = τ . We can isolate the real roots of A and compute their multiplicities in expected time O B (d 6 + d 4 τ 2 ), or O B (N 6 ), where N = max {d, τ }.

  3) in order to compute an interval [c, c + 1] ⊆ [b, d b] such that it contains γ and c ∈ Z is the partial quotient that we are intersted in. Budan's theorem corresponds to 2 polynomial shifts, thus the binary search needs, in order to compute c, at most O(lg d + lg b) shift operations. However, b ≤ c ⇒ L (b) ≤ L (c) = O(1), and since c is a partial quotient in the continued fraction expansion of γ, its magnitude should follow Khintchine, c.f (2).

  ), we conclude that #(T ) = O(d lg d) = O B (d). If we substitute this value of #(T ) in the proof of Th. 10, presented in Sec. 4, and taking into account that the bit size of C is O(τ + ℓd 2 + ℓdτ ) then we conclude that the expected complexity of this variant of the CF algorithm is O B (d 3 τ ).

Table 1 :

 1 Experimental results

			100	200	300	400	500	600	700	800	900	1000
		cf	0.27	2.24	9.14	25.27	55.86	110.13	214.99	407.09	774.22	1376.34
	L	rs	0.65	3.65	13.06	35.23	77.21	151.17	283.43	527.42	885.86	1387.45
		#roots	100	200	300	400	500	600	700	800	900	1000
		cf	0.11	0.85	3.16	8.61	19.67	38.23	77.75	139.18	247.11	414.51
	C1	rs	0.21	1.36	3.80	10.02	23.15	46.02	82.01	150.01	269.35	458.67
		#roots	100	200	300	400	500	600	700	800	900	1000
		cf	0.11	0.77	3.14	8.20	19.28	38.58	73.59	133.52	233.48	386.61
	C2	rs	0.23	1.48	3.80	9.84	23.28	46.34	83.58	146.04	273.00	452.77
		#roots	100	200	300	400	500	600	700	800	900	1000
		cf	0.11	0.76	2.54	6.09	12.07	21.43	34.52	53.35	81.88	120.21
	W	rs	0.09	0.59	2.25	6.34	14.62	29.82	55.47	104.56	179.23	298.45
		#roots	100	200	300	400	500	600	700	800	900	1000
		cf	0.02	0.08	0.21	0.42	0.73	1.19	1.84	2.75	4.16	6.22
	M1	rs	7.83	287.27	1936.48	7328.86	*	*	*	*	*	*
		aberth	0.01	0.04	0.07	0.11	0.12	0.26	0.43	0.37	0.47	0.90
		#roots	4	4	4	4	4	4	4	4	4	4
		cf	0.08	0.43	1.10	2.78	4.71	8.67	18.26	25.28	40.15	60.10
	M2	rs #roots	1.24 8	144.64 8	1036.785 8	4278.275 8	12743.79 8	* 8	* 8	* 8	* 8	* 8
		cf	0.001	0.04	0.07	0.33	0.06	0.37	0.66	0.76	1.03	1.77
	R1	rs aberth	0.026 0.02	0.09 0.03	0.11 0.07	0.68 0.14	0.22 0.21	0.89 0.31	0.95 0.44	0.69 0.51	1.55 0.64	2.09 0.80
		#roots	4	4	2	6	2	4	4	2	4	4
		cf	0.01	0.04	0.08	0.36	0.14	0.38	0.74	0.77	1.24	1.42
	R2	rs aberth	0.05 0.01	0.23 0.05	0.47 0.08	1.18 0.14	0.81 0.23	1.64 0.33	2.68 0.44	3.02 0.55	4.02 0.67	4.88 0.83
		#roots	4	4	4	6	4	4	6	4	6	4

RR n 6059

http://fgbrs.lip6.fr/salsa/Software/ RR n 6059

www-sop.inria.fr/galaad/logiciels/synaps/

www.swox.com/gmp/

fgbrs.lip6.fr/salsa/Software/index.php RR n 6059

cs.nyu.edu/exact/core_pages/ INRIA

Acknowledgments Both authors acknowledge fruitful discussions with Alkiviadis Akritas and Bernard Mourrain. The first author is grateful to Maurice Mignotte for discussions about the separation bound, to Doru Stefanescu for various discussions and suggestions about the bounds of the positive roots of polynomials and to Fabrice Rouillier for various discussions about rs and the experiments. Both authors acknowledge partial support by IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-006413-2 (ACS -Algorithms for Complex Shapes) and by a doctoral research grant by the Greek General Secretariat for Research and Technology under the program ΠEN E∆ 03.