<\body> <\hide-preamble> >> \; holonomic functions>|||<\author-affiliation> Laboratoire d'informatique, UMR 7161 CNRS Campus de l'École polytechnique 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau >>|>> ||> >>>>>>>>>>>>>> Let > be a subfield of >. A over > is a solution to a linear differential equation , where +L*\+\+L\\|]>> is a monic linear differential operator of order. Many classical special functions, such as , , , , , hypergeometric functions, Bessel functions, the Airy function, are holonomic. Moreover, the class of holonomic functions is stable under many operations, such as addition, multiplication, differentiation, integration and postcomposition with algebraic functions. In the sequel, and unless stated otherwise, we will assume that > is the field of algebraic numbers. The only singularities of a holonomic function as above can occur at the poles of the rational functions ,\,L>; let > denote the finite set of these poles. We will say that has >> if ,\,f>|)>\\> for a certain non-singular point \\\>. In this paper, we are interested in the design of efficient algorithms for the numeric evaluation of such a function , with a particular focus on high precision and uniform efficiency as afunction of the argument . For a fixed non singular evaluation point, say \\\>, an efficient general purpose algorithm was first given by the Chudnovsky brothers. More precisely, in the case when =\|]>>, they proved that an -bit approximation of > can be computed in time *log n|)>>. Here > stands for a complexity bound for integer multiplication and it has recently been proved that one may take =O> n>|)>>, where > n=min \:|k>>\log|)>\1|}>>. The Chudnovsky\UChudnovsky algorithm was rediscovered in and generalized to the case when > is the field of algebraic numbers. An early precursor and further variants can be found in. In order to design uniformly efficient evaluation algorithms, it is crucial to control the efficiency when approaches one of the singularities in >. Actually, one first question concerns the computation of the limit of a holonomic function at a singularity if this limit exists. This was first done in for so called regular singularities (achieving the same complexity bound as for non singular points), and in for irregular singularities (in which case we showed that -bit approximations of limits can be computed in time *log n|)>>). We refer to for the definitions of the concepts of regular and irregular singularities. The main aim of this paper is to achieve the same kind of complexity bounds uniformly in . Such bounds need to be stated with a lot of care. First of all, a holonomic function such as =exp z> grows exponentially fast at infinity: given the -bit number >, one needs |)>> bits to merely write down the closest integer approximation |exp|)>+|\>>> of >. Using floating point approximations for both and > does not help, since asimilar explosion then occurs for the exponent. But we may hope for a good uniform complexity bound if we use fixed point approximations for and floating point approximations for>. Another complication is due to the number zero, which should be regarded as a singularity when using floating point representations: it is difficult to compute accurate floating point approximations for > if is close to a zero of . Predicting the exact locations of zeros of holonomic functions is a notoriously difficult problem. Even the basic question to decide whether =0> for \\\> admits no algorithmic answer for the moment. Nevertheless, the number is often the approximation of some other complex number with a precision ofbinary digits behind the dot. In that case, it is natural to consider the more general evaluation of on the ball |)>> with center and radius>, and to require that admits no zeros on this ball. We are almost in a position to state the main result of this paper. Let =\*2>> be the set of numbers. Given \\>, we denote by =|log +1|)>|\>+> the bitsize of . Given *y\\|]>>, we also denote =size+size>. The set =\*2>> of numbers is defined in the same way as >, but the exponent of a floating point numbers \\> is represented in binary notation, so that the bitsize of is now fiven by =|log +1|)>|\>+|log +1|)>|\>>. Let \\> be the point at which we specified the initial conditions of . We define > to be the open subset of > of all points such that the straightline segment ,z|]>> from > to does not intersect >. We take to be the unique solution of on > that matches the prescribed initial conditions at >. Let \\> denote the set of zeros of . The main theorem of this paper is the following. <\theorem> There exists an algorithm that takes \> and \\\|]>> with |)>>\ \\\|)>=\> and \n> on input and that computes \|]>> on output with -v|\|>\2*|\|>>. Moreover, the running time of the algorithm is bounded by *log n|)>>, uniformly in . As long as remains in a compact subset of > in Theorem, the conclusion essentially follows from the existing complexity bounds in; using a refinement of the complexity analysis from, one even obtains the stronger complexity bound *log n|)>> for the evaluation of . Using the techniques from, these complexity bounds generalize to subsets \> of >, where is a compact set that contains none of the irregular singularities of>. If the point at infinity is a regular singularity, then the bound also applies on subsets U:\M|}>> for sufficiently large , modulo the change of coordinates z>. The above discussion shows that the proof of Theorem involves two main difficulties: controlling the complexity near irregular singularities and controlling the complexity of evaluating > near zeros of . For the first task, we will adapt the technique of accelero-summation from. For the second task, we rely on the idea that,f>> can never simultaneously become \Psmaller than expected\Q. A precise statement will be presented in Section; this statement can be regarded as a quantitative version of the well-known property that,f>>> cannot vanish simultaneously unless vanishes itself. Let us return to the evaluation of near an irregular singulary, say \>. At the origin, it is well-known that admits a basis of formal solution of the form <\equation*> =|~>*z>*\>|)>> for , where |~>\\>|]>|]>>, \\>, >|)>\\>|]>>, \\>>, and where \>> for some \\>. In, it is shown that the series |~>> are accelero-summable and that we can associate actual functions > to them that are defined on sectors of the form <\equation*> \,\>\*\>:r\,\\-\,\+\|]>|}>. Moreover, a finite number of these sectors can be made to cover a punctured neighbourhood of the origin. One crucual step toward the design of an efficient evaluation algorithm for on such a sector is to deal with the special case when > for some , which further reduces to the case when >. In the remainder of this paper, we will assume that the reader is familiar with and the notations that we used there. For simplicity, we will also restrict to accelerations and Laplace transforms such that we integrate on the positive real axis. Using a change of variables u*z> for a suitable \>>, this entails no loss of generality. More precisely, we assume that we are in the following situation. The function is the result <\eqnarray*> >|||\>>\|\>,k>\\\|\>,k>\|\>>|)>|)>>>>> of an accelero-summation process with critical times =>,\,z=>>, \\\k>, and all integrals taken on the positive real axis. The accelero-sum is defined in some sector <\equation*> \>\\> for any \0> with \k*\/2>. For any fixed \|]>\\>>, the accelero-summation process from provides us with an algorithm to compute digits of > in time *log n|)>>. In Section, we will show that this complexity is uniform in , provided that >\\/> for some computable constant \0>. In other words: accelero-summation is a good numerical scheme under the condition that we really need a lot of digits. In, we also showed that the technique of \Psummation until the least term\Q allows to compute digits of > in time *log n|)>>, provided that >\\/> for some computable constant \0>. This complexity bound is also uniform in . The above uniform complexity bounds still leave a gap for precisions between /|)>>>> and /|)>>>. In order to fill this gap, we introduce the technique of expedito-summation in Section. Roughly speaking, we perform the accelero-summation process until some critical time > with q\p> and then \Pexpedite\Q the process by directly taking a truncated Laplace transform with respect to >. We will show in Section that there exist computable constants ,\,\> such that expedito-summation until the critical time > allows us compute digits of > in time *log n|)>>, uniformly in provided that /|)>>\n\/|)>>>. This paper should be regarded as a supplement to. For this reason, and as we already stressed before, we will freely use concepts and notations from that paper. In this area it also frequently happens that there exist algorithms to explicitly compute various constants involved in error bounds, but that the precise values of these constants are irrelevant. In, we strived to make all error bounds as explicit as possible, but in this paper we will simply denote strictly positive constants of this kind by >. In analysis, the habit to write > for \Psome bounded function\Q is somewhat analoguous. For instance, given a real function and a constant \\>, saying that <\eqnarray*> |\|>>|>|*\*x>>>>> for all \> means that we can compute an explicit exponential bound for > on the interval ,\|)>>. <\acknowledgments*> We wish to like Grégoire for some helpful remarks. Throughout this and the next section, we make the following assumptions: <\itemize> \\>|]>|]>> with \|}>> is a formal solution to =0>. > is accelero-summable with critical times =>,\,z=>> and \\\k>. The holonomic equations satisfied by the Borel counterparts ,\,> at the various critical times admit no singularities on the positive real axis. All acceleration integrals and the final Laplace transforms are performed on the positive real axis. In, we provided a detailed analysis of two summation methods of >. The usual accelero-summation process associates the accelero-sum > to > using <\eqnarray*> >|||\>>\|\>,k>\\\|\>,k>\|\>>|)>|)>.>>>> In the appendix, we also considered \Psummation up to the least term\Q: given \>, one may approximate > by >, where <\equation*> |)>=|~>+\+*z. Taking *|)>1/k>>, we proved that <\eqnarray*> -accsum |)>|\|>>|>|*\*|)>1/k>>,>>>> for all |]>>. Summation up to the least term completely shortcuts the whole accelero-summation process. It provides approximations of a precision that correspond to stopping the accelero-summation process at the first singularity for the first critical time. It is natural to consider more general shortcuts, where we perform the usual accelero-summation process up till agiven critical time > and then \Pexpedite\Q the remainer of the process by directly performing a truncated Laplace transform on \|]>> for a suitable \\>>. More precisely, given ,p-1|}>> and \\>>, we define <\eqnarray*> > |)>|)>>|||\>,\>\|\>,k>\\\|\>,k>\|\>>|)>|)>|)>|)>>>||\>,\> >>|)>|)>>||>>>|)>*\/z>*\ \.>>>> Here >> denotes the contour from > to \0>, turning around and then back from > to >. As for summation to the least term, it is natural to chose > such that |)>*\/z>|\|>> is minimal. Since |)>> satisfies a bound of the form <\eqnarray*> |)>|\|>>|>|*\*\|k-k>>>>>>> at infinity, this means that we should take \\\\>, where <\eqnarray*> >||*|\|>-k|k>>=*|\|>-k|k>>.>>>> Our main aim is to prove the error bound <\eqnarray*> > -accsum |)>|\|>>|>|*\*\/|\|>>+*\/|\|>>,>>>> for |]>>. When taking =\>, this bound further simplifies to <\eqnarray*> > -accsum |)>|\|>>|>|*\/|\|>>.>>>> Let >|)>=>|)>> for \\> and >|)>=0> for \\>, so that <\eqnarray*> \g|)>>|>||\>> >|)>|)>=|\>,\> >|)>|)>.>>>> Since we know how to compute a bound for >|\|>> on the contour >>, we may compute an explicit bound of the form <\eqnarray*> |)>|\|>>|>|*\/|\|>>>>>> for > on a small positive sector near zero. at other critical times>For ,p>, we define <\eqnarray*> |)>>|>||^>,k> >|)>|)>=|^>,k,\> >|)>|)>,>>>> where <\eqnarray*> |^>,k,\> >|)>|)>>||>>>|)>*|^>,k>,\|)>*\ \.>>>> We may also represent > as the analytic Borel transform of |)>=g|)>> with respect to>. Using the bound(), this allows us to compute a bound <\eqnarray*> |)>|\|>>|>|*\*\>>>>> for \,\|)>>. and >Let \g-f>. For ,p>, we also define <\eqnarray*> |^>>|>|->>|>|>|-f.>>>> For , and setting =\>, we thus have <\eqnarray*> |^>|)>>||>>> for \|]>>. One major topic of this section will be to compute bounds at the origin for|^>|)>|\|>> and q>. |^>> at infinity>Let i\p>. Combining the bound() with the superexponential bound for >, as provided by the accelero-summation process, we may compute a bound <\eqnarray*> |^>|)>|\|>>|>|*\*\|k-k>>>>>>> for \,\|)>>. Notice that we may also compute a bound <\eqnarray*> |^>,k>|)>|\|>>|>|*\*|\|k-k>>/\|k-k>>|>>>>>> for \,\|)>> and \|]>>. The following bounds will be useful for proving precise error estimates for the |^>> and >. The proofs are a routine application of the saddle point technique. <\lemma> Let > and > be critical times with i>. Then <\eqnarray*> >\*\|k-k>>>*\*\/|\|>>*\ \|\|>>|>|*\/|\|>>,>>>> for all |\|>\|]>>. If i>, then <\eqnarray*> |>\*\|k-k>>>*|^>,k>,\|)>*\ \|>>|>|*\*\|k-k>>>,>>>> for all \|]>>. <\lemma> Let . We can compute \0> such that, for \|]>>, we have <\eqnarray*> |^>|)>|\|>>|>|*\*\|k-k>>*\|k-k>>>.>>>> <\proof> We have <\equation*> \; <\eqnarray*> |^>|)>>|||^>,k> |^>|)>|)>|)>>>|||>>|^>|)>*|^>,k>,\|)>*\ \.>>>> Using() and(), it follows that <\eqnarray*> |^>|)>|\|>>|>||*>>\*\|k-k>>-*|\|k-k>>/\|k-k>>|>>*\ \|>>>||>|*\*\|k-k>>*\|k-k>>>,>>>> on an interval \|]>> for some computable \0>. <\lemma> For each q+1>, we can compute a constant \0>, together with a bound <\eqnarray*> |^>|)>|\|>>|>|*\*\|k-k>>*\|k-k>>>+*\*\|k-k>>>>>>> for \|]>>. <\proof> We will prove the lemma by induction over . We have <\equation*> \; <\eqnarray*> |^>|)>>|||^>,k> |^>|)>|)>|)>=I|)>+I|)>,>>>> where <\eqnarray*> |)>>|>|>|^>|)>*|^>,k>,\|)>*\ \>>||)>>|>|>>|^>|)>*|^>,k>,\|)>*\ \>>>> If , then Lemma yields a bound <\eqnarray*> |^>|)>|\|>>|>|*\*\|k-k>>*\|k-k>>>,>>>> for \|]>>. For q+2>, the induction hypothesis yields the bound <\eqnarray*> |^>|)>|\|>>|>|*\*\|k-k>>*\|k-k>>>+*\*\|k-k>>>,>>>> for \|]>>. Now, in view of (), we may compute a suffiently small \0> such that <\eqnarray*> |>\*\|k-k>>*\|k-k>>>*|^>,k>,\|)>*\ \|>>|>|*\*\|k-k>>*\|k-k>>>,>>>> for all \|]>>. If q+2>, then a similar computation yields <\eqnarray*> |>\*\|k-k>>>*|^>,k>,\|)>*\ \|>>|>|*\*\|k-k>>>,>>>> for all \|]>>, modulo a decrease of > if necessary. Putting these bounds together, we obtain <\eqnarray*> |)>|\|>>|>|*\*\|k-k>>*\|k-k>>>+*\*\|k-k>>>>>>> for \|]>>. Using() and(), we may also compute a bound <\eqnarray*> |)>|\|>>|>||*>>\*\|k-k>>-*|\|k-k>>/\|k-k>>|>>*\ \|>>>||>|*\*\|k-k>>>>>||>|*\*\|k-k>>>>>>> for \|]>>, modulo a further decrease of > if necessary, and where we used the fact that \k>. Combining the bounds for > and >, the result follows. <\lemma> For any aperture \/2|)>\\>, we can compute a \0> and a bound <\eqnarray*> |)>|\|>>|>|*\*\/|\|>>+*\/|\|>>>>>> for all \\,\>>. <\proof> We have <\eqnarray*> |)>>|||^>> |^>|)>|)>|)>=I|)>+I|)>,>>>> where <\eqnarray*> |)>>|>|>|^>|)>*\/z>*\ \>>||)>>|>|>>|^>|)>*\/z>*\ \.>>>> Using Lemma and(), we can compute \0> and a bound <\eqnarray*> |)>|\|>>|>|>|*\*\|k-k>>*\|k-k>>>+*\*\|k-k>>>|>*/z>|\|>*\ \>>||>|>|*\*\|k-k>>*\|k-k>>>+*\*\|k-k>>>|>*\*\/|\|>>*\ \>>||>|*\*\/|\|>>+*\/|\|>>>>>> for \\,\>>. Using() and the exponential bound for > as provided by the accelero-summation process, we may also compute a bound <\eqnarray*> |^>|)>|\|>>|>|*\*\>>>>> for \|c,\|)>|\>>. Modulo a further increase of > if necessary, this allows us to compute abound <\eqnarray*> |)>|\|>>|>|>>*\*\>*/z>|\|>*\ \>>||>|>>*\*\>*\*\/|\|>>*\ \>>||>|*\/|\|>>>>||>|*\/|\|>>,>>>> for \\,\>>. Adding up the bounds for > and >, the results follows. <\corollary> For any aperture \/2|)>\\>, and assuming that <\equation*> \\\*|\|>-k|k>>, we can compute a \0> and a bound <\eqnarray*> |)>|\|>>|>|*\*\/|\|>>>>>> for all \\,\>>. <\proof> This directly follows from the fact that -k|k>>/z=z>. <\proposition> Let \/2|)>\\> be a fixed aperture and let \\>>. Then we can compute a constant \0> with the following property: given \ \|]>> and size+> with <\equation*> \/n>\\\ and \k*\>, we can compute an approximation \|]>> with |\|>\2> in time *log n|)>>, where the complexity bound holds uniformly in under the above conditions. <\proof> Recall that we may compute an exponential bound <\eqnarray*> |)>|\|>>|>|*\*\>>>>> for > at infinity. For =*n*|\|>> and >, this yields a bound <\eqnarray*> >>|)>|\|>*/\>|\|>*\ \>|>|.>>>> We now wish to compute by approximating the truncated Laplace integral <\eqnarray*> |>|>>>|)>*\/\>*\ \>>>> with precision >, \2> and |\|>\2>. Let us first consider the case when the bitsize of > is bounded by *log n>. Under the assumption that \\/n>>, we observe that \>. This implies that we can chose the contour >> to use a circle of fixed radius around the origin (which does not depend on>). We next evaluate() using the algorithm from6>. Our hypothesis that |)>=O> implies that the primitive of >|)>*\/\>> satisfies a holonomic equation of size >, uniformly in >. Consequently, it can be checked that the complexity bound from holds uniformly in >. This means that the required >approximation of can be computed in time *log n|)>>, uniformly in >. For general , we approximate > in two steps. Let =k> be the growth rate of the linear differential equation satisfied by at the origin. In 5.2>, we showed that in the sector =\,k*\>>, we have the following bound for the transition matrix on a straightline path z> in >: <\eqnarray*> |\z>|\<\|\|\>>>|>|*\*|)>>-z>|\|>>.>>>> For -z\*z+1>>, it follows that <\eqnarray*> |\z>|\<\|\|\>>>|>|.>>>> Now let \\|]>> be an approximation of with -z\*z+1>> and |)>\*|\|>>. By what precedes, we may compute >>-approximations of |)>,\,f>|)>> in time *log n|)>>, uniformly in . Using the usual \Pbitburst\Q algorithm from , together with(), it follows that we may compute a >-approximation of > using an additional time of *log n|)>>, uniformly in . Adding up these complexity bounds, the result follows. <\proposition> Let \/2|)>\\>. Then we may compute a constants \\>> such that <\eqnarray*> |)>-f|\|>>|>|>>>> for all \>, > and *n> with <\equation*> \\/n> and \k*\>. Moreover, if \|]>> and size>, then we can compute an approximation \|]>> with |)>|\|>\2> in time *log n|)>>, where the complexity bound holds uniformly in under the above conditions. <\proof> Direct consequence ofA.1>. <\proposition> Let \/2|)>\\> be a fixed aperture and let \\>>, where p>. Then we may compute a constant \\>> such that <\eqnarray*> > |)>-f|\|>>|>|>>>> for all \> and > with <\equation*> \/n>\\\/n> and \k*\>, where <\eqnarray*> >||*n*|\|>.>>>> Moreover, if \|]>> and size>, then we can compute an approximation \|]>> with > |)>|\|>\2> in time *log n|)>>, where the complexity bound holds uniformly in under the above conditions. <\proof> Our hypothesis on > implies that <\equation*> \\\*|\|>-k|k>>. By Corollary, it follows that for all > with =|z>|>\> and =k*|\|>\k*\>, we have <\equation*> > |)>-f|\|>=|)>|\|>=*\*\/|\|>>\2. For any suitable point > close to the origin and \>, we have shown in how to compute decimal digits of>>|)>> in time *log n|)>>. This provides us with the required initial conditions for the analytic continuation of the integrant of the truncated Laplace integral <\eqnarray*> |>|>>>|)>*\/\>*\ \.>>>> In a similar way as in the proof of Proposition, we may therefore approximate to precision > in time *log n|)>>, where the complexity bound is uniform in under our conditions. Putting Propositions, and together, we obtain: <\theorem> Let \/2|)>\\> be a fixed aperture. Then we may compute a constant \\>> with the following property. Given \|]>>> and \> on input with \k*\> and \\>, we may compute a >-approximation of > in time *log n|)>>, where the complexity bound holds uniformly in . <\proof> Let ,\,\,\> be as in Propositions, and . For any \>> with \k*\> and \\>, at least one of the following three statements holds: <\enumerate> We have /n>\\\>. We have /n>\\\/n>> for some ,p-1|}>>. We have \\/n>>. In these cases we respectively apply Proposition, or in order to obtain the desired result. Assume that is singular at the origin. Then for some \\>, there exists a basis of formal solutions of the form <\equation> =|~>*z>*\>|)>> for , where |~>\\>|]>|]>>, \\>, >|)>\\>|]>>, and where \>> for some \\>. Moreover, each |~>> belongs to the subset > of >|]>|]>> accelero-summable series. For each fixed accelero-summation scheme, there exist >, > and > such that the |~>> and > give rise to analytic functions ,i>> and ,i>> on the sector =\,\,\>>. A sector> for which this happens is said to be . Moreover, there exist afinite number of admissible sectors ,\,\>,\,\>,\>,\>>> with ,\*\>,\*\>\\> whose interiors cover asmall neighbourhood of>>. We will call this an . Let =\,\,\>> be one of the sectors in an admissible cover and let > and > denote the accelero-sums of |~>> and > on this sector. For each ,r|}>>, let =z>*\>|)>>>. Let > denote the subset of all \> such that <\equation*> |\|>\|\|>\\\|\|>. More generally, given a permutation > of ,r|}>>, let >> denote the subset of all \> with <\equation*> >|\|>\>|\|>\\\>|\|>. Clearly, =>\>>. Let *b+\+\*b> be a non zero solution to on > and let be the column vectors with entries ,\,f>>. Although can vanish on > due to cancellations among the terms *b> and *b>, the vector cannot vanish unless . We will now prove a stronger version of this observation by showing that the sup-norm |F|\<\|\|\>>> of cannot become much smaller than |\|>>. <\theorem> There exist constants 0> and > such that <\eqnarray*> |F|\<\|\|\>>>|>|*z>|\|>,>>>> for all \>. <\proof> Without loss of generality, we may assume that \1>. For each ,r|}>>, let> be the Wronskian matrix <\eqnarray*> >||>|>|>>|>||>>|>>|>|>>>>>>>>>> We may decompose <\eqnarray*> >||*\,>>>> where <\equation*> \=>||>||>|>|||>>>>>, and where the entries of > are in *z>> for some \\> that only depends on the degrees of ,\,P>. It follows that <\eqnarray*> >||*|)>|det|)>>,>>>> where |)>\0> by the linear independence of ,\,b>. Now |)>> and the entries of |)>> are all elements of *z>>. It follows that there exists a constant \\> such that |)>/det|)>=O>|)>> for all \>. Now consider our fixed linear combination =\*b+\+\*b> and let <\equation*> \=>>|>>|>>>>>,G=>>|>>|>>>>>>>, where =\*b+\+\*b>, so that > and =W*\>. Also let > be the column vector with entries ,\,E>. For the sup-norm on vectors, the above discussion shows that <\eqnarray*> |\|\<\|\|\>>>||*z>*|G|\<\|\|\>>|)>.>>>> For some fixed constant \0>, this means that <\eqnarray*> |G|\<\|\|\>>>|>|**z>|\|>.>>>> There also exist constants 0> and > such that for all ,r|}>> and r>, <\eqnarray*> *\*E|)>>*E|\|>>|>|>|\|>.>>>> Now we may partition > into subsets ,\,\> as follows. By induction over , we define > to be the subset of all \\\\\\|)>> such that <\equation*> 2*M**z>|\|>\C**z>|\|>, where we understand that =0>. If \>, then it follows that <\eqnarray*> |\|>>|>|/2*M|)>**z-\>|\|>>>||\|>>|>|*C/4*M|)>**z+\-2*\>|\|>>>||>|>||\|>>|>|*\*C/2*M|)>**z+\+\-*\>|\|>>>>> Still for \>, the relation() also implies the existence of an k> such that <\eqnarray*> >|\|>>|>|**z>|\|>.>>>> Using(), it follows that <\eqnarray*> |||)>>|\|>>>||>|*z>|\|>>>||>|**z>|\|>>>||>|>|\|>,>>>> whence <\eqnarray*> >|\|>>|>|*>|\|>>>||>|*C**z>|\|>>>||>|*\*C/2*M|)>**z+\+\-*\>|\|>.>>>> We conclude that |F|\<\|\|\>>\C**z>|\|>> for *\*C/2*M:|1\k\r|\>|}>> and =max +\+\-*\:|1\k\r|\>|}>>, using our assumption that \1>. <\remark> It is plausible that a bound for > can be stated in terms of> and the degrees of ,\,P>. We have not pursued this line of thought any further since any constant > will do for our purposes. Consider the power series expansion =f+f*t+f*t+\> of at . For each \>, let > be the vector with entries ,\,f>. Theorem provides us with auniform lower bound for |\|\<\|\|\>>> in terms of >. We also have the following upper bound for the remaining coefficients. <\lemma> There exist constants \0>, 0> and \\> such that <\eqnarray*> |\|\<\|\|\>>>|>||\|\<\|\|\>>*>|\|>,>>>> for all \ and> \> with \\>. <\proof> Since is holonomic, there exists a matrix > with coefficients in |]>> such that <\eqnarray*> >||*\.>>>> Consequently, there exists a uniform majorant equation for > of the form <\eqnarray*> |\>>||*J*|\>*>|\|>,>>>> for suitable constants 0> and \\>, and where denotes the r> matrix whose coefficients are all one. Taking |\>> to be the vector with entries |\|\<\|\|\>>,\,|\|\<\|\|\>>>, it follows that |\>> is the vector with entries |\|\<\|\|\>>*>|\|>,\,|\|\<\|\|\>>*>|\|>>. By construction|\|\<\|\|\>>\||\>|\<\|\|\>>>>. <\lemma> Let +g*t+\> be an analytic function on the unit disk > such that |\|>\>, |\|>,\,|\|>|)>=1> and *t+g*t+\|\|>\> on >. Then admits a root on >. <\proof> Let =g*t+\+g*t>. We may factor =|)>*\*|)>> with =0>. Let \\1> be such that -|\|>|\|>\\> for all . Then we have |\|>\> for all \> with =\>, whence -G|\|>\2*\\|\|>>. By Rouché's theorem, it follows that and admit the same number of zeros in >. Hence admits at least one zero inside \\>. <\lemma> There exist positive constants >, and > such that <\eqnarray*> |\|>\C**z>*2|\|>>|>|z\\,-z|\|>\2\f|)>=0>>>> for all |r*log |\>> and \> with \\\>. <\proof> Let and > be as in Theorem and >, and > as in Lemma. Take =min,\|)>>>. We thus have |\|\<\|\|\>>\C**z>|\|>> and |\|>\|\|\<\|\|\>>*>|\|>> for all. Let =f*t|)>=g+g*t+\>. Then it follows that |\|>,\,|\|>|)>>\|\|\<\|\|\>>*2*n>> and |\|>\|\|\<\|\|\>>*>|\|>*2\M*>|\|>*2> for r>. Assuming that |\|>\C**z>*2|\|>>, we also obtain |\|>\|\|\<\|\|\>>*2\M*2\M*>. Decreasing > if necessary, we may arrange ourselves so that >|\|>\>>. Consequently, =g*t+g*t+\> satisfies |\|>\M*2\M*> for \1>. We now conclude by Lemma. We are now in a position to prove our main theorem. We start with proving the uniform bound on \Psuper-admissible\Q sectors near singularities. Here the sector =\,\,\>> is said to be if we may take =\> in Lemma, as well as in the analoguous statement on >> for each permutation > of ,r|}>>. Given \0> and \\> with -z|\|>\\>, we will say that > is an >-approximation> of . <\lemma> Assume that is a singularity for and that is a solution to on asuper-admissible sector =\,\,\>>, with holonomic initial conditions at apoint in \\>. Denote =\:f=0|}>>. Then there exists an algorithm that takes \> and \\\|]>> with |)>>\ \\\|)>=\> and \n> on input and that computes \|]>> on output with -v|\|>\2*|\|>>. Moreover, the running time of the algorithm is bounded by *log n|)>>, uniformly in . <\proof> Let > and > denote the accelero-sums of |~>> and > on >. By Theorem, we may compute >-approximations of the evaluations > in time *log n|)>>, uniformly for \\\|]>>. In particular, the constants ,\,\> with *b+\+\*b> can be evaluated with aprecision of bits in time *log n|)>>. For a given \\\|]>>, we first determine a permutation > such that \>>. Modulo apermutation of the basis elements >, we may assume without loss of generality that =Id>. In order to evaluate at , we perform tentative evaluations at increasing bit precisions =n,2*n,4*n,\> until the desired approximation with arelative precision of bits is found. For the tentative evaluations, we proceed as follows: <\itemize> We compute -1>>-approximations of ,\,\>. We compute >>-approximations of *E/E,\,\*E/E>. Summing up, we obtain a >>-approximation of /E>. If the >>-approximation of /E> has a relative precision of at least bits, then we obtain using one final multiplication with a floating point approximation of>. If /E> has a smaller relative precision, then we set \2*n> and keep iterating. Now whenever both \r*n-|\*log +log C|\>> and /E|\|>\2>>, Lemma implies that |)>>\\\\>. In other words, the iteration will stop whenever \r*n-|\*log +log C|\>+log r>. Since \2>, this happens for =O>. Since we double > at every iteration, the total running time is dominated by the running time of the last tentative evaluation at precision =O>. The most expensive step of this tentative evaluation is the computation of the >>-approximations of ,\,\>. By Theorem, this can be done in time|)>*log n|)>=O*log n|)>>, uniformly in . <\render-proof|Proof of Theorem> Let \\> be one of the singularities and let \\\\>> be an admissible ball cover in the neighbourhood of >. For each admissible sector > and each connected component > of \\> (there are at most two such connected components), we also arbitrarily pick a point >> in \\|]>>. We may compute >-approximations for >|)>,\,f>>|)>> in time *log n|)>>. These values may be used as initial conditions for on >. For \\\|]>> sufficiently close to >, we use the following algorithm for the evaluation of >. Among the sectors > that contain, we pick the one for which \|)>> is maximal. In particular, \|)>\\*|\|>> for some fixed constant \0>. Let> be the connected component of of \\> that contains . We now evaluate > using the algorithm from Lemma, by using the initial conditions for at >>. Applying Lemma on each of the sectors >, we obtain a constant >> such that > can be approximated with a relative precision of bits in time *log n|)>>, uniformly in \\\|]>\\,r>|)>>, provided that |)>>\ \\\|)>=\>. Considering the change of variables 1/z>, one may prove in a similar way that, for some sufficiently large , we can approximate > with a relative precision of bits in time *log n|)>>, uniformly in \\\|]>\\:\R|}>>, provided that |)>>\ \\\|)>=\>. Let \:\R\\\\,|\|>\r>|)>|}>>. The complement \U> is a compact set that contains none of the singularities of . Using the complexity bounds from, it follows that a >-approximation for > can be computed in time *log n|)>>, uniformly in \U|)>\\\\|]>>. Now > admits only a finite number of zeros on \U> and each zero has multiplicity at most . Considering the local power series expansions around any of these zeros >, we observe that |\|>\c*|\|>> for some computable contant 0> and sufficiently close to >. Provided that |)>\ \\\|)>=\>, this implies that we can also compute an approximation for > with a relative precision of bits in time *log n|)>>, uniformly for \U|)>\\\\|]>>. There are several directions in which the results of this paper can be extended or made more precise. In our main Theorem, we assumed that > is the field of algebraic numbers. Following the Chudnovsky's, and using the baby-step-giant-step technique, one may replace > with more general effective subfield of > whose elements can be approximated fast. More precisely, if for any constants in > we can compute a>approximation of in time |)>*log n|)>>, then Theorem still holds, but one should replace the uniform complexity bound *log n|)>> by |)>*log n|)>>. In this paper, we used > for the domain of our holonomic function. Of course, is really defined on the covering space of \\> which is a Riemann surface. Points on this Riemann surface can be represented by broken line paths as in. By using a suitable size function for broken line paths with vertices in |]>>, one may extend Theorem to the evaluation of at points above |]>> on this Riemann surface. Given a sufficiently good approximation \\|]>> of azero of of multiplicity > (we must have \r>), we may use Newton method's \-\*f|)>/f|)>> to compute a better approximation >. Since the evaluations of and > can be done with good uniform complexity, this should make it possible to compute a >-approximation of in time *log n|)>>, uniformly in > under suitable conditions. It would be a useful contribution to prove a more precise statement of this kind. In this paper, we assumed that the points where we evaluate are exactly known. An interesting question concerns the efficient computation of high quality ball lifts> of . In that case, the evaluation point is replaced by an explicit ball =\|)>>> with \|]>> and \\>>, and the evaluation |)>> should be a similar ball =\|)>> with the property that |)>\\> and |)>> contains two points with distance at least >. It would be worthwhile to extend Theorem to this kind of arithmetic. When introducing the theory of accelero-summability, Écalle also described a variant which only relies on the evaluation of iterated Laplace integrals (instead of the more general accelerations). This idea was further developed by Balser who rebaptized it under the term \Pmulti-summation\Q. It is quite plausible that and the present paper can be adapted to this setting. <\bibliography|bib|plain|> <\bib-list|10> W.Balser. , volume 1582 of Springer-Verlag, Berlin, 1994. R.P. Brent. The complexity of multiprecision arithmetic. In , 1976. D.V. Chudnovsky and G.V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, CA, 1986). In , volume 125, pages 109\U232, New-York, 1990. Dekker. J.Écalle. L'accélération des fonctions résurgentes (survol). Unpublished manuscript, 1987. J.Écalle. . Hermann, collection: Actualités mathématiques, 1992. B.Haible and T.Papanikolaou. Fast multiple-precision evaluation of elementary functions. Technical Report TI-7/97, Universität Darmstadt, 1997. J.vander Hoeven. Fast evaluation of holonomic functions. , 210:199\U215, 1999. J.vander Hoeven. Fast evaluation of holonomic functions near and in singularities. , 31:717\U743, 2001. J.vander Hoeven. Efficient accelero-summation of holonomic functions. , 42(4):389\U428, 2007. E.A. Karatsuba. Fast evaluation of Bessel functions. , 1(4):269\U276, 1993. Marc Mezzarobba. . PhD thesis, École polytechnique, 2011. H.Poincaré. Sur les intégrales irrégulières des équations linéaires. , 8:295\U344, 1886. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+U2YV1EuEKZY7La|inproceedings|CC90> <|db-entry> G. V. > <\db-entry|+Y7Wf699OJGUOd2|article|vdH:hol> <|db-entry> > <\db-entry|+U2YV1EuEKZY7LN|inproceedings|Br76a> <|db-entry> > <\db-entry|+U2YV1EuEKZY7MT|article|Kar93> <|db-entry> > <\db-entry|+dG1O0ihIeNj9Ug|techreport|HP97> <|db-entry> T. > <\db-entry|+Y7Wf699OJGUOd7|article|vdH:singhol> <|db-entry> > <\db-entry|+Y7Wf699OJGUOdh|article|vdH:reshol> <|db-entry> > <\db-entry|+dG1O0ihIeNj9X5|phdthesis|Mezza:phd> <|db-entry> > <\db-entry|+dG1O0ihIeNj9Yd|article|Poin1886> <|db-entry> > <\db-entry|+dG1O0ihIeNj9SS|unpublished|Ec87> <|db-entry> > <\db-entry|+M2XvD2msK5aQZQ|book|Ec92> <|db-entry> > <\db-entry|+dG1O0ihIeNj9PK|book|Bal94> <|db-entry> > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> CC90 vdH:hol Br76a Kar93 HP97 vdH:singhol vdH:reshol vdH:singhol vdH:reshol CC90 vdH:hol Mezza:phd vdH:hol vdH:singhol vdH:reshol vdH:reshol vdH:reshol vdH:reshol vdH:reshol Poin1886 vdH:reshol vdH:reshol vdH:reshol vdH:reshol vdH:reshol vdH:reshol CC90 vdH:hol Mezza:phd vdH:reshol vdH:reshol vdH:hol CC90 vdH:hol vdH:singhol vdH:reshol Ec87 Ec92 Bal94 vdH:reshol <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |Statement of the problem and the main result |.>>>>|> > |Proof strategy |.>>>>|> > |Notational conventions |.>>>>|> > |math-font-series||font-shape||2.Expedito-summation> |.>>>>|> |2.1.Introduction to expedito-summation |.>>>>|> > |2.2.The expedited approximation |.>>>>|> > |The truncated Laplace transform |.>>>>|> > |Borel transforms of |g> at other critical times |.>>>>|> > |The difference between |f> and |g> |.>>>>|> > |Behaviour of the ||^>> at infinity |.>>>>|> > |Majorants for specific accelerates and Laplace transforms |.>>>>|> > |2.3.The first acceleration |.>>>>|> > |2.4.Subsequent accelerations |.>>>>|> > |2.5.The final Laplace transform |.>>>>|> > |math-font-series||font-shape||3.Uniform complexity on local sectors> |.>>>>|> |3.1.Uniform complexity of accelero-summation |.>>>>|> > |3.2.Uniform complexity of summation until the least term |.>>>>|> > |3.3.Uniform complexity of expedito-summation |.>>>>|> > |3.4.The combined local strategy |.>>>>|> > |math-font-series||font-shape||4.Globally efficient evaluation> |.>>>>|> |4.1.Local analysis of cancellations |.>>>>|> > |4.2.Existence of zeros on disks |.>>>>|> > |4.3.Global uniform complexity bounds |.>>>>|> > |math-font-series||font-shape||5.Further thoughts and challenges> |.>>>>|> |More general constants |.>>>>|> > |Riemann surfaces |.>>>>|> > |Fast approximation of zeros |.>>>>|> > |Ball evaluations |.>>>>|> > |Multi-summation |.>>>>|> > |math-font-series||font-shape||Bibliography> |.>>>>|>