> <\body> <\hide-preamble> >> >> \\\>> <\surround||> <\render-specified-algorithm| >> <|render-specified-algorithm> > |<\doc-note> This paper is part of a project that has received funding from the French \PAgence de l'Innovation de Défense\Q. |||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau, France |>>||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau, France |>>|> Let > be a fixed effective field. The most straightforward approach to compute with an element in the algebraic closure of > is to compute modulo its minimal polynomial. The determination of a minimal polynomial from an arbitrary annihilator requires an algorithm for polynomial factorization over >. Unfortunately, such algorithms do not exist over generic effective fields. They do exist over fields that are explicitly generated over their prime sub-field, but they are often expensive. The dynamic evaluation paradigm, introduced by Duval and collaborators in the eighties, offers an alternative algorithmic solution for computations in the algebraic closure of >. This approach does not require an algorithm for polynomial factorization, but it still suffers from anon-trivial overhead due to suboptimal recomputations. For the first time, we design another paradigm, called directed evaluation, which combines the conceptual advantages of dynamic evaluation with a good worst case complexity bound. |> Let > be an effective field. Here, means that elements of > can be represented by concrete data structures and that algorithms for the field operations are at our disposal, including a zero-test. Effective rings are defined in a similar way. The aim of the present paper is the fast computation with algebraic numbers. We start by recalling various known strategies, including the most prominent one: dynamic evaluation. Our first main problem will be to develop amore efficient variant of dynamic evaluation. We next recall how to represent algebraic numbers using towers of algebraic extensions. Our second main problem is to develop efficient algorithms for computations in such towers. Let > be a monic separable polynomial of degree in >, not necessarily irreducible, and let > represent a root of > in the algebraic closure |\>> of >. Given an algorithm that runs over a generic effective field, consider the question of running efficiently over |]>>. A natural first approach begins with the computation of the defining polynomial of> over>: this essentially corresponds to factoring > into irreducible polynomials. Unfortunately this task is not feasible over a generic field. Of course, when > is explicitly finitely generated over its prime sub-field, such factorizations can be computed. However, no general efficient algorithms ( running in softly linear time) are currently known for this task; see. Another approach consists in computing in |]>> while regarding > as a parameter constrained by |)>=0>. So any element in |]>> is represented by a polynomial in> of degreed>, such that |)>>. With this representation, additions, subtractions and products can easily be performed in /|)>>, with > seen as the class of. On the other hand, testing whether |)>> is zero or not requires us to distinguish the following cases: <\compact> <\itemize> If is the zero polynomial, then |)>> is zero for any root > of >, so the result of the test is \P>\Q; If the resultant |)>> is non-zero, then |)>> is non-zero for any root > of >, so the result of the test is \P>\Q; Otherwise, gcd|)>> is not a constant polynomial and has degree d>. A proper decomposition of > is thus discovered: =g*/g|)>>. We the current computation, into the two following ones: <\itemize> In the first branch, > is subjected to the constraint |)>=0>; in this branch, the result of the zero-test |)>=0> becomes \P>\Q. In the second branch, > is subjected to the constraint /g|)>|)>=0> and the result of the zero-test |)>=0> becomes \P>\Q. If the inverse of |)>> is requested, then we first test if |)>> is zero or not. If is identically zero (in the resulting branch), then an exception is raised; if |)>> is non-zero, then the inverse can be computed from the Bézout relation for and >, which can itself be computed using the extended gcd algorithm. This manner of evaluating a program is called . It finishes after a necessarily finite number of splittings. At the end of all the computations, we obtain a factorization of =\*\*\>, not necessarily into irreducible polynomials, along with one output value for each of the cases when |)>=0> for ,s>. In other words, instead of working with a specific root of>, the program is evaluated for a generic root of >. For this reason, > is sometimes called an : the program is executed as if |]>> were a field, and cases are distinguished only when inconsistencies actually occur during the execution. After a zero test |)>=0> or an inversion > that gives rise to a splitting, the element is enforced to be identically zero or invertible in each branch. Notice that the separability assumption on > is important, since it ensures that and /g> are coprime in the above decomposition =g*/g|)>>. <\example> Let > be a parameter with |)>=0> for \x**\\>, and consider the computation of the gcd of <\equation*> f\y-+\|)>*y+3*\-2*\,g\-1|)>*y-3*-1|)>*y+2*-1|)>. Using dynamic evaluation, this gives rise to three branches, and the result <\equation*> gcd=|||\=0>>|||\-1=0>>|||\-2=0.>>>>> Dynamic evaluation is very attractive from a conceptual point of view, but rather tricky to implement: splittings correspond to non-deterministic control structures that are typically implemented using continuations. Dynamic evaluation is also difficult to analyze from the complexity perspective. In particular, it is hard to determine the amount of computation that can be shared between several branches. At any rate, the worst case complexity of dynamic evaluation is much higher than the number of steps of the program multiplied by the cost of operations in /|)>>. The first aim of this paper is to design an alternative, so-called evaluation strategy, with the same abstract specification, but with a quasi-linear computational complexity in. The key idea is to run the entire program, while systematically opting for the \Pprincipal\Q branch in case of splittings. This principal branch is the one for which the defining polynomial of > is maximal. At every splitting, we also store the defining polynomial for the other \Presidual\Q branch. Once the computation for the principal branch has been completed, we recursively apply the same algorithm for each residual branch, on the reduced input data modulo the corresponding defining polynomial. The required reductions are computed simultaneously for all residual branches, using a fast divide-and-conquer algorithm for multi-modular reduction. We have outlined above how to compute with a single algebraic parameter > using the dynamic evaluation strategy. More generally, one may wish to compute with a finite number of parameters ,\,\> that are introduced successively as follows: > is subjected to the constraint |)>=0> for some monic polynomial \\|]>>>, then > is subjected to |)>=0> with > monic in |]>|]>>, then > is subjected to |)>=0> with > monic in ,\|]>|]>>, and so on. The second aim of the present paper is the design of fast algorithms for computing dynamically in ,\,\|]>> as if it were a field. The main difficulties arise when is allowed to be arbitrarily large. The parameters ,\,\> naturally induce a of effective algebraic extensions <\equation*> \=\\\\\\\\\, where <\eqnarray*> >|>|>>|>|>||]>/|)>|)>,for >i=1,\,t.>>>> The parameter > corresponds to the class of > in > for ,t>. A tower of this type is written |)>t>> and we call its . Throughout this paper, we write \deg \> and d*\*d>. The > are called the of the tower, and its . Elements in > are naturally represented by univariate polynomials in> over> of degreed>. In order to reduce computational costs, it will be convenient to assume that the tower is in the sense that ,\|)>=1> and that we have explicit Bézout cofactors ,\\\|]>> with *\+\*\=1> for ,t>. In particular, each |\>\\> is reduced. This means that |\>\\> contains no non-zero nilpotent elements or, equivalently, that > is a product of separable field extensions of >. Towers of algebraic extensions are related to \Ptriangular sets\Q. In fact, we may see the preimage of > over> as amultivariate polynomial > in ,\,x|]>> such that > has degree > in>, degrees d> in > for ,i-1>, and |)>=T,\,\,x|)>>. The sequence|)>t>> then forms a special regular case of a . The separability of > translates into the requirement that ,\,\,x|)>> is separable for all roots > of ,\,\,x|)>> for ,i-1>. The second main aim of this paper is to generalize the directed evaluation strategy from the univariate case, while ensuring that the complexity remains bounded by the number of steps in our algorithm multiplied by >> (which corresponds roughly speaking to the cost of arithmetic operations in the tower). Intuitively speaking, we use the univariate strategy in a recursive fashion, but the analysis becomes far more technical due to the fact that splittings can occur at any level of the tower. This difficulty will be countered through the development of suitable data structures. Before we discuss complexity issues of dynamic evaluation and tower computations in more detail, it is useful to introduce various standard notations. We often use the notation: (g(n))> means that >>; see25, section7> for technical details. The notation > means that there exist 0> such that \c*g> for sufficiently large. The least integer larger or equal to is written |x|\>>; the largest one smaller or equal to is written |x|\>>. Given an effective ring >, we use >> as a notation for the cost of multiplying two polynomials of degree d>, in terms of the number of operations in >. It is known that >=O>. We will also denote <\equation*> \d>\\\deg P\d|}>. In particular, given =\/|)>> for some monic polynomial \\> of degree , elements in > may be represented as classes of polynomials in d>> modulo >, additions in> require additions in >, whereas multiplications in > can be done using >|)>> ring operations in >. We let \3> denote an exponent such that two n> matrices over a commutative ring> can be multiplied with >|)>> operations in >. The constant\2> denotes another exponent such that a rectangular > matrix over a commutative ring > can be multiplied with a square \> matrix with>|)>> operations in>. Le Gall has shown in that one may take \2.373>; Huang and Pan have shown in that one may take \1.667>>. Throughout this paper, in order to simplify complexity analyses, we assume that \2> and \>. Recall that an element \\> is said to be if \\|]>>. If |\>\\> is a reduced |\>>algebra, then it is well known that a sufficiently generic >-linear combination of ,\,\> is a primitive element of >. It may thus seem odd, at first sight, to manipulate towers |)>t>> of height 2> whenever an isomorphic algebra |]>> exists. The problem is that both the computations of primitive elements and conversions between representations are usually expensive. Over a general field >, no efficient algorithm is currently known for finding a primitive element together with its minimal polynomial >, and polynomials \\d>> such that =\|)>> for ,t>. It is known that this problem can efficiently be reduced to a multivariate version of the problem of modular composition using a randomized Las Vegas algorithm. The corresponding conversions between tower and primitive element representations can also be done using modular composition. All this is a consequence of the transposition principle and Le Verrier's method; we refer to for more details. Unfortunately, no softly linear algorithm is known for modular composition over a generic field, although efficient algorithms have recently been designed for specific cases. If > is a finite field, then Kedlaya\UUmans and followers have established almost optimal theoretical bit complexity bounds. Without primitive elements, using a naive induction on , the multiplication in > can be performed in time |)>> for some constant 1>. It is well known that, for a sufficiently large constant 1>, such products can actually be carried out in time *d*log d*log log d|)>> using Kronecker substitution; see for instance8>. If many of the individual degrees > are small, then can become as large as , which leads to an overall complexity bound of the form >>. Unfortunately, this bound is far from linear if is much larger than . Lebreton has shown that one may take ; see and2.4>. Substantial improvements for the value of seem difficult to achieve, and it might not even be possible to reach values that are arbitrarily close to. An alternative approach for efficient computations in a given tower is to produce an equivalent, so-called tower of small height, such that conversions between both towers are reasonably cheap. This approach was first proposed in: when the > are all irreducible, we have shown how to multiply elements in > with >|)>> operations in>, for any fixed real\0>. Dynamic evaluation has been developed by Della Dora, Dicrescenzo and Duval as a way to compute with algebraic parameters without irreducible factorizations. The approach is sometimes called the \PD5 principle\Q, after the initials of the authors of. One may regard dynamic evaluation as a computer algebra counterpart of the concept of non-deterministic evaluation from theoretical computer science. The strategy of dynamic evaluation has been extended to transcendental parameters, real algebraic numbers in, and more general algebraic structures8>. Several implementations have been proposed for parameters that are constrained by triangular sets. Early implementations simply handled splittings by redoing the entire computation under stricter constraints. Unnecessary recomputations can be avoided through the use of high-level control structures such as continuations. Unfortunately, efficient implementations of such control structures are rarely available for common programming languages. In this paper, we mostly leave implementation issues aside and focus on the complexity of computations with parameters. In his PhD thesis, Dellière has investigated the relationship between dynamic evaluation and decompositions of constructible sets into triangular sets: the central operation is the computation of gcds with coefficients in products of fields, such as>. Let us further mention that dynamic evaluation has influenced several polynomial system solvers relying on triangular sets, and is now involved in various other algorithms in computer algebra; see for instance. Dedicated algorithms over dynamic fields such as> have been proposed by Dahan . Without appealing to the general dynamic evaluation paradigm, they designed efficient algorithms for quasi-inversion in >, as well as gcd computations and coprime factorization in >. Recomputations induced by splittings are handled using fast hoc> techniques. In the worst case, it is known that dynamic evaluation over > suffers from an overhead of the order dim> \>: see Examples and. To our knowledge, this paper is first to propose a general strategy for removing this overhead. The main contribution of the present paper is a new evaluation paradigm to compute with algebraic parameters in an asymptotically fast manner. In section, we recall the concept of computation trees as a formalization for the cost of algebraic algorithms. In section, we introduce the concepts of unpermissive, panoramic, and directed evaluation. This provides us with precise terminology for analyzing subtle differences between the complexities of various evaluation strategies. Informally speaking, the unpermissive evaluation of a computation tree simply aborts the usual evaluation whenever a zero-divisor needs to be inverted or tested to zero. If azero-divisor is discovered in this way, then a proper factorization =|\>*|\>> of one of the defining polynomials can be deduced. This leads to a decomposition of> into the direct sum of two proper subalgebras, defined by the towers \\\\\|]>/|\>|)>|)>>\\> and \\\\\\|]>/|\>|)>|)>\\>. A panoramic evaluation of a computation tree returns all possible results when considering ,\,\> as algebraic parameters, and thereby constitutes our main objective. The unpermissive evaluation model gives rise to the following naive panoramic evaluation strategy: whenever the unpermissive evaluation produces a proper splitting of >, we restart the evaluation over each of the two subalgebras of >. The problem with this rather naive approach is that the evaluation may need to be restarted as many as> \>> times, which turns out to be suboptimal from a complexity point of view: see Example. The directed evaluation is meant to remedy this situation by ensuring a sharp decrease of every time that we need to restart the evaluation. More precisely, we will show that the reevaluation depth remains bounded by >. Section contains our main complexity result in the case of a single parameter, >. We prove a softly linear complexity bound for panoramic evaluation and provide a detailed comparison with various implementations of dynamic evaluation. In section, we turn to the case of an arbitrary number of parameters 2>. With respect to the univariate case, the main difference is that > is not necessarily a field, although we still conduct our computation as if it were ( during gcds computations in>). Consequently, zerotests and inversions of elements in \\> may lead to additional case distinctions according to the possible values of ,\,\>. Despite these technical complications, we again prove a quasi-linear complexity bound for the cost of panoramic evaluation, under the assumption that is fixed (this means that is not allowed to grow with ). For arbitrary, not necessarily bounded heights, the complexity analysis becomes tedious. We need to revisit the construction of accelerated towers of fields, introduced in, in the context of directed evaluation. The key idea is as follows: before the directed evaluation of a given computation tree, we perform the directed computation of an accelerated version of the current tower, so the computation tree can subsequently benefit from accelerated arithmetic. Overall, in section, we achieve an overhead of the form>> for the panoramic evaluation, where > represents any fixed positive real number. Our techniques are more general than those of: they turn out to be applicable in all contexts that involve dynamic evaluation with algebraic numbers. In addition, thanks to our accelerated tower arithmetic, we improve the complexity bounds for the specific tasks studied in, whenever is allowed to be arbitrarily large. Section contains two important additional examples. We first show that products in a separable tower can be done in time >|)>>, which extends. We next present a less straightforward application of fast panoramic evaluation to matrix multiplication with entries in >. This section gathers known definitions and results about elementary operations in computer algebra, to be used in this paper. Let us recall the notion of a computation tree; we essentially follow the presentation from4, section4>. In the present paper, all computation trees manipulate data in >-algebras over an effective field >, and only the following operations are allowed: <\itemize> The binary arithmetic operations > in the algebra. The unary operation > of inversion, which is partially defined in the algebra. The unary zero-test, written >. For each constant \>, the nullary constant function \c> and the unary function c*x> of scalar multiplication by . We denote the corresponding sets of constant functions and scalar multiplications by > and >. We write \\\\\,|}>> for the set of all arithmetic operations. Consider a binary tree whose set of nodes is a disjoint union \\\\\\> of the sets >, >, >, and > of , , and . We assume that the input nodes form an initial segment of unary nodes starting at the root, that the output nodes are leafs (of arity zero), that computation nodes admit arity one, and that branching nodes admit arity two. A over > is such a binary tree, together with an that <\itemize> assigns an instruction of the form <\equation*> ;u,\,u|)> to every computation node , where \\> has arity , and ,\,u> are nodes in\\>> that are of ( nodes in the path ascending from to the root of the tree); assigns an instruction of form <\equation*> ;u|)>, to every branching node , where is a predecessor of in \\>; assigns a ,\,u|)>> to every output node , where ,\,u> are predecessors of in \\>, and > may depend on . Let be a computation tree as above with |\|>> input nodes. Let > be a>algebra and let us show how gives rise to an evaluation function <\eqnarray*> :\|\|>>>|>||}>\\>\>,>>||>|.>>>> The value > is a new symbol that is returned whenever an arithmetic operation cannot be executed. In the present framework this can only happen for inversions. Given an input value ,\,a|\|>>|)>\\|\|>>>, the evaluation of at proceeds by constructing a path > from the root of the tree, along with the function <\equation*> \:P\\\,,|}>\\>\> that associates a value to each node of the path, as follows: <\itemize> The path > begins with the input nodes ,\,u|\|>>> of >, and we set ;a|)>\a> for ,|\|>>. The next node of the path is set to the successor of |\|>>>. If the current node of the path is a computation node of the form ;u,\,u|)>> then we set \;a|)>,\,\;a|)>|)>>. If this calculation is well defined, then the next node of the path is set to the successor of . Otherwise, the evaluation path ends at, we say that the computation tree is at , and we set \>\>. If the current node of the path is a branching node of the form ;u|)>>, then we set \|)>>. If > is > then the next node of the path is set to the left successor of , otherwise the next node is the right successor of . If the current node of the path is an output node with return value ,\,u|)>>, then we set \;a|)>,\,\;a|)>|)>>. The path ends at and we set \\>. \; <\wide-tabular> |||||||||| <\example> This example illustrates the definition of a computation tree with =\> and a single input node. Let > represent the -th prime number, let > be a positive integer, and let be the computation tree that takes as input and performs the following computation: \; <\indent> > -p|)>>=0> \; The computation tree for =2> is shown on the right-hand side. The input node is a circle, computation nodes are long rectangles, output nodes are shorter rectangles, and branching nodes are diamond-shaped. If =2>, then evaluates to at when =2>>, to when =3>, and to in all other cases. We notice that <\equation*> -p|)>>=0\x=p, which makes the example slightly artificial. |<\cell> |gr-frame|>|gr-geometry||gr-snap||gr-grid||gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||gr-edit-grid-old||1>|gr-grid-aspect|||>|gr-grid-aspect-props|||>|gr-transformation||||>|magnify|0.707106780759852||>|||||>||>|||||>|||||>||>||>|||||>||>|||||>||>||>||||>|||>| y>|>||)>>|>|\y-y>|>|\y\y>|>|\y\y>|>|\y-y>|>|>|>|>|>|||>||>>|||||||>|\x\x>|>|||||||>|\2>|>||||||>|||>|\3>|>||)>>|>|>|>| y>|>|||||>|||||>||||||>|\1>|>|||||>||>||>||>|\0>|>|||||>||)>>|>|>|>||>>> >>> One may associate cost functions to a computation tree . Given apath of length with leaf \> in , we define > to be its cost. The maximal cost of apath is called the of and we denote it by >. We may use > as a bound for the number of operations in > that are required for the evaluation of over >. Since additions, multiplications and inversions typically admit different costs, it is convenient to introduce the following more detailed quantities: <\itemize> > stands for the number of input nodes, \|\|>>. > stands for the maximal arity of a return value, \max\> m>. > stands for the maximal number of operations in \\\> for a path in . > stands for the maximal number of multiplications for a path in . > stands for the maximal number of inversions or zero-tests for a path in . We will call ,\,\,\,\|)>> the of and notice that \\+\+\+\+\>. Taking =2> in Example, we have =1>, =1>, =5>>, =3>>,=2>. Usually, we are really interested in the maximal number >> of scalar operations in> that are needed to evaluate over >. If > and > are clear from the context, this is simply called the of or the needed to evaluate . It will be useful to introduce the following additional quantities: <\itemize> >> stands for the maximal number of elements in > that are needed to represent an element in >. Throughout this paper, we assume that operations in \\\> can all be computed using >|)>> operations in >. >> stands for the number of operations in > that are needed to multiply two elements in >. >> stands for the maximal number of operations in > that are needed to perform azero-test or inversion in >. We clearly have <\equation*> \>\O+\+\|)>*>|)>+\*>+\*>. <\remark> In a natural programming language, negations, divisions and equality tests are allowed, but for the sake of the presentation, we assume that <\itemize> negations are implemented as ; divisions are implemented as >; equality tests are implemented as >. These restrictions are harmless, in the sense that they only affect the constants hidden in the \P\Q of complexity estimates. <\remark> For actual implementations of zero-tests that we will encounter in this paper, it is usually possible to compute the actual inverses of non-zero elements with little extracost. We will allow ourselves to store such inverses \Pfor future use\Q. In gcd computations, this helps us to keep the number of zero tests and inversions sufficiently low. An alternative, more rigorous, but less pedagogic approach would be to systematically work with a hybrid instruction that both performs a zero-test and an inversion in the case when the zero-test fails. <\remark> The \PBSS model\Q provides an alternative approach for computations over an abstract field>. Roughly speaking, it is a natural extension of the Turing machine model for which the tapes are allowed to contain elements in >. The BSS model is more powerful than the computation tree model in the sense that it allows for loops, subroutines, lookup tables, etc. Nevertheless, an arbitrary program in the BSS model that admits a finite number of execution flows may be emulated by a computation tree. This amounts to \Punrolling\Q all possible executions as in Example above. <\remark> We will also use the notion of a . In the present context it is convenient to define a straight-line program as a computation tree without branching nodes or inversions, so it encodes a polynomial expression. This definition is a bit different but equivalent to the standard one4, section1>. A polynomial in > of degree d> is represented by the vector of its coefficients from degree to . Polynomial additions ( subtractions) in d>> take at most additions ( subtractions) in >. Determining the degree of a polynomial in d>> requires at most zero-tests. Let > be an effective commutative ring with unity. We denote by >> acost function for multiplying two polynomials \d>> by a straight-line program over>. We make the following assumptions: <\itemize> >/d> is a nondecreasing function in\Vthis assumption is customary; >> is , in the sense that <\equation> >|m*d>=O>|d>|)> holds whenever d>. This assumption is less common, but it is only used within Propositions and. Notice that is equivalent to >=O>|)>>. For general >, it has been shown in that one may take <\equation*> >=O=. If > has positive characteristic, then it was shown in that one may even take <\eqnarray*> >>||> d>|)>,>>>> where > d\min \\log\|k\>\log d\1|}>>. Let \> be of degree > and let \> be monic of degree \d>. The quotient of the Euclidean division of by can be computed by a straight-line program in time >-d+1|)>|)>>. Given this quotient, the remainder f-q*g\\d>> can be computed using >|)>|)>> additional operations. If necessary, the degree of can be determined using at most> further zero-tests. It is well known that the gcd of two polynomials and in d>> can be computed in time >*log d|)>>; see11>. But we will need to be more precise in section in order to analyze the complexity of \Pdirected inversions in towers\Q. Following the notation of, let =F> and =G> be in > of respective degrees \d\1> and \n-1>, and consider the extended Euclidean sequence defined as follows: <\itemize> \1>, \0>, \0>, \1>; \R-E*R>, \C-E*C>, \D-E*D>, where \R quo R> is the quotient of > by >. Consequently we have =R rem R>, that is the remainder in the division of > by>, and =C*F+D*G> for all 0>. The sequence ends after division steps with \0> for ,w>, and =0>. The last non-zero polynomial > is > and the Bézout relation is =C*F+D*G>. The fast extended Euclidean algorithm applied to > and > does not compute the complete Euclidean sequence, but only the sequence of the quotients ,\,E> in a divide and conquer fashion. This is enough to permit the efficient recovery of the Bézout relation =C*F+D*G>. For ,w+1>, let \deg R>. We claim that the number of zero-tests in the fast extended Euclidean algorithm is exactly >. This claim is a consequence of the two following observations about the fast extended Euclidean algorithm (see for instance18>): <\itemize> Computing the quotients > does not involve any zero-tests or inversions. On the other hand the determination of > requires testing the coefficients of > from degree -1> to >, which involves -n> zero-tests. This totalizes > zero-tests. The degrees of the cofactors > and >, but also of all the entries of the \Ptransition matrices\Q are explicitly determined from the >; see10>. So the computation of the transition matrices also does not involve any zero-tests or inversions. In order to perform polynomial divisions, the inverses of the leading coefficients of the> are needed. This requires at most =deg F> inversions. To summarize the discussion, the extended gcd of and of degree d> takes >*log d|)>> additions, subtractions and products in >, plus d> zero-tests and d> inversions. In addition, every inversion of an element is preceded by an unsuccessful zero-test for that element. Elements of a tower |)>t>> are represented by vectors of coordinates in >. So additions, subtractions, and products by scalars in > can be done by straight-line programs with linear costs. We recall the following result, where >> represents the cost of one product in>. <\proposition> Under the assumptions of section, there exists a constant C\3> such that one product in > can be computed by a straight-line program in time <\equation*> >=O*>|)>. In addition, the product of two polynomials inn>> can be computed by a straight-line program in time <\equation*> >=O*>|)>. <\proof> This result is essentially due to Lebreton; see also2.4>. In the introduction, we have informally discussed computations with parameters and various strategies for automating case distinctions. In this section, we formalize these ideas in the specific situation of algebraic parameters. Let > be an effective field and let be an ideal of ,\,x|]>> such that: <\itemize> \\,\,x|]>/I> is a >-algebra of finite dimension dim> \>, is absolutely radical, which means radical over the algebraic closure |\>> of >. In the context of the present paper, it will be convenient to call > a over> with parameters, and is said to be its , written >>. The respective images of ,\,x> in > are denoted by ,\,\>; they are regarded as over>, subject to the relations in . Geometrically speaking, the tuple ,\,\|)>> represents ageneric point in the set >> of the zeros of in |\>>. This setting is more general than the one of the introduction, but it is intended to be applied later to ideals generated by triangular sets. Let > be a second parametric algebra over > with parameters. As a shorthand, we write \\>> whenever > is aquotient algebra of >. This is the case if, and only if, >\I>>, or, equivalently, if >\Z>>. If \\>, then we write \\>> for the canonical projection \\>>, and notice that \\>|)>,\,\\\>|)>|)>> represents a generic point in the set >> of the zeros of >> in |\>>. With a slight abuse of notation, \\>> is extended in a coefficient-wise manner to \\>. Two parametric algebras \\,\,x|]>> and \\,\,x|]>> are said to be if >\Z>=\>. In that case, we have <\equation*> \,\,x|]>/>\I>|)>\\\\. More generally, given pairwise disjoint ,\,\>\,\,x|]>>, we have <\equation*> \\\,\,x|]>/>\\\I>|)>\\\\\\. We will call such a decomposition a of >. Now consider the prime decomposition <\equation*> I=\\\\\ of the defining ideal of >, and define \\,\,x|]>/\> for ,s>. Then we have \\> and there exists a natural isomorphism <\equation> \\\\\\\. It is convenient to call this relation the of >. The corresponding zero-set>> is a disjoint union: <\equation*> Z>=Z>\\\Z>. Given a zero-divisor \>, we have <\equation*> I=I\I,I\I+I\I\. Indeed, we clearly have I\I>. Conversely, given I\> with I>, we have *v\I>, whence I> since is radical, and I>. Setting <\eqnarray*> >|>|,\,x|]>>/I\\/>>|>|>|,\,x|]>/I\\|]>,>>>> we obtain a natural isomorphism <\equation*> \\\\\. Such a decomposition is called an of >. We have <\equation*> Z>=Z>\Z>. From an effective point of view, the computation of total splittings requires an algorithm for polynomial factorization, whereas atomic splittings can be computed using standard techniques from effective polynomial algebra, such as Gröbner bases, triangular sets, or geometric resolutions. Let us now describe an abstract way to formalize computations in parametric algebras modulo splittings. Consider a set > of parametric algebras over >. We say that > is a if the following conditions are satisfied: <\itemize> Each \\> is an effective >-algebra. Given \\\>, \ we can test whether is invertible and compute > if so. Given ,\\\> with \\>, we have an algorithm for the projection \\>>. Given \\\>, we can effectively compute /\\> and |]>\\>. For any \\\\\\> with ,\,\,\\\>, we have algorithms for both directions of this isomorphism. Using Gröbner basis techniques, the above conditions are in particular verified if > is the set of all parametric algebras> that are explicitly given by a finite set of generators of >>. Indeed, a Gröbner basis of>> induces a basis of > over > along with the multiplication matrices by ,\,\>, so the above operations boil down to linear algebra. This observation is convenient from a conceptual point of view, but, of course, not very efficient from the asymptotic complexity perspective. Sections, , and are devoted to more specific parametric frameworks that allow for asymptotically faster implementations. From now on, > denotes a parametric algebra, and we will use the notations from section for computation trees. The of a computation tree with input nodes > as above at ,\,a|\|>>|)>\\|\|>>> is defined as follows. Informally speaking, the tree is evaluated in the usual way over > concerning ring operations, but the evaluation aborts whenever a zero-divisor needs to be inverted or tested to zero. More precisely, we write>> for the , and |\>> for the . We introduce anew output value, written >, in order to indicate that the evaluation process detects that the current algebra > is not a field. We define |\>> by induction: <\itemize> If the current node of the path is a computation node of the form ;u|)>>, then we distinguish the following cases: <\itemize> If |\>> is zero in >, then the path ends at with |\>\|\>\>. If |\>> is invertible, then |\>\|\>> and the next node of the path becomes the successor of . Otherwise, |\>> is a zero-divisor in >, and the evaluation aborts; the path ends at , we set |\>\|\>\>, and record the zero-divisor |\>> for future use. If the current node in the path is a branching node ;u|)>>, then we distinguish the following cases: <\itemize> If |\>> is zero in >, then |\>\>, and the next node of the path becomes the right successor of . If |\>> is invertible in >, then we set |\>\>, and the next node of the path becomes the left successor of . Otherwise, |\>> is a zero-divisor in >, and the evaluation aborts; the path ends at , we set |\>\|\>\>, and record the zero-divisor |\>> for future use. For the other types of nodes, the evaluation rules remain the same as for the standard evaluation described in section. <\lemma> With the above notations, let \\>. If |\>\>, then the evaluation paths >> and \\>|)>> coincide and \\>|\>|)>=\\\>|)>> holds, under the natural convention that \\>|)>\>. <\proof> The proof is straightforward from the definitions. <\definition> Given an input ,\,a|\|>>|)>\\|\|>>> for a computation tree , we say that <\equation*> \\\\\\\> is a of > for the pair > if |\>\\>|)>\> for ,\>. A of at is a set of pairs ,b|)>,\,>,b>|)>|}>> such that \\\\>> is a panoramic splitting of > and \|\>\\>|)>> for ,\>. <\lemma> Let \\\\\\> denote the total splitting of >, and let ,b|)>,\,>,b>|)>|}>> be a panoramic value of at . Then, for each ,s|}>>, we have <\equation*> |\>\\>|)>=\\\>|)>=\\\>|)>, where ,\|}>> is the unique integer such that \\>. <\proof> Since > is a field, any non-zero element in > is invertible. Consequently, <\equation*> |\>\\>|)>\, and Lemma implies that |\>\\>|)>=\\\>|)>>. On the other hand, <\equation*> b=|\>\\>|)>\, and Lemma implies that <\equation*> \\\>|)>=\\\>|)>. <\example> Consider the computation tree from Example for some \\>, and let <\equation*> \\-p|)>*\*-p>|)>, |)>>, and \\/I>, with \\>. If > represents the image of in >, then a possible panoramic splitting of at> is <\equation*> \\\\\\\>, where <\itemize> \\+1>, \\/-p|)>> and |\>\\>|)>|)>=i>, for ,\>, >\\/-p+1>|)>*\*-p>|)>|)>> and |\>\\>>|)>|)>=0>. Notice that the associated primes of are =-p|)>> for ,\>, and the total splitting of > is <\equation*> \\>\/-p|)>. The following naive algorithm for the computation of panoramic values was already sketched in the introduction: <\specified-algorithm> <\description-compact> A computation tree and an evaluation point \|\|>>>. A panoramic value of at . <|specified-algorithm> <\enumerate> Compute the unpermissive evaluation |\>>. If |\>\>, then return ,|\>|)>|}>>. Otherwise a non-trivial zero-divisor \> has been recorded, which allows us to compute proper subalgebras ,\,\> and ,l-1|}>> such that /\\\\\>> and |]>\\\\\\>. Recursively apply the algorithm to \\>> for ,l> and return the union the panoramic values obtained in this way. <\proposition> Algorithm is correct. <\proof> The algorithm finishes since > is finite dimensional. As for the correctness it suffices to verify that the output in step2 is correct, which is straightforward from the definitions. From now we focus on the development of a faster alternative for Algorithm. The idea is to impose a finer control over the dimension of the components of splittings. Informally speaking, computation trees over > will be evaluated entirely, while restricting operations to suitable subalgebras of >: when a zero test or an inversion occurs for avalue , the current subalgebra is further restricted to its largest subalgebra where the projection of is either invertible or zero. In order to formalize this idea, we need some definitions and the underlying directed arithmetic operations. <\definition> Given a computation tree , we say that a splitting <\equation*> \\\\\\\\\> is if <\itemize> > \\1> and > \\1> for ,\>, > \\dim> \> for ,\>. A of takes as input: <\itemize> a directed splitting of \\\\\\\\>>, a point \|\|>>>, and returns <\itemize> a refined directed splitting of \|~>\|~>\\\|~>\\\\\\>>, |\>\|~>>|)>> such that |\>\|~>>|)>\>. We introduce a in >, that takes a directed splitting \\\\\\>> as input, the value in > to be inverted, and that returns a directed splitting |~>\|~>\\\|~>\\\\\\>> such that <\itemize> \|~>>> is either zero or invertible; The result of the directed inversion of is respectively > or \|~>>>. We also introduce a in >, that takes a directed splitting \\\\\\>> and the value in > to be tested as input, and that returns a directed splitting |~>\|~>\\\|~>\\\\\\>> such that <\itemize> \|~>>> is either zero or invertible; If \|~>>> is invertible, then \|~>>> has been computed and recorded; The result is \|~>>|)>>. <\remark> The above specifications leave room for some flexibility for the precise implementation of zero-tests and inversions: in general, the conditions > \\dim> \> do not imply uniqueness of the output splittings. <\remark> We could have introduced directed variants of additions, subtractions, and products in parametric algebras, exactly in the same way as for the zero-test and the inversion. This could actually be useful in practice. However, in order to keep our exposition simple, we prefer to use straight-line programs over > for these operations, so splittings never occur. Let us now define the directed evaluation of a tree . As input, we take a directed splitting \\\\\\>> and \|\|>>>. Informally speaking, this evaluation simply applies the above directed operations in sequence, so we evaluate the entire computation tree while restricting the current algebra when encountering zero-tests and inversions. The list of the residual subalgebras is maintained throughout the evaluation process. For consistency, the evaluation takes a directed splitting \\\\\\>> as input, but only the summand> will be decomposed during the evaluation process. Formally speaking, the directed evaluation path is written >>. To each node >>, we both associate a directed splitting <\equation*> |\>=,\,\,\>|)> of >, so <\equation*> \\\\\\\\\>, and a value <\equation*> |\>\\\,,|}>\\>\>. The directed evaluation of is defined inductively as follows: <\itemize> The path >> starts with the input nodes ,\,u|\|>>> of >. We set |\>;a|)>\,,\,\>>|)>>> and |\>;a|)>\a>, for ,|\|>>. The next node of the path is set to the successor of|\|>>>. If the current node of the path is the root of the path, and is a computation node ;u,\,u|)>>>, then we necessarily have =\> and , we set |\>\,\,\,\>|)>>> and |\>\>. The next node of the path is set to the successor of . If the current node of the path is a computation node ;u,\,u|)>> with \\\\\|}>>, whose direct predecessor is , then we set |\>\|\>> and <\equation*> |\>\>\\>|\>;a|)>|)>,\,\>\\>|\>;a|)>|)>|)>. The next node of the path is set to the successor of . If the current node of the path is a computation node ;u|)>>, whose direct predecessor is , then we apply the directed inversion to \\\>|\>|)>> for the splitting |\>>. This yields a new splitting \\\\\\\\>> that we assign to |\>>. <\itemize> If \\>=0>, then we set |\>\|\>\>, and the path ends at . Otherwise |\>\\\\>>, and the next node of the path becomes the successor of . If the current node of the path is a branching node ;u|)>>, whose direct predecessor is , then we apply the directed zero-test to \\\>|\>|)>> for the splitting |\>>. This yields a new splitting \\\\\\\\>>, that we assign to |\>>. <\itemize> If \\>=0>, then |\>\>, and the current node of the path becomes the right successor of . Otherwise, |\>\>, and the current node of the path becomes the left successor of . We also record the inverse \\>>. If the current node of the path is an output node ,\,u|)>>, whose predecessor is, then we set |\>\|\>\|\>> and <\equation*> |\>\|\>\>\\>|\>;a|)>|)>,\,\>\\>|\>,a|)>|)>|)>. Whenever >> are such that is asuccessor of , the splittings of > at and satisfy \\>. It can be checked by induction over the path >> that |\>> and |\>> are well defined. <\proposition> Let \|~>\|~>\\\|~>\\\\\\>> represent the directed splitting |\>> returned by the directed evaluation of at as above. Then, for all \|~>>, we have <\equation*> \|~>\\>|\>|)>=|\>\\>|)>. <\proof> We verify by induction on paths that >> and >\\>|)>> coincide, and that \\>|\>|)>=|\>\\>|)>> holds for all >> that is not a branching node. <\example> Let us again consider the computation tree from Example, and let <\equation*> \\-p|)>*\*-p>|)>, |)>>, and \\/I>, with \\>. Consider the directed evaluation of at >>, where > represents the image of in >. The first zero-test that we encounter is -p|)>>>, which yields the directed splitting <\equation*> \\\/-p|)>*\*-p>|)>|)>\\/-p|)>. After the > zero-tests -p|)>,\,-p>|)>>>, we end up with the directed decomposition <\equation*> \\\/-p+1>|)>*\*-p>|)>|)>\\/-p>|)>\\\\/-p|)> and the value |\>|)>=0>. This is due to the requirement that directed evaluation always privileges the \Pbranch of highest degree\Q. If =\+1>, then the last zero-test potentially leads to another directed decomposition <\equation*> \\\/-p>|)>\\/-p+1>|)>\\/-p-1>|)>\\\\/-p|)> and the value |\>|)>=\>. In general, we recall that directed evaluation is a non-deterministic process: the output may depend on internal splitting choices that are made during the directed zero-tests and inversions. We are now in a position to state a central algorithm of this paper, which performs panoramic evaluations using directed ones. The presentation is abstract, in terms of general parametric frameworks. In the remainder of the paper we will study various concrete instantiations of this algorithm. <\specified-algorithm> <\description-compact> A computation tree and an evaluation point \|\|>>>. A panoramic value of at . <|specified-algorithm> <\enumerate> Perform the directed evaluation of at for the trivial directed splitting |)>> of >. Let \\\\\\\\>> be the directed splitting obtained in return. Compute the projections \\>> for ,\>. Recursively call the algorithm in order to evaluate at \\>> for ,\>. Return the union of ,|\>|)>|}>> and of the panoramic values obtained in step3. <\proposition> Algorithm is correct. <\proof> Algorithm finishes because the dimension of the input algebra strictly decreases throughout the recursive calls in step3. At the end of step1, we have <\equation*> |\>=|\>\\>|)>\, by Proposition. Therefore the singleton ,|\>|)>|}>> is a panoramic value of at \\>>. We conclude by observing that the union of the panoramic values in step4 gives a panoramic value of at . <\example> Example illustrates step1 of Algorithm, for which we obtain =\/-p+1>|)>*\*-p>|)>|)>>, |\>|)>=0> and =\/-p|)>> for ,\>. After the> recursive calls in step3, we obtain the panoramic value <\equation*> /-p>|)>*\*-p>|)>|)>,0|)>,/-p|)>,1|)>,\,/-p>|)>,\|)>|}>. In the next sections, Algorithm will lead to nearly linear asymptotic complexity bounds. So it turns out to be much faster than the naive Algorithm. From the complexity point of view, there is still a problem with naive implementations of Algorithm: the directed evaluation approach involves many potentially expensive conversions of the form \\>|\>>|)>>. A general solution to this issue is tedious, but for the concrete parametric frameworks from this paper, a natural and efficient approach is to delay these conversions. This can be done at the price of performing arithmetic operations in the input algebra instead of its subalgebras. Consider for instance the simplest case when =\/|)>>, where > is monic of degree . Let =\/|)>\\> with \\> and \d/2>. Then one projection \\>> corresponds to a division by > of cost >|)>>, when using the standard representation for elements in >. This means that additions during the directed evaluation of a tree typically admit a cost >|)>> instead of >, which is suboptimal. A natural remedy to this problem is to delay reductions modulo >. This strategy naturally fits in our setting of parametric frameworks through the use of redundant representations. More precisely, consider some \\> within a parametric framework >. Then we may define a new parametric framework >> whose objects are algebras \\>> in >, with this modification that elements in > are represented by elements in >. Given \\>, this means that projections \\>> are free of charge in >>. The arithmetic operations \\\\\|}>> on elements in > are also performed in >. The inversion of \> is done by computing the projection =\\\>> in > and then performing the inversion of > in >; zero-tests are done similarly. Of course, at the end of a directed evaluation that uses this kind of redundant representations, we may wish to convert the result to the standard representation in >. This can be done by inserting a \Pfinalization\Q step at the end of step 1 in Algorithm. This section is devoted to parametric algebras with one algebraic parameter, that is of the form =\/>|)>> with >> monic, separable, and of degree . For our complexity bounds it will be convenient to assume that 2>. Elements in > are represented as remainder classes >> with \d>>. The univariate situation is notably simple but already useful enough to be treated separately. We first specify the parametric framework and the directed operations, then we analyze the cost of our fast panoramic evaluation, and finally we compare the directed evaluation strategy with dynamic evaluation. For efficiency reasons, we further assume that >> is in the sense that we are given the cofactors >> and >> in d>> in the Bézout relation <\equation> 1=\>*\>+\>*\>. Computing this relation from the outset only requires >*log d|)>> operations in >. Let us first specify the required operations of the univariate parametric framework, and explicit their complexity. <\itemize> Additions and subtractions in > can clearly be performed by straight-line programs in linear time>, whereas multiplications take time >|)>>. An element >\\> with \d>> is invertible if and only if >|)>=1>> and, in that case, > can be computed using the extended Euclidean algorithm. Both the test and the computation of > can be done by a computation tree in time >*log d|)>>. We have \\> if and only if >\\>>. In that case, we have <\equation*> \\\>>|)>=>|)> mod \> for all \d>>; the projection \\>> can thus be computed in time >|)>> by astraight-line program (below, we will rather use the technique of delayed reductions from section in order to avoid projections altogether). Given >\\\> with \d>>, we have />=gcd>,B|)>> and |]>>=\>/gcd>,B|)>>. This shows that we can compute /> and |]>> in time >*log d|)>> using computation trees. Given univariate parametric algebras ,\,\\\>, we have \\\\\\> if, and only if, >=\>*\*\>> (which in particular implies that the >> are pairwise coprime). In this case, the isomorphism \\\\\\> in both directions can be computed in time >*log s|)>> by using the usual subproduct tree of >,\,\>>; see10>. The directed zero-tests and inversions of an element \> with preimage can be computed in time >*log d|)>>, as follows: <\itemize> The input is a directed splitting of >, <\equation*> \\\/>|)>\\\\\\>, the Bézout relation >*\>+\>*\>>, and an element \/>|)>> with preimage \deg \>>>. If , then the result of the zero-test is > and the result of the inversion is >. The input directed splitting is left unchanged in return. We compute gcd>|)>> along with the Bézout relation >>. If , then the result of the zero-test is > and the result of the inversion is . The input directed splitting is left unchanged in return. We compute \>/g>, \ and deduce the Bézout relations of > and , and of > and by Lemma below. If deg \>> then we return the directed splitting <\equation*> \\\/|)>\\/|)>\\\\\\> and the image of is zero in /|)>>. The value of the zero-test is >, and the result of the inversion is >. Otherwise, we return the splitting <\equation*> \\\/|)>\\/|)>\\\\\\> and the image of in /|)>> is invertible. The latter splitting is actually directed since deg \>> implies <\equation*> 2*deg g=2*>-deg h|)>\2*>-deg h|)>\deg \>. The inverse of modulo is obtained as follows: <\itemize> From the Bézout relation >*\>+\>*\>>, we deduce >**h+g*h|)>+\>*\>> and then <\equation*> 1=\>*g*h mod h. From the Bézout relation >>, we get , and deduce <\equation*> 1=\>*h*U*A mod h. The value of the zero-test is >, and the result of the inversion is >*h*U rem h>. <\lemma> Let \> be monic and separable of degree , and let and be non-constant monic polynomials in > such that . Given the Bézout relation +B*f>, the Bézout relations for > and , and > and can be computed by a straight-line program intime>|)>>. <\proof> From the given Bézout relation we have <\equation*> 1=A*g*h+|)>*h. Since rem h|)>*h|)>> and |)> rem h|)>*h|)>> are strictly less than *h|)>>, reduction of this relation modulo *h> yields <\equation*> 1= rem h|)>*h+|)> rem h|)>*h. This is the desired Bézout relation for > and . By symmetry, the Bézout relation for > and can be computed in a similar way. We are now ready to present the main complexity bound of this section, in terms of the detailed cost functions defined in section. <\theorem> Let =\/>|)>> be an explicitly separable extension of > of degree deg \>\2>, and let be a computation tree over >-algebras of detailed cost ,\,\,,\>|)>>. Then the panoramic evaluation of \ over> by Algorithm takes time <\equation*> O*d++\|)>*>++\|)>*>*log d|)>*log d|)>. <\proof> We use Algorithm in combination with the technique of delayed reductions from section. This means that we avoid the cost of conversions, at the price of performing arithmetic operations in subalgebras of > in the algebra > itself. More precisely, the cost of one directed evaluation of over > is the sum of: <\itemize> *d|)>> operations in > for the nodes of type in \\\>, *>|)>> operations in > for the nodes of type >, *>*log d|)>> operations in > for the directed zero-tests and inversions, *>|)>> operations in > for the reductions in the output nodes of the path ( the \Pfinalization step\Q in the terminology of section). Let \\\\\\\\>> denote the directed splitting obtained at the end of step1 of Algorithm. By construction we have <\equation> dim> \\d/2i=1,\,\. Fast multi-remaindering yields \\>> for ,\> in time *>*log d|)>>. We recursively perform the panoramic evaluation of over > for all ,\>. Let> be the cost of one panoramic evaluation of over an algebra of dimensiond>>. We have shown that there exists a universal constant such that <\equation*> \c*d++\|)>*>++\|)>*>*log d|)>+>> \|)>. In view of, we conclude by unrolling this inequality at most ||\>> times. <\example> .> The first directed evaluation of performs *>|)>log*\|)>|)>> operations in>. One directed evaluation of over /-p|)>>> takes time |)>>, for ,\>. In this example, the resulting cost of Algorithm is <\equation*> O*>|)>*log*\|)>+>i*log \|)>=O*>|)>*log*\|)>|)>, which is better than the bound of Theorem because the recursive depth is constant. If > is a field, then we notice that the usual evaluation of at > takes time *>|)>*log \|)>>. Let us now compare the complexity of directed evaluation with the complexities of other known strategies for a single algebraic parameter. One problem with dynamic evaluation is that it is hard to implement in common programming languages without support for parallelism or high level control structures such as continuations. Early implementations of dynamic evaluation were therefore naive, the computation tree essentially being reevaluated for every separate case: see subsection. In theory, using -style continuations or -style forking, it is possible to factor out many common computations between the different cases; see. We analyze these approaches from a complexity point of view in section. Besides dynamic evaluation, various more approaches have also be proposed for computations with asingle algebraic parameter; we will discuss them in section. When using common sequential programming languages, dynamic evaluation is usually implemented as in Algorithm, with the following two differences: <\itemize> Splittings are no longer required to be directed. In other words, at each evaluation step, the splitting \\\\\\\\>> at node of is not required to satisfy the conditions > \\dim> \> for ,\>. Consequently, whenever a zero-test or an inversion triggers a basic splitting for >, the branch where we continue the evaluation is chosen non-deterministically. Such evaluations are said to be in the sequel. Once the undirected evaluation is finished, the projections in step2 of Algorithm are done naively, without fast multi-remaindering. Adapting the cost analysis of Algorithm leads to the complexity bound <\equation*> O*d++\+\|)>*>+\*>*log d|)>*d|)> for naive dynamic evaluation, in terms of the detailed cost functions from section. The following example shows that the latter bound is tight in the worst case. So naive dynamic evaluation is in general less efficient than fast panoramic evaluation. <\example> Let us again consider the family of computation trees of Example, let <\equation*> \\-p|)>*\*-p>|)>, with \\>, |)>>, \\/I>, and let > represent the image of in >. Then a possible undirected evaluation of at > performs a basic splitting and may select the splitting <\equation*> \/-p|)>\\/-p|)>*\*-p>|)>|)>. So a possible undirected evaluation ends with the latter splitting and output value . A possible undirected evaluation of over /-p|)>*\*-p>|)>|)>> may end with the splitting <\equation*> \/-p|)>\\/-p|)>*\*-p>|)>|)> and value . Doing so for the rest of the evaluation, we may end with the splitting <\equation*> \/-p|)>\\\\/-p>|)>\\/-p+1>|)>*\*-p>|)>|)> and the value of over /-p|)>> is for ,\>, and is over /-p+1>|)>*\*-p>|)>|)>>. The total execution time therefore grows at least with <\eqnarray*> >k*>-k|)>>||>k*-k|)>|)>=\*-\|)>|)>.>>>> In comparison to Example, it turns out that dynamic evaluation may be significantly more expensive than our fast panoramic evaluation based on directed evaluation. The naive implementation of dynamic evaluation using reevaluations of the entire computation tree leads to unnecessary recomputations. High-level control structures such as continuations can be used to avoid this kind of recomputations, by resuming the \Precomputations\Q directly at the points where the splittings occurred. -style forks can be used to the same effect. We will now illustrate the benefit of these approaches on our running Example, after which we will present another example that remains problematic even with this type of optimizations. <\example> Let be a computation tree of the family introduced in Example, and let us again consider <\equation*> \\-p|)>*\*-p>|)>, with \ \\>, |)>>, \\/I>, and let > represent the image of in >. The dynamic evaluation of at > encounters an inconsistency when testing whether -p|)>>> is zero modulo >. One computation continues modulo -p>, and so returns . Another computation continues modulo -p|)>*\*-p>|)>> and a new splitting occurs at the zero-test of -p|)>>>, etc. Counting common computations in branches only once, the total cost of the dynamic evaluation is bounded by <\equation*> O*>|)>*log \+\*>|)>*log \|)>=O*>|)>*log*\|)>|)> which is essentially the same as the cost of our fast panoramic evaluation: see Example. <\example> Let us now consider the following (still somewhat artificial) program over >-algebras: <\quote-env> > \-p|)>>> > =0> \f+1> Evaluated over a field > of degree over >, the total cost of this program is <\equation*> >>*log \=*d|)>. Let us now take \\/I> with as in the previous example. The dynamic evaluation executes the first loop sequentially with cost >>|)>*log \=*\|)>>. Then it splits at the zero-test of -p|)>> modulo > into two branches: <\itemize> The first branch works modulo -p> and reduces ,\,f>> modulo -p>, which amounts to -1|)>*\|)>> operations in >. The costs of the zero-tests totalize -1|)>*>*log 2|)>>>. The second branch works modulo -p|)>*\*-p>|)>>. The zero-test of > costs >-1|)>*log-1|)>|)>>, and causes the present branch to split up into two: <\itemize> The first branch works modulo -p> and reduces ,\,f>>, which amounts to -2|)>*\|)>> operations in >. The costs of the zero-tests totalize -2|)>*>*log 2|)>>>. The second branch works modulo -p|)>*\*-p>|)>>. The zero-test of > costs >-2|)>*log-2|)>|)>>, and causes the present branch to split up into two: <\itemize> The total execution time when using dynamic evaluation is therefore <\equation*> \>>|)>*log \+>-i|)>*\+>-i|)>*log-i|)>|)>|)>=\*\|)>. By Theorem, the execution time using fast panoramic evaluation is *\|)>>, which is significantly better. The bottleneck of dynamic evaluation in Example lies in the projections of data from parametric algebras into smaller ones. It is important to stress that this cost cannot be reduced by executing the branches in a judicious order or by cleverly factoring out common computations in branches using continuations. In our fast panoramic evaluation strategy, this means that fast multi-remaindering plays a crucial role for handling these projections efficiently. The above examples show that determining the best strategy to compute a panoramic value for a given computation tree is not an obvious problem: in fact, computation trees and more general programs may often be modified in order to accelerate panoramic evaluations. Let us now consider some specific computation trees for which efficient > strategies have been developed. For panoramic quasi-inversions in >, gcds, and coprime factorizations in >, Dahan al.> have designed fast algorithms in. For instance, they showed that a panoramic gcd in n>> could be obtained with cost <\equation> O>*log d*>*log n|)>; see2.4 and4.1>. For this problem, Theorem leads to the cost <\equation*> O>*>*log n+n*>*log d|)>*log d|)>, which can be further improved to <\equation> O>*log n+n*>*log d|)>*log d|)> by using Kronecker substitution to multiply polynomials in /|)>|)>n>> in time >|)>>. If n=o>, then this cost is slightly higher than. If >, then() simplifies to >*log n*log d|)>>, which is slightly better than. Another interesting application of fast panoramic evaluation is the computation of the determinant > of an n> matrix with entries in =\/|)>>. By means of Berkowitz' algorithm, such a determinant can be computed in time +1>|)>> by astraight-line program over >, and therefore in time +1>*>|)>> by a straight-line program over>. This cost decreases to /2+2>|)>*>> by using, and even to +1/2>*>|)>> thanks to, whenever inverses of ,n> are given in >. We can do better with fast panoramic evaluation: we first compute the determinant of over> as if it were a field by means of a computation tree that performs >|)>> ring operations and |)>> zero-tests and inversions. By Theorem, this can be done in time <\equation*> O>*>+n*>*log d|)>*log d|)>. The resulting panoramic value corresponds to the residues of> modulo several pairwise coprime factors of >. Chinese remaindering finally allows to recover the actual determinant> using >*log d|)>> additional operations in >. From now on, we focus on the complexity of panoramic evaluation for 2> algebraic parameters. Such a tower is determined by algebraic parameters ,\,\>, where > is constrained by an algebraic equation over >, and > is constrained by an algebraic equation over ,\,\|]>> for ,t>. It is natural to apply the method of the previous sections for a single algebraic parameter in a recursive manner. But we have to face anew difficulty: directed zero-tests and inversions in ,\,\|]>> will involve occasional zero-tests and inversions in ,\,\|]>>, that will themselves involve occasional zero-tests and inversions in ,\,\|]>>, etc. The first goal of this section is to design data structures that allow us to create new branches for free during directed evaluation. At the end of a directed evaluation we need to project input data into all the residual branches. Performing this task efficiently is the second goal of this section. Data structures play an important role in the efficiency of operations required by parametric frameworks. From now on, we will only manipulate parametric algebras whose defining ideals are generated by triangular sets. In other words, all parametric algebras will be represented by towers |)>t>> over=\>, as in section. We recall that |)>t>> is also assumed to be absolutely reduced, |\>\\> is a product of fields. A tower |)>t>> is said to be if we are given the Bézout cofactors> and > in |]>> such that *\+\*\> for ,t>. \ In order to simplify complexity analyses, it is convenient to assume that \deg \\2>> for ,t>. In particular, *\*d\2>. This restriction is harmless, since extensions of degree =1> can be discarded without cost in our model of computation trees. Consider two towers |)>t>> and |)>t>> of the same height and over the same base field >. Let |)>t>> and |)>t>> denote the respective defining polynomials of |)>t>> and |)>t>>. We say that |)>t>> is a of |)>t>> if >\Z>>. This is the case if, and only if, there exist natural projections \\>> (that naturally extend to projections \\>:\|]>\\|]>> in a coefficient-wise manner) such that: <\itemize> > divides \\>|)>> for ,t>. \\>> sends an element \> represented by |)>=-1>A*x\\|]>d>> to <\equation*> \\\>|)>|)>=-1>\\\>|)>*x rem \|)>, for ,t>. Given such a factor tower |)>t>> of |\|>t>>, let us now study the cost \\|)>> of computing one projection \\>\\> of an element \> with t>. <\lemma> Let |\|>t>> be a factor tower of |\|>t>>. The projection \\>> of an element \> can be computed by a straight-line program in time <\equation*> \\|)>=O>|)>*d*\*d|)>=O*>|)>. <\proof> Let \|]>d>> denote the preimage of . We recursively apply \\>> to the coefficients of . Then, the reduction of \\>> modulo > can be done by a straight-line program with cost >|)>|)>>. Consequently, there exists a universal constant such that the cost function \\|)>> satisfies <\eqnarray*> \\|)>>|>|>|)>+\\|)>*d.>>>> Unrolling this inequality yields <\equation*> \\|)>=O>|)>*d*\*d|)>. Taking >|)>=O*>*\*d|)>|)>> from Proposition concludes the proof. In the sequel, \P()\Q stands for the empty tuple. Let > be an index set of -tuples of integers with =|}>> and <\equation*> \=,\,\,i|)>>\,\,\|)>\\,i\,l,\,\>|}>|}>, for integers ,\,\>> and ,t>>. Consider a family >|)>t>|)>\\>> of factor towers of |)>t>> with the property that ,\,\>> only depends on ,\,\> for all ,\,\|)>\\>, and write ,\,\>\\,\,\>>. We say that such a family of factors forms a of |)>t>> if the variety >> is partitioned into >=\\>Z>>>. If 0> and \\>, then we also write >\\,\,\>|]>> for the defining polynomial of >> over >>. It is convenient to represent such a factorization by a labeled tree (see Figure): the nodes are identified with the index set made of the disjoint union <\equation*> \\\\\\\, and each node \\> is labeled with the algebraic extension >>. The parent of the node \\> with 0> is simply the node ,\,\|)>\\>. Each individual factor tower >|)>t>> corresponds to a path from the root to a leaf.<\float|float|tbh> <\big-figure> |||\|\|\>>|\|>|\,1>|\|\,l>>>>|\|>>|>,1>|\>,1,1>|\|\>,1,l>,1>>>|\|>,l>>>|\>,l>>,1>|\|\>,l>>,l>,l>>>>>>> > <|big-figure> Example of a tree factorization of a tower of height . Given t> and \\>, let <\equation*> \>\\,\|)>\\|}>. Projecting the equality <\equation*> Z>=\\>\\>>Z,\>> on the first coordinates, we observe that the projection of ,\>>>, for given \\>, is the same for all >\\>>, and equals >>>, whence >=\\>Z>>>. Consequently, ,\,\>|)>k>|)>\\>> forms a tree factorization of the sub-tower |)>k>>. From an algebraic point of view, this means that we have anatural isomorphism <\eqnarray*> >|>|\\>\>.>>>> Consider an explicitly separable tower |)>t>> and assume that we wish to compute the panoramic evaluation of a computation tree over >. In order to apply Algorithm in this multivariate context, it would be natural to specify a parametric framework, as we did in the univariate case. Since we will exclusively focus on the directed approach from now on, it turns out to be simpler and more straightforward to describe how to perform the directed evaluation and the projections in steps1and2. Informally speaking, we want to work with respect to a \Pfactor of highest possible degree\Q at each level. This leads to special types of factorizations of |)>t>> that are illustrated in Figure. The actual computations are done in the algebras from the highlighted \Pprincipal branch\Q. The other \Presidual branches\Q are dealt with at a next iteration, when the computations for the principal branch have been completed. Technically speaking, a of > will be represented by: <\itemize> Vectors |\>\,\,\>|)>> of polynomials in |]>> for ,t>, such that: <\itemize> |\>\\,\,|\>\\> are the defining polynomials of a factor tower of |)>t>>, written ||\>|>t>>, and called the . \|\>>|)>=|\>*\\|\>>|)>*\*\\|\>>>|)>> for ,t>. \deg \> for ,l>. The Bézout relations |\>*|\>+|\>*|\>> for ,t>, so ||\>|>t>> is explicitly separable. Each factor \|\>>|)>> with ,t> and ,l> gives rise to a factor tower |)>t>> of |)>t>>, called a , as follows: <\itemize> For j>, we set \|\>>. \|\>|]>/\|\>>|)>|)>|)>>. For j>, the defining polynomial of > over > is the projection of |)>> in |]>>. The tree representation of the resulting tower factorization is summarized in Figure<\float|float|tbh> <\big-figure> <\equation*> ||\>=\||\>=\|||\>=\|\|||>\|\>>|\|\|\>|||\>>|||>\|>||\>>>>||||\>>>|||>\|>|>||\>>>>>||gr-color|none|gr-fill-color|#0002|||||||||||||||||||>>>>|1cm> \; <|big-figure> Illustration of a generic tower factorization involved in a directed evaluation. The principal branch is highlighted. . The actual directed splitting of > represented in this manner is <\equation*> \\|\>\\\\\\>\\\\\\\\>\\\\\\\\>. Notice that a directed splitting |\>,\,|\>> of |)>t>> naturally induces a directed splitting |\>,\,|\>> of |)>j>> for ,t>. Now the main idea is to perform the directed evaluation of a computation tree over the principal branch, while postponing evaluations over residual branches. With our representation of directed splittings, creating residual branches is essentially free of charge; the corresponding tower representations will only be computed after completion of the entire directed evaluation, using a dedicated \Pfinalization\Q procedure that will be detailed in subsection below. After the finalization, the projections from step2 of Algorithm can be carried out efficiently using fast multi-remaindering; this will also be detailed in subsection. As in the univariate case, it will be convenient to use the technique of delayed reductions from section. During directed evaluations, this means that we will actually represent elements in |\>>> by elements in >, for ,t>. In particular, operations in \\\|}>>> on elements in|\>> are really performed in >. We recall that the main benefit of this representation is that projections |\>\|\>>> are free of charge, whenever |\>> is a quotient algebra of |\>> whose elements are also redundantly represented by elements in>. On the other hand, we will resort to reduced representations for directed zero-tests and inversions. We will also systematically reduce all output values. Notice that elements in |\>> can be reduced in time *>*\*d|)>|)>>, by Lemma. In the next subsection, we detail how to perform directed zero-tests and inversions. In the case of a single algebraic parameter, we reduced directed inversions and zero-tests to extended gcd computations. With several parameters the problem is more difficult. An element in > can be tested to be invertible by means of a straight-line program over > with polynomial cost and a single zero-test in >: it essentially suffices to compute the determinant of the multiplication endomorphism \x\a*x\\> using Berkowitz' algorithm. But the cost of this approach is more than quadratic in , which is not satisfactory for our purposes. We now develop a more efficient strategy based on recursive calls of the fast extended gcd algorithm in the directed evaluation model. Note that asimilar recursive approach was previously used in the contexts of dynamic evaluation and triangular sets. <\specified-algorithm> <\description-compact> An explicitly separable tower |)>t>>, a directed splitting |\>|)>t>> of|)>t>>, and |\>>, where ||\>|>t>> denotes the principal branch of |\>|)>t>>. A directed splitting |\>|)>t>> of |)>t>>, with principal branch ||\>|>>t>>, the boolean value of the zero-test of >\\|\>\|\>>>, where >> is either zero or invertible in |\>>, and the inverse >> whenever >> is non-zero. <|specified-algorithm> <\enumerate> If then return > if or > and > otherwise. The directed splitting is left unchanged. Let |\>|]>d>> denote the preimage of , and recursively compute the extended monic gcd of and |\>> over |\>>, using directed evaluation of a computation tree for extended gcds, with the directed splitting |\>|)>t-1>> as extra input. Let |\>|)>t-1>> denote the directed splitting obtained in return and let ||\>|>t-1>> be its principal branch. This extended gcd computation also returns a monic polynomial |\>|]>>, and in |\>|]>> such that the following Bézout relation holds: <\equation*> g=U*>+V*|\>, where >\\|\>\|\>>> and |\>\\|\>\|\>>|\>|)>>. Let |\>\\|\>\|\>>|\>|)>>, |\>\\|\>\|\>>|\>|)>>, so that the Bézout relation |\>*|\>+|\>*|\>> holds. Compute the reduced representations of >>, |\>>, |\>>, |\>>, and (recall that we delayed these reductions), and then compute|\>/g>. Deduce the Bézout relations *g+\*g> and *h+\*h> by means of Lemma. If , then return , along with the directed splitting |\>|)>t-1>,|\>,\,\,\>|)>>, and the Bézout relation of |\>> and |\>>. If , then return >, along with the directed splitting |\>|)>t-1>,|\>,\,\,\>|)>>>, the Bézout relation of |\>> and |\>>, and the inverse |)> mod |\>> of|\>\|\>>>. If deg \>, then return , along with the directed splitting |\>|)>t-1>,,\,\>|)>>>, and the Bézout relation of > and . Otherwise return >, along with the directed splitting |\>|)>t-1>,,\,\>|)>>, the Bézout relation of > and , and the inverse |\>*U*h mod h> of|\>\|\>>>. Until the end of the paper, >,\,d;n|)>> represents a cost function for products in |\>n>> where ||\>|>t>> can be any principal branch encountered in the directed evaluation model over |)>t>>. Similarly, >,\,d|)>> is a cost function for reduced projections from > onto |\>>. <\proposition> Algorithm is correct and takes *>*log >|)>> operations in >, where >\max,\,d|)>>. <\proof> In step8 we have <\equation*> 2*deg g=2*-deg h|)>\2*-deg h|)>\deg \. Consequently, the splittings in the output are directed. In step8, the fact that |\>*U*h> taken modulo is the inverse of >> in |\>> can be verified as follows, in the same way as in section: the Bézout relation of >> and |\>> gives <\equation*> |\>*h*U*> mod h=|\>*h*g mod h, which simplifies to thanks to the Bézout relation of |\>> and |\>>. The correctness of the algorithm follows from these facts. Let us write >,\,d|)>> for the cost of the algorithm and recall that we are using the technique of delayed reductions. If then the cost is >. Otherwise, when computing extended gcds using the fast algorithm from section, step2 takes <\equation*> O>,\,d;d|)>*log d+>,\,d|)>*d|)>+>,\,d|)>*d operations in >. Step3 takes <\equation*> O>,\,d|)>*d+>,\,d;d|)>|)> further operations, and step4 takes time >,\,d;d|)>|)>>, by Lemma. Steps5to8 require >*\*d;d|)>|)>> operations in >. Therefore, there exists auniversal constant> such that <\equation> >,\,d|)>\c*>,\,d;d|)>*log d+>,\,d|)>*d|)>+>,\,d|)>*d. Proposition and Lemma lead to <\eqnarray*> >,\,d;d|)>>||*>*\*d|)>|)>>>|>,\,d|)>>||*>*\*d|)>|)>,>>>> whence <\equation*> >,\,d|)>\c*C*>*\*d|)>*log d+>,\,d|)>*d, for some universal constant >. Using 1>, unrolling the latter inequality leads to the claimed bound. As before, let |)>t>> be a separable tower with defining polynomials > of degree \2>>, and denote d*\*d>. At the end of adirected evaluation, we must recover the tower factorization of|)>t>> induced by the directed splitting. We also need efficient routines for projecting onto the residual branches. In this subsection (and contrary to the previous subsection), we use the traditional, reduced representations for elements in towers. We begin with a simple lemma for the computation of Bézout relations induced by factorizations. <\lemma> Let \> be monic and separable of degree , and let ,\,g> be non constant monic polynomials in > such that *\*g>. Given the Bézout relation +B*f> of > and , the Bézout relations of > and > for ,s> can be computed by a straight-line program in time >*log s|)>>. <\proof> We first construct the subproduct tree of ,\,g>: it is defined as the set of the sub-products defined recursively as follows: <\itemize> the set |}>> if , the union of *\*g|}>> and the subproduct trees of ,\,g|s/2|\>>> and |s/2|\>+1>,\,g> if 1>. A straightforward divide and conquer algorithm computes all these products with >*log s|)>> arithmetic operations in >. Then, we obtain the Bézout relations for *\*g|s/2|\>>|)>>> and *\*g|s/2|\>>>, as well as for |s/2|\>+1>*\*g|)>> and |s/2|\>+1>*\*g>, in time >|)>> by Lemma. We conclude using a standard induction argument on . <\lemma> Given a directed splitting ||\>|>t>> as above, the explicitly separable factor towers |\|>t>> for ,t> and ,l> can be computed in time *>*log >|)>> by a straight-line program, where >\max,\,d|)>>. In addition, both directions of the isomorphism <\equation> \\|\>\>\ can be computed by straight-line programs in time *>*log >|)>>. <\proof> Until the end of the proof, it is convenient to keep in mind the notation for the tree factorization in Figure, associated to the directed splitting. Let us write: <\itemize> >,\,d|)>> for the cost of the construction of the explicitly separable factor towers|\|>t>>; >,\,d|)>> for the cost of the projections from > onto |\>\>\>; >,\,d|)>> for the cost of the Chinese remaindering from |\>\>\> to>. The proof is done by induction on. If , then the costs are zero. Assume now that1> and that explicitly separable factor towers |\|>t-1>> have been constructed. We thus have the following effective isomorphism: <\equation> \\\\|\>\>\. We first project |)>> and the Bézout relation |)>*\|)>+\|)>*\|)>> onto |\>|]>> and |]>>> for ,t-1> and ,l> with cost >,\,d|)>*d|)>>. This already gives the defining polynomials of >> over >> for ,t-1> and ,l>, along with the corresponding Bézout relations. We next project the polynomials of |\>> onto |\>|]>>, namely <\equation*> |\>\\\|\>>|)>, for ,l>, using >,\,d|)>*d|)>> operations in > (it is better to use Lemma in practice, but the present bound in terms of >> simplifies the analysis). From the already computed \|\>>|)>>, \|\>>|)>>, and \|\>>|)>>, we deduce the Bézout relations of |\>> and |\>> for ,l>, by means of Lemma, in time <\equation*> O|\>>|)>*log d|)>. Overall, we have shown that there exists a universal constant > such that <\equation> >,\,d|)>\c*>,\,d;d|)>*log d+>,\,d|)>*d|)>+>,\,d|)>. Let us now consider both directions of the isomorphism. Given \>, represented by \|]>d>>, we compute the projections >\\\|\>>> and \\>> for ,t-1> and ,l> in time >,\,d|)>*d|)>>; this already gives the images of into > for ,t-1> and ,l>. Then we compute the remainders of >> modulo |\>> for ,l> in time |\>>|)>*log d|)>>. So there exists a universal constant > such that <\equation> >,\,d|)>\c*>,\,d;d|)>*log d+>,\,d|)>*d. For the inverse Chinese remaindering problem, we are given \\> for ,l>, and \\> for ,t-1> and ,l>. We have at our disposal \|\>>|)>>, its factors |\>> for ,l> and the Bézout relation of \|\>>|)>> and \|\>>|)>>. We compute \|\>|]>/\|\>>|)>|)>> whose projections are > for ,l>: <\equation*> A=*\\|\>>|)>*|\>|)> rem |\>|)>*\|\>>|)>||\>>, where > (resp. >) is the canonical preimage of > (resp. of >). Computing > costs |\>>|)>*log d|)>>; see10.20>. The isomorphism gives rise to the isomorphism <\eqnarray*> >|||]>/|)>|)>>>||>||]>/\\>|)>|)>|)>>>||>||\>|]>/\|\>>|)>|)>|)>\>\|]>/\\>|)>|)>|)>,>>>> whose right-hand side contains ,|)>t-1,2\k\l>|)>>. We finally recover the image of this element in > using > recursive calls of the Chinese remaindering procedure. Altogether, this shows that there exists auniversal constant > with <\equation> >,\,d|)>\c*>,\,d;d|)>*log d+>,\,d|)>*d. By using 1>, inequality and Proposition give <\eqnarray*> >,\,d|)>>||C*>*\*d|)>*d*\*d*log d|)>>>|||*>*log >|)>.>>>> Similarly, the relation yields <\equation*> >,\,d|)>=O*>*log >|)>. Finally, using our assumption that \2> for ,t>, the relation implies that <\equation*> >,\,d|)>=O*>*log >|)>. We are now ready the state the main complexity result of this section, in terms of the detailed cost functions from section. <\theorem> Let |)>t>> be an explicitly separable tower of degree dim> \>, let >\max,\,d|)>>, and let be a computation tree over >-algebras of detailed cost ,\,\,\,\|)>>. Then the panoramic evaluation of over > using Algorithm, along with the computation of auxiliary data, requires <\equation*> O*d++\|)>*C*>++\|)>*C*>*log >|)>*log d|)> operations in >. Let \\\\\\>> denote the panoramic splitting in the output. By means of the auxiliary data, conversions in both directions of this isomorphism can be done in time <\equation*> O*>*log >*log d|)>. <\proof> The proof is very similar to the one of Theorem. It is straightforward whenever =0>, so we may freely assume \0> from now. Using redundant representations, the directed evaluation of over > requires the following operations in>: <\itemize> *d|)>> operations for the nodes of type in \\\>; *C*>|)>> operations for the nodes of type > by Proposition; *C*>*log >|)>> operations for the zero-tests and inversions by Lemma and Proposition; *C*>|)>> operations to reduce the output values, by Lemma. At the end, the directed splitting <\equation> \\\\\\\\\> satisfies <\equation> >dim> \\ddim> \\d/2i=1,\,\. The finalization of the residual branches ,\,\>> takes time *>*log >|)>> by Lemma. In step 2 of Algorithm we next project the > input values of the computation tree to the residual algebras ,\,\>>. Again by Lemma, this can be done in time *C*>*log >|)>>. Let > denote the cost function of one panoramic evaluation of over a >-algebra of dimension d>. The above analysis shows the existence of a universal constant suchthat <\eqnarray*> >|>|*d++\|)>*C*>++\|)>*C*>*log >|)>+>> \|)>.>>>> Unrolling this inequality at most ||\>> times, thanks to, the claimed complexity bound follows. Let > denote the cost function of the conversions between > and a panoramic splitting. Using Lemma, we conclude that <\eqnarray*> >||*>*log >|)>+>> \|)>>>|||*>*log >*log d|)>,>>>> again thanks to. Before we turn to the more technical topic of speeding up computations in algebraic towers, we will have a short to study primitive tower representations. The results in this section are essentially from3 and4.1>, although we slightly generalized some of them. Let > be an effective >-algebra and let > be an effective >-algebra with an explicit basis,\,b>. We start by recalling the main result from 3> about the evaluation of multivariate polynomials in,\,x|]>> at points in >. This can in particular be used in order to compute so-called multivariate modular compositions. We recall that>>(>>) stands for the number of operations in > that are required in order to multiply two elements in> ( >). We assume that >\r\*>> and that additions and subtractions in > and> are cheaper than multiplications. <\proposition> Let > be an effective >algebra of rank, whose basis is explicitly given. Let \,\,x|]>> with > A\d> for ,t>, and let ,\,a\\>. If d*\*d=O>, then A,\,a|)> can be computed by a straight-line program in time <\equation*> O>*+>*r*d-1>|)>. <\proof> The case corresponds to the classical baby-step giant-step algorithm over>; see for instance3.1>. The extension to 2> has been designed in3.2>. In3.3>, the assumption \2> for ,t> was used for convenience. But if =1> for some , then > does not actually appear in , so discarding> is free of charge in the straight-line program model. The main difference with is that we will consider primitive tower over arbitrary >algebras> instead of fields >. In the same spirit as section, it will also be convenient to also integrate the idea of redundant representations in the definition. From an abstract point of view, given two effective >-algebras > and >, we may use elements in> as a redundant representation of elements in > if we have an effective monomorphism :\\\> and an effective epimorphism :\\\> such that \\>> is the identity map of >. We say that > is an of >. We will write \\|)>>> ( \\|)>>) for the cost of one evaluation of > ( >), and we denote \\|)>>\max\\|)>,\\|)>|)>>. From now on, assume that > is a product of separable field extensions of >. We consider a tower of ring extensions of > of the form \\>, \\|]>/|)>|)>> for ,t>, where > is monic and explicitly separable of degree>, which means that there exists a Bézout relation *\+\*\> with \\|]>d>> and \\|]>d-1>>. <\definition> A of |)>t>> consists of: <\itemize-dot> A >-algebra >, a monomorphism :\\\>, and an epimorphism :\\\> such that \\> is the identity map of >. Linear forms |)>\x>, ,\,x|)>\x+\*b,\,x|)>> with \\>, for ,t>. Monic polynomials \\|]>>, for ,t>. \\|]>d*\*d>>>, for ,t> and ,i>. Writing > for the class of > in \\|]>/|)>|)>>, we assume that these data satisfy the following properties for ,t>: <\description-compact> >>>The following map > is a monomorphism that extends >: <\eqnarray*> :\>|>|>>|>|>||)>,i|)>.>>>> >>>The following map > with \\=Id>> is an epimorphism that extends >: <\equation*> |||||||:\>|>|>>|>|>|,\,\|)>.>>>>> >>>,\,\|)>|)>=\>. The polynomials > are called of the > in terms of >. In terms of the triangular set |)>t>> defined in the introduction (> is the canonical preimage of > in ,\,x|]>>), an element \> is represented by a polynomial ,\,\|)>>> with \,\,x|]>> defined modulo ,\,T|)>>. So the conversion of \>> into an element of > boils down to evaluating |)>,\,\|)>|)>> modulo |)>>. The backward conversion consists in evaluating the image > of a univariate polynomial \|]>d>> at ,\,\|)>>. Both conversions are instances of multivariate modular composition problems that can be handled using Proposition. More precisely: <\proposition> Assume that we are given: <\itemize> |\|>t>> in terms of the defining polynomials |)>t>>, and |)>t>> in terms of ,\,\>, |)>t>> and |)>i\t>>, such that |)>t>> is a primitive tower representation of |\|>t>>. Then there exist straight-line programs for which: <\itemize> One evaluation of > takes >*d>|)>+d*\\|)>> operations in >. The images \\|)>> for ,t> can be computed in time >*d>|)>+2*d*\\|)>>. Given ,\,\>, one evaluation of > can be done in time >*d>|)>+d*\\|)>>. <\proof> If =1> for some , then > does not actually appear in polynomial representations of elements in >. In the computation tree model, we may suppress such indices without any cost. Without loss of generality we may therefore assume that \2> for ,t>. The complexity bound for one evaluation of > with t> is a direct consequence of Proposition. Indeed, any element in > can be represented as ,\,\|)>>, where \,\,x|]>>> admits partial degrees d> in > for ,i>. Now we can compute <\equation*> B\\|)>,\,\|)>|)> mod \|)>\\|]>d*\*d> in time <\eqnarray*> ||>**\*d|)>+-|)>>+>**\*d|)>>|)>+d*\*d*\\|)>>>|||>**\*d|)>>|)>+d*\*d*\\|)>,>>>> since \>. We finally notice that ,\,\|)>|)>=B|)>>. For ,t>, the map > extends coefficientwise into a map |]>\\|]>>. We may thus convert the minimal polynomial \\|]>> of > over > into a polynomial \\|]>> in time <\equation*> O>**\*d|)>>*d|)>+d*\*d*\\|)>. The computation of ,\,\> then takes time >*d>|)>+2*d*\\|)>>, since \2> for all. In order to evaluate > at an element in >, we write \|]>d>> for the preimage of and observe that <\equation*> \=\,\,\|)>|)>=\+\*b,\,\|)>|)>. We first evaluate at +\*\> in |]>=\|]>|]>>, where > is the class of > in |]>/|)>|)>>. This takes time >*d>|)>> by Proposition and yields a polynomial <\equation*> |)>\B+\*\|)> mod \|)>. Since \\=Id>>, we next notice that <\equation*> \|)>|)>=\+\*\|)>|)> mod \|)>, so the preimage in |]>> of |)>|)>> is <\equation*> \+\*b,\,\|)>|)> mod \|)>, which represents >. Applying > to the d> coefficients of > costs *\\|)>>. Altogether, this proves the existence of a universal constant such that <\equation*> \\|)>>\c>*d>+d*\\|)>. We conclude that> can be computed in time <\eqnarray*> |||>*d>+d*>*|)>>+\+d*\*d*>**\**d|)>|)>>|)>+d*\\|)>>>|||>*d>*>+\+*\*d|)>>|)>|)>+d*\\|)>>>|||>*d>|)>+d*\\|)>,>>>> using our assumptions that \> and \2> for all . If =\=\> is a field, then our definition of primitive tower representations of |)>t>> coincides with the one from2.2> whenever the > are isomorphisms. If> has sufficiently many elements, then primitive tower representations can for instance be computed using linear algebra techniques. For efficiency reasons, we will rely on the following result that will be used later with a parametric algebra in the role of >. <\proposition> 4.4>> Assume that > is a field of cardinality \>. Then a primitive tower representation of |)>t>> can be computed using |)>> inversions and zero-tests in >, plus >|)>*log d|)>> ring operations in >. <\remark> Checking that the deterministic algorithm underlying Proposition fits the computation tree model is straightforward and left up to the reader. <\remark> Proposition admits a randomized variant4.4>: if \2*>>, then a primitive tower representation of |)>t>> can be computed by arandomized Las Vegas algorithm using an expected number of > inversions and zero-tests in > plus >|)>*log d|)>> arithmetic ring operations in >. It is more subtle to regard such randomized variants as computation trees. Although our model does not provide us with an instruction to compute random elements of >, nothing prevents us from adding a \Ppool\Q of randomly chosen elements to the input. Since randomized Las Vegas algorithms may fail for certain random choices, they typically loop until suitable random numbers are drawn. As explained in Remark, we may unroll such loops to make things fit in our computation tree model, that we can provide an absolute bound on the number of times that we have to run the loop. In our case, we claim that such an absolute bound indeed exists. Following 4.3>, the construction is incremental in : assuming that ,\,\>> already found, one has to pick up a suitable value of > in a subset > of > of cardinality >. The crucial observation is that a suitable value always exists in this finite set >, which bounds the number of random values that have to be tried. With > ordered randomly, > can actually be found with a bounded number of expected trials. The suboptimality of the complexity bounds of Proposition and of Theorem appears when the height of the tower gets as large as |log d|\>>. In fact, if indeed gets large, then many of the > are necessarily small. This section is devoted to an efficient solution to this issue. Roughly speaking, as long as a product of the form *\*d> is reasonably small, it turns out to be favorable to change the given representation of =\,\,\|]>> into a more efficient primitive element representation \\|]>>. Repeating this operation as many times as necessary, the original tower |)>t>> is replaced by an equivalent tower|)>s>> of much smaller height and for which all defining polynomials have sufficiently large degree. Such were first introduced in4.2>. In this section, we will further refine the concept and show how to use such towers in combination with directed evaluation. Throughout this section, we carry on with the notations from section: the original tower |)>t>> is explicitly defined by ,\,\>, and we set \deg \> for ,t>. As before, we will assume that 2> and that \2> for ,t>. In particular, *\*d\2>. In this subsection, we extend the notion of accelerated towers from4.6> and study accelerated tower arithmetic. Let |)>t>> be an explicitly separable tower over>, and let \1>. By4.7>, there exists a sequence of integers \i\\\i=t> of length <\equation> s\3*>+1, such that, for ,s>, we have <\equation> i\i+1\e\\, where \d+1>*\*d>>. In this subsection, we assume that the sequence \\\i> has been fixed once and for all. <\definition> Let ,s|}>> and consider a factor tower ||\>|>i>> of |)>i>>. Then the subsequence |)>r>> induces a family of towers |\>>|)>+1\k\i>> over |\>>> for ,r>. An for ||\>|>i>>, and with respect to the sub-sequence |)>r>>, consists of a family of primitive tower representations of these towers |\>>|)>+1\k\i>> for ,r>. More precisely, these representations comprise the following data: <\itemize> A tower |)>r>> over > with defining polynomials >,\,\>>, where \\>|]>/>>|)>|)>> and >\\>|]>>, and such that >\e>. The class of >> in > is written >. For ,r>: <\itemize> Linear forms +1>=x+1>>, =x+\*b> over > for +2,\,i>, \\|]>> for +1,\,i-1>, \\|]>d+1>*\*d>>> for +1,\,i> and +1,\,k>. Let > represent the identity map of >. For ,r> and +1,\,i>, these data induce the following monomorphism that extends >>: <\eqnarray*> ||:|\>>|>||]>/|)>|)>>>||\>>|>||)> l=i+1,\,k.>>>> Let > represent the identity map of >. For ,r> and +1,\,i>, we also have the following epimorphism that extends >>: <\eqnarray*> :\|]>/|)>|)>>|>||\>>>|>|>||\>+1>,\,|\>|)>,>>>> and \\=Id|\>>>. For ,r> and +1,\,i>, we finally have <\equation*> \-1>,\,\|)>|)>=\. In particular, for ,r>, we have the following monomorphism that extends >>: <\eqnarray*> >:|\>>>|>|=\>|]>/>>|)>|)>>>||\>>|>|,l>>|)>+1,\,i|)>>>|>|\>+1>,\,|\>>|)>>|>|>.>>>> When , taking <\equation> \\d>,\\> yields <\equation> s=O>|)>,C=exp|)>|)>=d|)>>. whence products in > can be computed using |)>>=O>|)>> operations in >, by Proposition. The worst case complexity of products in |)>s>> is therefore asymptotically better than in ||\>|>t>>, which explains the terminology of \Paccelerated towers\Q. Let us now detail how to make elements in ||\>|>i>> benefit from this acceleration. <\lemma> Let |)>r>> be an accelerated tower for ||\>|>i>> as in Definition. Given r> and \i\i>, conversions between |]>=\|]>/|)>|)>> and |\>> > and > can be done by straight-line programs in time *>*\*d|)>*\-1>|)>>. <\proof> The proof is adapted from4.8>. Let us first assume that the polynomials \\|)>> have been precomputed for ,i>. By Proposition,\ <\eqnarray*> >>||*>*\*e|)>|)>,>>>> and by Proposition, we have\ <\eqnarray*> |\>\\|]>|)>>||>*+1>*\*d|)>>|)>+>\\|)>*d+1>*\*d>>|||*>*\*e|)>*+1>*\*d|)>>|)>+>\\|)>*d+1>*\*d.>>>> If =i+1> then such conversions simply cost >\\>|)>*d+1>*\*d>. Otherwise we have \\> by (). In both cases it follows that <\eqnarray*> |\>\\|]>|)>>|>|*>*\*d|)>*\-1>+>\\|)>*d+1>*\*d,>>>> for some universal constant . Unrolling the latter inequality, while taking into account that =\=\> and 1>, we deduce that <\eqnarray*> |\>\\|]>|)>>|>|*>*\*d|)>*\-1>>>|||d+1>*\*d**>*\*e|)>*\-1>+e*>\\|)>|)>>>|||+C|)>*>*\*d|)>*\-1>+>\\|)>*e*d+1>*\*d>>||>|>>|||*>*\*d|)>*\-1>|)>.>>>> Finally, given +1,\,i|}>>, we notice that \\|)>> can be precomputed in time <\equation*> O>*+1>*\*d|)>>|)>+2*>\\|)>*d+1>*\*d=O*>*\*d|)>*\-1>|)>, by Proposition, again by distinguishing the cases when =i+1> and \i+1>. Consequently, the total cost of these precomputations is <\equation*> O+1>|)>>C*>*\*d|)>*\-1>|)>=O*>*\*d|)>*\-1>|)>. <\proposition> Let |)>r>> be an accelerated tower for ||\>|>i>> as in Definition. Given r> and \i\i>, products in |\>> can be computed by a straightline program in time <\equation*> |\>>=O*>*\*d|)>*\-1>|)>. Two polynomials of degree n> over |\>> can be multiplied by a straight-line program in time <\equation*> |\>>=O*>*\*d|)>*\-1>*n+>*\*d*n|)>|)>|)>. <\proof> One conversion between |\>> and |]>> can be done in time <\eqnarray*> |\>\\|]>|)>>||*>*\*d|)>*\-1>|)>>>>> by Lemma. On the other hand, Proposition yields <\eqnarray*> >|]>>>||*>*\*d|)>|)>>>|>|]>>>||*>*\*d*n|)>|)>,n\0.>>>> Combining the latter costs, we deduce that <\eqnarray*> |\>>>|||\>\\>|]>|)>*n|)>+>|]>>>>|||*>*\*d|)>*\-1>*n+>*\*d*n|)>|)>|)>,>>>> and the claimed cost for |\>>> corresponds to setting . One motivation behind Definitions and with respect to the less general definitions from is to allow for redundant representations. More precisely, we have: <\lemma> Let |)>r>> be an accelerated tower for ||\>|>i>> as in Definition. Then |)>r>> is an accelerated tower for any factor tower of ||\>|>i>>. <\proof> A tower factor ||~>|>i>> of ||\>|>i>> is a tower factor of |\|>i>>. Let |~>\|\>>:|~>\|\>> denote the canonical monomorphism, then |\>\|~>>\\|~>\|\>>> is the identity of|~>>. Setting |~>\\> we first verify by induction that <\eqnarray*> |~>:|~>>|>||]>/|)>|)>>>||~>>|>||)> +1,\,k|)>>>>> is a monomorphism that extends |~>>>, for +1,\,i>, since |~>=\\\|~>\|\>>>. Let |~>> represent the identity map of >. For ,r>, we define the epimorphism |~>>, for +1,\,i>, that extends |~>>>: <\eqnarray*> |~>:\|]>/|)>|)>>|>||~>>>|>|>||~>+1>,\,|~>|)>.>>>> Since |~>=\|\>\|~>>\\>, we deduce that |~>\|~>> is the identity map of |~>>. Notice that the tower |)>r>> is only used for the acceleration of arithmetic operations; we do not require this tower to be separable. Writing |\>> for the image of |\>>> in >, our use of redundant representations also makes it unnecessary to determine the defining polynomials of ||\>|>r>>. Although the computation of such defining polynomials |\>> along with Bézout relations for |\>> and \ |\>> would be convenient for speeding up multiplications in |\>>, it seems tricky to integrate these computations without deteriorating the overall complexity. When reduced, non-redundant representations are explicitly required, we will resort to the following counterpart of Lemma: <\lemma> Let |\>|)>i>> be a factor tower of |)>i>>, and let |)>r>> be an accelerated tower for |\>|)>i>> as in Definition. Given r> and \i\i>, the projection of an element \> onto|\>> can be computed by a straight-line program in time *>*\*d|)>*\-1>*log \|)>>. <\proof> The proof is the same as in Lemma, except that we appeal to accelerated products |\>>=O*>*\*d*n|)>*\-1>|)>> of Proposition. The cost of the projection thus becomes: <\eqnarray*> \|\>|)>>|||\>>|)>*d*\*d|)>>>|||+1>|)>>C*>*\*d|)>*\-1>|)>>>|||C*>*\*d|)>*\-1>*-i|)>|)>.>>>> Now() yields -i=O|)>> for ,j>. Since 1>, the claimed bound follows. <\proposition> Let |\>|)>i>> be a principal branch encountered in a directed evaluation over|)>i>>, and let |)>r>> be an accelerated tower of |\>|)>i>>, as in Definition. Given r> and \i\i>, one directed zero-test or inversion can be done in time <\equation*> O*>*\*d|)>*\-1>*log \*log >|)>. <\proof> We adapt the proof of Proposition so as to benefit from accelerated products. From Proposition we have <\equation*> >,\,d;n|)>=O*|>*\*d*n|)>*\-1>|)>|)>, and from Lemma we have <\equation*> >,\,d|)>=O*>*\*d|)>*\-1>*log \|)>. Consequently, the relation implies the existence of a universal constant such that <\eqnarray*> >,\,d|)>>||>,\,d;d|)>*log d+>,\,d|)>*d|)>+>,\,d|)>*d>>||>|*>*\*d|)>*\-1>*log \*log d+>,\,d|)>*d.>>>> Unrolling the latter inequality yields <\eqnarray*> >,\,d|)>>||+1>|)>>C*>*\*d|)>*\-1>*log \*log d|)>>>|||C*>*\*d|)>*\-1>*log \*log >|)>>>|||*>*\*d|)>*\-1>*log \*log >|)>,>>>> while using the facts that 1> and -i=O|)>> for ,j>, by(). Now that we have seen how to benefit from accelerated arithmetic, let us show how to construct accelerated towers. We use induction on the height, in combination with Proposition. As usual, all computations in the directed model are done using the redundant representation. <\specified-algorithm> <\description-compact> An explicitly separable tower |)>t>> and a sequence of integers i\\\i=t>. A directed splitting of |)>t>> with principal branch ||\>|>t>> and an accelerated tower |)>s>> for ||\>|>t>>. <|specified-algorithm> <\enumerate> If , then return > for the directed splitting along with an empty accelerated tower. Otherwise 1>; recursively apply the algorithm to |)>i>> and i\\\i>>. Let|~>|)>i>> represent the directed splitting of |)>i>> obtained in return, let||~>|>i>> be the principal branch, and let|)>s-1>> be the accelerated tower for ||~>|>i>>. Let +1>,\,P>> be the canonical preimages of +1>,\,\>> in >+1>,\,x>|]>>; compute +1>\\>\|~>>>+1>|)>>,,>\\>\|~>>>>|)>>. By directed evaluation over >>, starting with the directed splitting |~>|)>i>>, compute a primitive tower representation for <\equation*> |~>>+1>|]>/+1>|)>\\\|~>>+1>,\,x>|]>/+1>,\,Q>|)>, seen as a tower over |~>>>. Let |\>|)>i>> be the directed splitting obtained in return and let ||\>|>i>> be the corresponding principal branch. The latter primitive tower representation consists of <\itemize> Linear forms +1>=x+1>>, =x+\*b> over > for +2,\,i>; >\|\>>|]>> for +1,\,i>; >\|\>>|]>d+1>*\*d>>> for +1,\,i> and +1,\,k>. With the notation of Definition, we set \\>>|)>> for +1,\,i> and \\>>|)>>> for +1,\,i> and +1,\,k>. Compute |~>>\|\>>>+1>|)>,\,\|~>>\|\>>>>|)>> and define, for +1,\,i>: <\itemize> |\>> as |~>>\|\>>>+1>|)>> regarded as in |\>|]>>; |\>\|\>|]>/|\>|)>|)>>. Complete the tower ||\>|>t>> with the projections of the Bézout relations of > and > over|\>>>; return this tower, ||\>|>i>,||\>+1>|>,\,|\>>|)>>, and |)>s>>. <\proposition> If \>, then Algorithm is correct and runs in time <\equation*> O*>*\+1>*log*>|)>|)>, for a sequence of integers |)>s>> that satisfies)>. <\proof> When entering step5, |)>s-1>> is an accelerated tower for ||\>|>i>>; so we have the monomorphism >:|\>>\\> and the epimorphism >:\\|\>>> such that >\\>> is the identity map of |\>>>. We also have the following isomorphisms for +1,\,i>: <\eqnarray*> |\>\|\>>|\>+1>,\,|\>|]>>|>||\>>|]>/>|)>|)>>>||\>>|>|>|)> mod \>|)>+1,\,k|)>.>>>> So the following morphisms are monomorphisms that extend >:|\>>\\>, for +1,\,i>: <\eqnarray*> :|\>>|>||]>/|)>|)>\\|]>>>||\>>|>||)>+1,\,k|)>>>||\>+1>,\,|\>|)>>|>|.>>>> Let <\eqnarray*> :\|]>>|>||\>>>|>|>||\>+1>,\,|\>|)>.>>>> We observe that > extends >> and that <\eqnarray*> \\|)>|\>|)>>|||)>|)>>>|||>|)>|\>+1>,\,|\>|)>|)>>>|||>>>|)>|)>|\>+1>,\,|\>|)>|)>>>|||>|\>+1>,\,|\>|)>|)>=|\>.>>>> This completes the correctness proof. Step1 takes constant time. In step3, the projections require <\equation*> O+1>>C*>*\*d>|)>*d+1>*\*d*\-1>*log \|)>=O*>*\-1>*log \|)> operations in >, by Lemma and the assumption that \2> for ,t>. Notice that the same bound holds for step6. Step4 is free of charge whenever =i+1>. Otherwise \\> holds by(). During the directed evaluation of step4, one product in the principal branch takes *>*\*e|)>*\-1>|)>> operations in> by Proposition, and the cost of one directed inversion is *>*\*e|)>*\-1>*log \*log >|)>> by Proposition. Consequently, step4 runs in time <\eqnarray*> ||*>*\*e|)>*e*\-1>*log \*log >+C*>*\*e*e|)>*e*\-1>*log \|)>>>|||*>*\*e|)>*e*\-1>*log \*log >+C*>*\*e|)>*e*\-1>*log \|)>>>|||*>*\>*log \*log >+C*>*\+1>*log \|)>>>|||*>*\+1>*log*>|)>|)>,>>>> by Proposition and. In step5 we perform <\equation*> O+1>+2*d>*d+2>+\+-i|)>*d>*\*d>|)>=O*log \|)> conversions from |\>>> to >, which amount to <\equation*> O*>*\*e|)>*e*\-1>*log \|)>=O*>*\-1>*log \|)> operations in > by Lemma. <\remark> If \2*>, then the randomized Las Vegas version of Proposition (see Remark) may be used in Algorithm, so that step4 has an expected cost <\equation*> O*>*\>*log*>|)>|)>, which still dominates the cost of Algorithm in this model. accelerated towers> In order to make the directed evaluation benefit from accelerated arithmetic, we first need to compute an accelerated tower. Then, the complexity of accelerated divisions is simply adjusted according to Proposition. At the end of acomputation, we use the following lemma in order to recover the extended tower factorization of|)>t>>, as in section. <\lemma> Given a directed splitting ||\>|>t>> as above, and an accelerated tower for its principal branch, the explicitly separable factor towers |\|>t>> for ,t> and ,l> can be computed in time *>*\-1>*log \*log >|)>> by a straight-line program, where >\max,\,d|)>>>. In addition, both directions of the isomorphism <\equation*> \\|\>\>\ can be computed by straight-line programs in time *>\-1>*log \*log >|)>>. <\proof> The algorithm is the same as in the proof of Lemma. We only revisit the cost analysis when using accelerated arithmetic. Given \i\i>, Proposition yields <\equation*> >,\,d;n|)>=O*|>*\*d*n|)>*\-1>|)>|\>, whence <\eqnarray*> >,\,d|)>>||+1>>C*>*\*d|)>*\-1>*d*\*d*log d|)>>>|||*>*\-1>*log \*log >|)>.>>>> In a similar way, we obtain <\eqnarray*> >,\,d|)>>||*>*\-1>*log \*log >|)>.>>>> We deduce that <\eqnarray*> >,\,d|)>>||*>*\-1>*log \*log >|)>.>>>> <\theorem> Let |)>t>> be an explicitly separable tower of degree dim> \>, let >\max,\,d|)>>, and let be a computation tree over >-algebras of detailed cost ,\,\,\,\|)>>, as defined in section. Assume that \>. Then the panoramic evaluation of over > using Algorithm, along with the computation of auxiliary data, requires <\equation> O*d+\*C*>*\-1>|)>*log d|)> operations in >, where <\equation*> \=\+\*log \*log >+\*log \+\*log \*log >+\*log*>|)>. Let \\\\\\>> denote the panoramic splitting in the output. Using the auxiliary data, conversions in both directions of this isomorphism can be done in time <\equation> O*>*\-1>*log \*log >*log d|)>. <\proof> The directed construction of the accelerated tower takes <\equation*> O*>*\+1>*log*>|)>|)> by Proposition. Then, we project the input values onto the principal branch, written ||\>|>t>>, in time <\equation*> O*C*>*\-1>*log \|)>, by Lemma. Let us summarize the number of operations in > needed for the directed evaluation of over >, when using redundant representations in |\>>: <\itemize> *d|)>> operations for the nodes of type in \\\>; *C*>*\-1>|)>> for the nodes of type > by Proposition; *C*>*\-1>*log \*log >|)>> for the zero-tests and inversions by Lemma and Proposition, *C*>*\-1>*log \|)>> for the reduction of the output node by Lemma. At the end, the directed splitting \\\\\\\\>> satisfies <\equation> >dim> \\d,dim> \\d/2,\|)>. Then we finalize the construction of the residual branches ,\,\>> in time <\equation*> O*>*\-1>*log \*log >|)>, by Proposition. We next project the > input values of the tree to ,\,\>>, in time <\equation*> O*C*>*\-1>*log \*log >|)>, again by Proposition. We finally perform the recursive panoramic evaluations of over ,\,\>>. The conclusion follows as in the proof of Theorem. <\remark> If \2*>, then the factor > in the definition of > can be replaced by an expected > in Theorem, by using the randomized variant from Remark for the directed construction of the accelerated tower. The following corollary simplifies the above complexity bound by tuning the parameters> and. <\corollary> For a suitable choice of >, the bound )> simplifies into <\equation*> O*d*log d|)>++\+\+\|)>*d|)>> and the bound )> into |)>>>. <\proof> It suffices to take > and as in() and(). The main result of is an efficient algorithm to compute products in separable towers of field extensions. We are now in a position to generalize this result to arbitrary explicitly separable towers. <\theorem> Let |)>t>> be an explicitly separable tower as in the introduction of this section. If \>, then products in > can be computed in time <\equation*> d|)>>. <\proof> Let \>. Applying Theorem to the straight-line program that simply computes a product, it requires *>*\+1>*log*>|)>*log d|)>> operations to compute aparametric splitting \\\\\\>>, auxiliary data, and the projections \\>> for,\>>. Using the auxiliary data, the theorem also allows us to recover from these projections using *>*\-1>*log \*log >*log d|)>> further operations in >. We conclude by taking> and as in() and(). Another interesting application that has already been discussed in the univariate case at the end of section is the computation of determinants. <\theorem> Let |)>t>> be an explicitly separable tower as in the introduction of this section. If \>, then the determinant of an n> matrix in n>> can be computed intime <\equation*> n>*d|)>>. <\proof> The proof is similar to the one of Theorem. As a final application, we revisit the matrix product. We need the following generalization of Proposition: <\proposition> With the notations of Proposition and 2>, assume that \2*d>. Then the product of two n> matrices inn>> can be computed in time <\equation*> O*n>*d+2*n*>*log d+C*n*>|)>. <\proof> We proceed along the same lines as Lebreton in3.2>; see also2.4>. Consider two matrices \n>>, we first lift the matrices to multivariate polynomial matrices in ,\,x|]>n>> of partial degrees d> in > for ,t>. We next convert these polynomial matrices to univariate polynomial matrices in 2*d>> using Kronecker substitution. We multiply these matrices using the evaluation-interpolation technique. Since > admits at least \2*d> distinct evaluation points, this can be done in time <\equation*> O*n>*d+n*>*d|)>*log*d|)>|)>. We finally convert the result back to a polynomial matrix in ,\,x|]>n>>, and we reduce each of the entries with respect to ,\,\> using the algorithm from3.2>. This reduction step requires *>*d|)>|)>> operations in>. Now our assumption that \2> for ,t> implies \d> and \d>. Using(), we conclude that the total running time is bounded by <\eqnarray*> ||*n>*d+n*>*d|)>*log*d|)>+n*>*d|)>|)>>>|||*n>*d+2*n*>*log d+C*n*>|)>.>>>> The next proposition is an example of a less straightforward use of Theorem, where we adapt the \Pacceleration factor\Q > to a specific situation, and where we wish to decrease the overhead of the accelerated towers. Precisely, after a directed construction of an accelerated tower, we obtain a directed splitting \\\\\\\\> that satisfies <\equation*> dim> \\d,dim> \\d/2,h|)>. As a byproduct, we have an accelerated tower of > of degree d> at our disposal. The recursive calls to panoramic evaluations over > for ,h> then lead to accelerated towers for each of the factor towers of |)>t>>. Let > denote a bound for the sum of the degrees of all these accelerated towers. Then we have <\equation*> \d+> \|)>+\+> \|)>. Unrolling this inequality leads to =O>, which is slightly suboptimal. We may modify the construction of accelerated towers, described in Algorithm, in order to ensure that the degree of the accelerated tower is never more than twice the degree of the principal branch before entering the evaluation of the given computation tree. This is done as follows. At the end of Algorithm, we compare the degree of the accelerated tower |)>s>> to the degree of the principal branch ||\>|>t>>. If > \\2*dim> |\>> then we are done. Otherwise, the principal branch is much smaller than > in the sense that > |\>\dim> \\d>, and we use again Algorithm in order to compute an accelerated tower for ||\>|>t>>. We carry on computing a new accelerated tower of the current principal branch in the directed model over |\|>t>> until the condition > \\2*dim> |\>> is met. By Proposition, the total cost of this process is roughly only twice as much as a single run of Algorithm since <\eqnarray*> ||*>*\+1>*log*>|)>+C*>*\+1>*log*>|)>+C*>*\+1>*log*>|)>+\|)>>>|||*>*\+1>*log*>|)>|)>.>>>> With these modifications in hand, we ensure that \2*d>. <\proposition> Let |)>t>> be an explicitly separable tower as in the introduction of this section. If \d> and >>, then two n> matrices in n>> can be multiplied in time>*d|)>>. <\proof> Let \-2|)>/-1|)>> be a fixed positive constant. Take =n>> and fix a sequence \\\i> such that() and() hold. Since >>, we observe that >. We first compute a single product in > with the sole purpose of retrieving aparametric splitting \\\\\\>>, together with the auxiliary data for efficient conversions in both directions, and an accelerated tower of height for each > of degree 2*D>, where \dim> \>; as discussed above. This precomputation takes time <\equation*> *d*\+1>|)>=+1|)>*\>|)>=-2*+1-\|)>/-1|)>>|)>=O>*d|)>. One conversion between n>> and n>\\\\>n>> also take time <\equation*> *d*\-1>*n|)>=*-2|)>>|)>=O>*d|)>. Now assume that we wish to multiply two matrices \n>>. This problem is reduced to > multiplication problems of matrices in n>> that we further transform into matrix multiplications within the corresponding accelerated towers, so Proposition, yields the cost <\eqnarray*> ||>2*n>*D+2*n*>|)>*log d+C*n*>|)>|)>>>|||*n>*d+2*n*>*log d+C*n*>|)>>>|||>*d+n*>*log d|)>>>|||>*d|)>.>>>> using the assumptions that \2> and >>. <\remark> In view of the above proposition, it is likely that determinants can also be computed in time>*d|)>>. It is an interesting question how to adapt the setting of this paper so that complexity bounds of this type can be derived. Theorems,, and show that the approach of directed evaluation allows us to compute panoramic evaluations in a time that is arbitrarily close to linear. We chose the setting of computation trees as our complexity model and it is natural to ask whether similar results hold in the RAM and Turing models. This seems plausible, although technical difficulties are likely to arise in the efficient implementation of data structures on Turing machines; see for a detailed analysis of a similar kind, but for another problem. So far, we have only addressed the sequential complexity of dynamic evaluation and its variants. It would be interesting to conduct a similar study for parallel computation models. Dynamic evaluation lends itself particularly well to parallel execution: whenever we encounter a splitting, it is natural to continue the execution of each of the branches in parallel. In the directed setting, we have to complete the execution of the principal branch in order to benefit from the fastest possible multi-remaindering. Nevertheless, this is really a trade-off, and we may very well start to execute some \Psufficiently thick\Q residual branches before completion of the principal branch. It is also important to notice that these considerations have only minor impact from the worst case complexity perspective: the opportunities for this kind of parallelism only arise when splittings actually occur. In the absence of splittings, we have to evaluate the computation tree over the full original algebra >, so the parallel complexity is really a function of the amount of parallelism that is available in and in the algebra operations of >. For our presentation, we restricted our towers to be explicitly separable from the outset. In practice, towers are usually constructed by adding new parameters that satisfy polynomial constraints one by one. These polynomials may contain multiple factors, in which case one is usually only interested in the radical ideal generated by the constraints. This more general setting can actually also be covered efficiently using our techniques. Indeed, consider an explicitly separable tower |)>t>> and a new algebraic parameter> that is subjected to |)>=0>, where \\|]>> is amonic polynomial that is not necessarily separable. Then we simply compute the separable factorization =\*\*\*\> as if > were a field (here assuming that the characteristic is zero or sufficiently large), using panoramic evaluation, together with the requested Bézout relations for the non-trivial factors \1>. Let \\\\\\>>> be the resulting splitting. Then any pair ,\|)>> with \1> gives rise to a new explicitly separable tower of height >, which allows us to recurse. In this paper, we only considered parameters that satisfy polynomial constraints, but the technique of directed evaluation naturally generalizes to various other settings. For instance, for an integer parameter \>, one may compute in /r*\> as if it were afield, so is partially factored during directed evaluations. This situation is commonly encountered in number theory and computer algebra, where the deterministic construction of\Plarge\Q prime numbers is rather expensive. Another possible extension of our work concerns real algebraic numbers in the continuation of. Another direction for future work concerns the particular kind of tower arithmetic that we build on. In this paper, we essentially combined the best previously known generic algorithms from Theorem with the idea of accelerated towers. For specific base fields>, such as finite fields or subfields of >, other efficient algorithms have been proposed for tower arithmetic. It should not be hard to combine directed evaluation with these algorithms in order to improve on Theorem and Corollary for such more specific base fields >. Finally, the recent new theoretical ideas from and this paper should also allow for more efficient software implementations, although it remains a major challenge to make this happen. In particular, this requires to implement all available approaches with care and determine the thresholds for which they are most efficient. For particularly long parametric evaluations, one may also wish to switch to towers of smaller height, and to spend more time on factoring the defining polynomials. We thank the anonymous referees for their useful comments. <\bibliography|bib|plain|direval.bib> <\bib-list|10> S.J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. , 18:147\U150, 1984. L.Blum, F.Cucker, M.Shub, and S.Smale. . Springer Science & Business Media, 2012. F.Boulier, F.Lemaire, and M.MorenoMaza. Well known theorems on triangular systems and the D5 principle. In J.-G. Dumas, editor, , pages 79\U92. U.J.Fourier, Grenoble, France, 2006. P.A. Broadbery, T.Gómez-Díaz, and S.M. Watt. On the implementation of dynamic evaluation. In A.H.M. Levelt, editor, , ISSAC '95, pages 77\U84, New York, NY, USA, 1995. ACM. P.Bürgisser, M.Clausen, and M.A. Shokrollahi. , volume 315 of . Springer-Verlag, 1997. D.G. Cantor and E.Kaltofen. On fast multiplication of polynomials over arbitrary algebras. , 28:693\U701, 1991. M.Coste, H.Lombardi, and M.-F. Roy. Dynamical method in algebra: Effective nullstellensätze. , 111(3):203\U256, 2001. X.Dahan, M.Moreno Maza, É.Schost, and Yuzhen Xie. On the complexity of the D5 principle. In J.-G. Dumas, editor, , pages 149\U168. U.J.Fourier, Grenoble, France, 2006. L.DeFeo, J.Doliskani, and É. Schost. Fast algorithms for -adic towers over finite fields. In , ISSAC '13, pages 165\U172, New York, NY, USA, 2013. ACM. J.DellaDora, C.Dicrescenzo, and D.Duval. About a new method for computing in algebraic number fields. In B.F. Caviness, editor, , pages 289\U290. Springer Berlin Heidelberg, 1985. S.Dellière. . PhD thesis, Université de Limoges. Faculté des sciences et techniques, 1999. S.Dellière. On the links between triangular sets and dynamic constructible closure. , 163(1):49\U68, 2001. C.Dicrescenzo and D.Duval. Algebraic extensions and algebraic closure in Scratchpad II. In P.Gianni, editor, '88. Rome, Italy, July 4\U8, 1988. Proceedings>, number 358 in Lect. Notes Comput. Sci., pages 440\U446. Springer-Verlag, 1989. D.Duval. Rational Puiseux expansions. , 70(2):119\U154, 1989. D.Duval. Algebraic numbers: An example of dynamic evaluation. Symbolic Comput.>, 18(5):429\U445, 1994. D.Duval and L.González-Vega. Dynamic evaluation and real closure. , 42(4-6):551\U560, 1996. D.Duval and J.-C. Reynaud. Sketches and computation\UII: dynamic evaluation and applications. , 4(2):239\U271, 1994. H.Friedman. Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory. In R.O. Gandy and C.M.E. Yates, editors, , volume61 of , pages 361\U389. Elsevier, 1971. A.Fröhlich and J.C. Shepherdson. On the factorisation of polynomials in a finite number of steps. Z.>, 62:331\U334, 1955. A.Fröhlich and J.C. Shepherdson. Effective procedures in field theory. , 248:407\U432, 1956. J.vonzur Gathen and J.Gerhard. . Cambridge University Press, New York, 3rd edition, 2013. T.Gómez-D|\>>az. Examples of using dynamic constructible closure. , 42(4-6):375\U383, 1996. D.Harvey and J.vander Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Complexity>, 54:101404, 2019. D.Harvey, J.vander Hoeven, and G.Lecerf. Faster polynomial multiplication over finite fields. ACM>, 63(6), 2017. Article52. J.vander Hoeven. . PhD thesis, École polytechnique, Palaiseau, France, 1997. J.vander Hoeven and G.Lecerf. Composition modulo powers of polynomials. In M.Blurr, editor, , ISSAC '17, pages 445\U452, New York, NY, USA, 2017. ACM. J.vander Hoeven and G.Lecerf. Modular composition via complex roots. Technical report, CNRS & École polytechnique, 2017. . J.vander Hoeven and G.Lecerf. Modular composition via factorization. Complexity>, 48:36\U68, 2018. J.vander Hoeven and G.Lecerf. Accelerated tower arithmetic. Complexity>, 55:101402, 2019. J.vander Hoeven and G.Lecerf. Fast multivariate multi-point evaluation revisited. Complexity>, 56:101405, 2020. Xiaohan Huang and V.Y. Pan. Fast rectangular matrix multiplication and applications. Complexity>, 14(2):257\U299, 1998. E.Kaltofen. On computing determinants of matrices without divisions. In P.S. Wang, editor, , ISSAC '92, pages 342\U349, New York, NY, USA, 1992. ACM. K.S. Kedlaya and C.Umans. Fast polynomial factorization and modular composition. , 40(6):1767\U1802, 2011. F.LeGall. Powers of tensors and fast matrix multiplication. In K.Nabeshima, editor, , pages 296\U303, New York, NY, USA, 2014. ACM. R.Lebreton. Relaxed Hensel lifting of triangular sets. Symbolic Comput.>, 68(2):230\U258, 2015. G.Lecerf. Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. Complexity>, 19(4):564\U596, 2003. G.Lecerf. On the complexity of the Lickteig\URoy subresultant algorithm. Symbolic Comput.>, 92:243\U268, 2019. A.Poteaux and É.Schost. Modular composition modulo triangular sets and applications. , 22(3):463\U516, 2013. A.Poteaux and É.Schost. On the complexity of computing with zero-dimensional triangular sets. Symbolic Comput.>, 50:110\U138, 2013. F.P. Preparata and D.V. Sarwate. An improved parallel processor bound in fast matrix inversion. , 7(3):148\U150, 1978. J.C. Reynolds. The discoveries of continuations. , 6:233\U247, 1993. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+tRqnglh3Bg4WG1|article|FrohlichShepherdson1955> <|db-entry> J. C. > Z.> <\db-entry|+tRqnglh3Bg4WG2|article|FrohlichShepherdson1956> <|db-entry> J. C. > <\db-entry|+tRqnglh3Bg4WG5|book|GathenGerhard2013> <|db-entry> J. > <\db-entry|+tRqnglh3Bg4WH1|article|Rey93> <|db-entry> > <\db-entry|+tRqnglh3Bg4WFq|article|CK91> <|db-entry> E. > <\db-entry|+tRqnglh3Bg4WH4|inproceedings|Gall14> <|db-entry> > > <\db-entry|+tRqnglh3Bg4WG8|article|HuangPan1998> <|db-entry> V. Y. > Complexity> <\db-entry|+tRqnglh3Bg4WGk|article|vdH:tower> <|db-entry> G. > Complexity> <\db-entry|+tRqnglh3Bg4WGi|article|vdH:kucomp> <|db-entry> G. > Complexity> <\db-entry|+tRqnglh3Bg4WGX|article|KU11> <|db-entry> C. > <\db-entry|+tRqnglh3Bg4WH7|article|PoteauxSchost2013> <|db-entry> É. > <\db-entry|+tRqnglh3Bg4WGH|article|PoteauxSchost2013b> <|db-entry> É. > Symbolic Comput.> <\db-entry|+tRqnglh3Bg4WH2|inproceedings|DDS13> <|db-entry> J. É. > -adic towers over finite fields> <\db-entry|+tRqnglh3Bg4WGQ|techreport|vdH:zcomp> <|db-entry> G. > > <\db-entry|+tRqnglh3Bg4WGN|article|vdH:ffcomp> <|db-entry> G. > Complexity> <\db-entry|+tRqnglh3Bg4WH5|article|Leb15> <|db-entry> > Symbolic Comput.> <\db-entry|+tRqnglh3Bg4WFu|inproceedings|DellaDoraDicrescenzoDuval1985> <|db-entry> C. D. > > <\db-entry|+tRqnglh3Bg4WGm|inproceedings|DuvalDicrescenzo1989> <|db-entry> D. > '88. Rome, Italy, July 4\U8, 1988. Proceedings> > <\db-entry|+tRqnglh3Bg4WGl|article|Duval1989> <|db-entry> > <\db-entry|+tRqnglh3Bg4WFw|article|Duval1994> <|db-entry> > Symbolic Comput.> <\db-entry|+tRqnglh3Bg4WGn|article|ReynaudDuval1994> <|db-entry> J.-C. > \UII: dynamic evaluation and applications> <\db-entry|+tRqnglh3Bg4WGo|article|Gomez1996> <|db-entry> |\>>az>> <\db-entry|+tRqnglh3Bg4WGp|article|DuvalGonzalez1996> <|db-entry> L. > <\db-entry|+tRqnglh3Bg4WH0|phdthesis|vdH:phd> <|db-entry> > <\db-entry|+tRqnglh3Bg4WGv|inproceedings|BroadberyDiazWatt1995> <|db-entry> T. S. M. > > <\db-entry|+tRqnglh3Bg4WGr|phdthesis|Delliere1999> <|db-entry> > <\db-entry|+tRqnglh3Bg4WGq|article|Delliere2001> <|db-entry> > <\db-entry|+tRqnglh3Bg4WFs|inproceedings|BoulierLemaireMaza2006> <|db-entry> F. M. > > J.Fourier, Grenoble, France> <\db-entry|+tRqnglh3Bg4WGt|article|CosteLombardiRoy2001> <|db-entry> H. M.-F. > <\db-entry|+tRqnglh3Bg4WGR|inproceedings|vdH:pcomp> <|db-entry> G. > > <\db-entry|+tRqnglh3Bg4WGs|article|Lecerf2003> <|db-entry> > Complexity> <\db-entry|+tRqnglh3Bg4WFr|inproceedings|DahanMazaSchostXie2006> <|db-entry> M. Moreno É. Yuzhen > > J.Fourier, Grenoble, France> <\db-entry|+tRqnglh3Bg4WFp|book|BuClSh97> <|db-entry> M. M. A. > <\db-entry|+tRqnglh3Bg4WGx|book|BlCuSm2012> <|db-entry> F. M. S. > <\db-entry|+tRqnglh3Bg4WGw|incollection|Friedman1971> <|db-entry> > C. M. E. > <\db-entry|+tRqnglh3Bg4WGV|article|vdH:cyclomult> <|db-entry> J. van der > Complexity> <\db-entry|+tRqnglh3Bg4WGO|article|vdH:ffmul> <|db-entry> J. van der G. > ACM> 52> <\db-entry|+tRqnglh3Bg4WGC|article|Lecerf2017> <|db-entry> > Symbolic Comput.> <\db-entry|+tRqnglh3Bg4WGd|article|Berkowitz1984> <|db-entry> > <\db-entry|+tRqnglh3Bg4WGy|inproceedings|Kaltofen1992> <|db-entry> > > <\db-entry|+tRqnglh3Bg4WGz|article|PreparataSarwate1978> <|db-entry> D. V. > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > ||math-font-series||W>>|35>> ||math-font-series||W>>|35>> ||math-font-series||W>>|35>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> FrohlichShepherdson1955 FrohlichShepherdson1956 GathenGerhard2013 Rey93 vdH:tower GathenGerhard2013 CK91 Gall14 HuangPan1998 vdH:tower vdH:kucomp KU11 PoteauxSchost2013 PoteauxSchost2013b DDS13 vdH:zcomp vdH:ffcomp vdH:kucomp KU11 PoteauxSchost2013 GathenGerhard2013 Leb15 vdH:tower vdH:tower DellaDoraDicrescenzoDuval1985 DuvalDicrescenzo1989 Duval1989 Duval1994 DellaDoraDicrescenzoDuval1985 ReynaudDuval1994 Gomez1996 DuvalGonzalez1996 vdH:phd DuvalDicrescenzo1989 BroadberyDiazWatt1995 Delliere1999 Delliere2001 BoulierLemaireMaza2006 CosteLombardiRoy2001 vdH:pcomp Lecerf2003 DahanMazaSchostXie2006 vdH:tower DahanMazaSchostXie2006 DahanMazaSchostXie2006 vdH:tower BuClSh97 BlCuSm2012 Friedman1971 BuClSh97 CK91 vdH:cyclomult vdH:ffmul GathenGerhard2013 Lecerf2017 Lecerf2017 Lecerf2017 Leb15 vdH:tower GathenGerhard2013 Rey93 DuvalDicrescenzo1989 BroadberyDiazWatt1995 DahanMazaSchostXie2006 DahanMazaSchostXie2006 Berkowitz1984 Kaltofen1992 PreparataSarwate1978 Berkowitz1984 GathenGerhard2013 vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower vdH:tower Leb15 vdH:tower Leb15 vdH:kucomp DuvalGonzalez1996 DDS13 vdH:zcomp vdH:ffcomp vdH:zcomp vdH:ffcomp vdH:tower <\associate|figure> |5.1>|> Example of a tree factorization of a tower of height |t=3>. |> |5.2>|> Illustration of a generic tower factorization involved in a directed evaluation. The principal branch is highlighted. |> <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Statement of the problems |.>>>>|> > |Dynamic evaluation |.>>>>|> > |Algebraic towers |.>>>>|> > |Further notations |.>>>>|> > |1.2.Previous work |.>>>>|> > |1.3.Our contributions |.>>>>|> > |math-font-series||font-shape||2.Prerequisites> |.>>>>|> |2.1.Computation trees |.>>>>|> > |Definition |.>>>>|> > |Evaluation |.>>>>|> > |Cost functions |.>>>>|> > |2.2.Univariate polynomials |.>>>>|> > |Product |.>>>>|> > |Division |.>>>>|> > |Gcd |.>>>>|> > |2.3.Towers |.>>>>|> > |math-font-series||font-shape||3.Evaluation models> |.>>>>|> |3.1.Parametric frameworks |.>>>>|> > |3.2.Unpermissive evaluation |.>>>>|> > |3.3.Panoramic values |.>>>>|> > |3.4.Directed operations |.>>>>|> > |3.5.Directed evaluation |.>>>>|> > |3.6.Fast panoramic evaluation |.>>>>|> > |3.7.Delayed reductions |.>>>>|> > |math-font-series||font-shape||4.Complexity of univariate panoramic evaluation> |.>>>>|> |4.1.Univariate parametric framework |.>>>>|> > |4.2.Main complexity result with one algebraic parameter |.>>>>|> > |4.3.Comparison with previous work |.>>>>|> > |4.3.1.Naive dynamic evaluation |.>>>>|> > |4.3.2.Dynamic evaluation using continuations or forking |.>>>>|> > |4.3.3.Specific algorithms |.>>>>|> > |math-font-series||font-shape||5.Several algebraic parameters> |.>>>>|> |5.1.Tower factorizations |.>>>>|> > |5.2.Directed evaluation in the multivariate case |.>>>>|> > |5.3.Directed zero-tests and inversions |.>>>>|> > |5.4.Finalizing the residual branches |.>>>>|> > |5.5.Panoramic evaluation |.>>>>|> > |math-font-series||font-shape||6.Primitive tower representations> |.>>>>|> |6.1.Evaluating polynomials at points in algebras |.>>>>|> > |6.2.Primitive tower representations |.>>>>|> > |6.3.Complexity of conversions |.>>>>|> > |6.4.Constructing primitive tower representations |.>>>>|> > |math-font-series||font-shape||7.Accelerated tower arithmetic> |.>>>>|> |7.1.Accelerated towers |.>>>>|> > |7.1.1.Accelerated arithmetic |.>>>>|> > |7.1.2.Redundant representations |.>>>>|> > |7.1.3.Directed zero-tests and inversions |.>>>>|> > |7.2.Directed construction of an accelerated tower |.>>>>|> > |7.3.Panoramic evaluation with |>accelerated towers |.>>>>|> > |7.4.Applications |.>>>>|> > |math-font-series||font-shape||8.Conclusion> |.>>>>|> |Acknowledgments. |.>>>>|> > |math-font-series||font-shape||Bibliography> |.>>>>|>