> <\body> of differential Galois groups>|||<\author-affiliation> de Mathématiques ( 425) Université Paris-Sud 91405 Orsay Cedex France |>>|>> <\abstract> Let \|]>> be a linear differential operator, where > is an effective algebraically closed subfield of>. It can be shown that the differential Galois group of is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in local exponential groups. Moreover, there exist fast algorithms for the approximation of the entries of these matrices. In this paper, we present a numeric-symbolic algorithm for the computation of the closed algebraic subgroup generated by a finite number of invertible matrices. Using the above results, this yields an algorithm for the computation of differential Galois groups, when computing with a sufficient precision. Even though there is no straightforward way to find a \Psufficient precision\Q for guaranteeing the correctness of the end-result, it is often possible to check whether the end-result is correct. In particular, we present a non-heuristic algorithm for the factorization of linear differential operators. >>>>>>>>>>>>>> Let \|]>> be a monic linear differential operator of order , where > is an effective algebraically closed subfield of >. A holonomic function is a solution to the equation. The differential Galois group > of is a linear algebraic group which acts on the space of solutions (see section and ). It carries a lot of information about the solutions in and on the relations between different solutions. For instance, the existence of non-trivial factorizations of and the existence of Liouvillian solutions can be read off from the Galois group. This makes it an interesting problem to explicitly compute the Galois group of . A classical approach in this area is to let > act on other vector spaces obtained from by the constructions from linear algebra, such as symmetric powers H>> and exterior powers H>> . For a suitable such space , the Galois group > consists precisely of those invertible n> matrices which leave a certain one-dimensional subspace of invariant . Invariants in H>> or H>> under > may be computed more efficiently by considering the local solutions of at singularities . More recently, and assuming (for instance) that the coefficients of are actually in >, alternative algorithms appeared which are based on the reduction of the equation modulo a prime number . In this paper, we will study another type of \Panalytic modular\Q algorithms, by studying the operator in greater detail near its singularities using the theory of accelero-summation. More precisely, we will use the following facts: <\itemize> The differential Galois group of is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in so called local exponential groups (see and theorem below). There exists an algorithm \ for the approximation of the entries of the above matrices (see and theorem below). If =\> is the algebraic closure of >, then -digit approximations can be computed in time d*log log d|)>>. When using these facts for the computation of differential Galois groups, the bulk of the computations is reduced to linear algebra in dimension with multiple precision coefficients. In comparison with previous methods, this approach is expected to be much faster than algorithms which rely on the use of exterior powers. A detailed comparison with arithmetic modular methods would be interesting. One advantage of arithmetic methods is that they are easier to implement in existing systems. On the other hand, our analytic approach relies on linear algebra in dimension (with floating coefficients), whereas modulo methods rely on linear algebra in dimension (with coefficients modulo ), so the first approach might be a bit faster. Another advantage of the analytic approach is that it is more easily adapted to coefficients fields > with transcendental constants. Let us outline the structure of this paper. In section , we start by recalling some standard terminology and we shortly review the theorems on which our algorithms rely. We start with a survey of differential Galois theory, monodromy and local exponential groups. We next recall some basic definitions and theorems from the theory of accelero-summation and the link with Stokes matrices and differential Galois groups. We finally recall some theorems about the effective approximation of the transcendental numbers involved in the whole process. Before coming to the computation of differential Galois groups, we first consider the simpler problem of factoring in section . We recall that there exists a non-trivial factorization of if and only if the Galois group of admits a non-trivial invariant subspace. By using computations with limited precision, we show how to use this criterion in order to compute candidate factorizations or a proof that there exist no factorizations. It is easy to check whether a candidate factorization is correct, so we obtain a factorization algorithm by increasing the precision until we obtain a correct candidate or a proof that there are no factorizations. In section we consider the problem of computing the differential Galois group of . Using the results from section , it suffices to show how to compute the algebraic closure of a matrix group > generated by a finite number of given elements. A theoretical solution for this problem based on Gröbner basis techniques has been given in . The main idea behind the present algorithm is similar, but more emphasis is put on efficiency (in contrast to generality). First of all, in our context of complex numbers with arbitrary precisions, we may use the LLL-algorithm for the computation of linear and multiplicative dependencies . Secondly, the connected component of > is represented as the exponential of a Lie algebra > given by a basis. Computations with such Lie algebras essentially boil down to linear algebra. Finally, we use classical techniques for finite groups in order to represent and compute with the elements in /\>> . Moreover, we will present an algorithm for non-commutative lattice reduction, similar to the LLL-algorithm, for the efficient computation with elements in /\>> near the identity. The algorithms in section are all done using a fixed precision. Although we do prove that we really compute the Galois group when using a sufficiently large precision, it is not clear how to find such a \Psufficient precision\Q. Nevertheless, we have already seen in section that it is often possible to check the correctness of the result posteriori>, especially when we are not interested in the Galois group > itself, but only in some information provided by >. Also, it might be possible to reduce the amount of dependence on \Ptranscendental arguments\Q in the algorithm modulo a further development of our ideas. Some hints are given in the last section. <\remark> The author first suggested the main approach behind this paper during his visit at the MSRI in 1998. The outline of the algorithm in section came up in a discussion with Harm Derksen (see also ). The little interest manifested by specialists in effective differential Galois theory for this approach is probably due to the fact that current computer algebra systems have very poor support for analytic computations. We hope that the present article will convince people to put more effort in the implementation of such algorithms. We started such an effort , but any help would be appreciated. Currently, none of the algorithms presented in this paper has been implemented. In this section, we recall several classical results about differential Galois theory and its link with accelero-summation theory. We also recall previous work on the efficient evaluation of holonomic constants. The main result of this section is theorem. Throughout this paper, we will use the following notations: <\with|item-strong|>> <\description> \\>>An algebraically closed field of constants. |)>>>The algebra of n> matrices with coefficients in >. |)>>>The subgroup of |)>> of invertible matrices. >>The vector space generated by a subset of a larger vector space. >>The algebra generated by a subset of a larger algebra. Vectors are typeset in bold face =,\,v|)>> and we use the following vector notations: <\eqnarray*> \\>||*w+\+v*w>>|>>||>*\*v>>>>> Matrices |)>> will also be used as mappings \\;\\M*\>. When making a base change in >, we understand that we perform the corresponding transformations P*M*P1>> on all matrices under consideration. We denote ,\,X|)>> for the diagonal matrix with entries ,\,X>. The > may either be scalars or square matrices. Given a matrix |)>> and a vector \\>, we write > for the vector > with =v>*\*v>> for all . Consider a monic linear differential operator +L*\+\+L\\|]>>, where > is an algebraically closed subfield of > and =\>. We will denote by =\\\\|}>> the finite set of singularities of (in the case of >, one considers the transformation z1>>). A of > is a differential field \\> such that <\description> =\|h,\,h|\>> is differentially generated by > and a basis of solutions =,\,h|)>\\> to the equation . > has > as its field of constants. A Picard-Vessiot extension always exists: given a point \\\\> and ,n|}>>, let> be the unique solution to with >|)>=\> for ,n-1|}>>. We call =\>=,\,h|)>> the for the solution space of at >, and regard> as a column vector. Taking =\|h,\,h|\>>, the condition is trivially satisfied since +\|)>\\|]>|]>\\|)>|)>> and the constant field of |)>> is>. Let > be a Picard-Vessiot extension of > and let \\> be as in . The /\>> of the extension /\> is the group of differential automorphisms which leave > pointwise invariant. It is classical that /\>> is independent (up to isomorphism) of the particular choice of the Picard-Vessiot extension >. Given an automorphism \\/\>>, any solution to is sent to another solution. In particular, there exists a unique matrix ,\>\|)>> with h=M h\M*h> for all . This yields an embedding >> of /\>> into |)>> and we define >\\>/\>|)>>. Conversely, |)>> belongs to >> if every differential relation ,\,h|)>=0> satisfied by ,\,h> is also satisfied by ,\,M h> (with \,\,F|}>>). Since this assumption constitutes an infinite number of algebraic conditions on the coefficients of , it follows that >> is a Zariski closed algebraic matrix group. Whenever =P*\> is another basis, we obtain the same matrix group >=P*\>*P1>> up to conjugation. Assume now that |^>\\> is a larger algebraically closed subfield of >. Then the field |^>=|^>|h,\,h|\>=\\|^>> is again a Picard-Vessiot extension of |^>>. Furthermore, the Ritt-Raudenbush theorem implies that the perfect differential ideal of all \,\,F|}>> with ,\,h|)>=0> is finitely generated, say by ,\,G>. But then ,\,G> is still a finite system of generators of the perfect differential ideal of all |^>,\,F|}>> with ,\,h|)>=0>. Consequently, |^>>\|^>|)>> ( as an algebraic group over |^>>) is determined by the same algebraic equations as >>. We conclude that >=|^>>\|)>>. Let > be a Picard-Vessiot extension of >. Any differential field > with \\\\> naturally induces an algebraic subgroup \\/\>> of automorphisms of > which leave > fixed. Inversely, any algebraic subgroup > of /\>> gives rise to the differential field > with \\\\> of all elements which are invariant under the action of >. We say that> ( >) is if =\> ( =\>). In that case, the extension /\> is said to be , every element in \\> is moved by an automorphism of > over>. The main theorem from differential Galois theory states that the Galois correspondences are bijective. <\theorem> With the above notations: <\enumerate-alpha> The correspondences \\> and \\> are bijective. The group > is a closed normal subgroup of /\>> if and only if the extension /\> is normal. In that case, /\>/\\\/\>>. <\corollary> Let \|h,\,h|\>>. If for all \>>, then \>. Consider a continuous path > on \|}>\\> from \\> to \\>. Then analytic continuation of the canonical basis >> at > along > yields a basis of solutions to at >. The matrix >\|)>> with <\equation> \>=\>*\> is called the or along >. In particular, if =z>, then we call >> a based in >. We clearly have <\equation*> \\\>=\>*\> for the composition of paths, so the monodromy matrices based in > form a group >> which is called the . Given a path > from > to >, we notice that >=\>*>*\>1>>. Since any differential relation satisfied by >> is again satisfied by its analytic continuation along >, we have >\\>>> and >>=\>*\>>*\>1>>. <\remark> The definition of transition matrices can be slightly changed depending on the purpose : when interpreting >> and >> as row vectors, then() has to be transposed. The roles of >> and >> may also be interchanged modulo inversion of>>. Now assume that admits a singularity at (if \\> then we may reduce to this case modulo a translation; singularities at infinity may be brought back to zero using the transformation z1>>). It is well-known that admits a computable formal basis of solutions of the form <\equation> f=|)>+\+f|)>*log z|)>*z>*\|)>>, with ,\,h\\|]>>, \>>, \\> and \>. We will denote by > the set of finite sums of expressions of the form (). We may see > as a differential subring of aformal differential field of \Pcomplex transseries\Q > with constant field >. We recall that transseries in > are infinite linear combinations \\>f>*\> of \Ptransmonomials\Q with \Pgrid-based support\Q. The set > of transmonomials forms a totally ordered vector space for exponentiation by reals and the asymptotic ordering >>. In particular, each non-zero transseries admits a unique dominant monomial >. It can be shown that there exists a unique basis =,\,h|)>> of solutions to of the form (), with \\\h> and |)>|)>>=\> for all ,n|}>>. We call =\> the canonical basis of solutions in and there is an algorithm which computes > as a function of . Let > be the subset of > of all finite sums of expressions of the form () with . Then any \> can uniquely be written as a finite sum \\>f>*\>, where =exp\|]>|)>>. Let > be the group of all automorphisms :\\\> for which there exists a mapping :\\\>;\\\>> with =\\>\>*f>*\> for all \>. Then every \\> preserves differentiation and maps the Picard-Vessiot extension =\|h,\,h|\>> of > into itself. In particular, the restriction >> of > to> is a subset of >>. <\proposition> Assume that \> is fixed under >. Then \>. <\proof> Assume that \> and let \\> be a \Pgeneralized exponent\Q with >\0>. Let > be a supplement of the >-vector space >. Let :\\\> be the mapping in > which sends >*\> to >*\>*\> for each \\> and \exp \>. Then we clearly have \f>. Let ,\,\> be the set of generalized exponents corresponding to the generalized exponents of the elements of the canonical basis >. Using linear algebra, we may compute a multiplicatively independent set ,\,\\\>*\*\>> such that =\>*\*\>> for certain \\> and all . <\proposition> With the above notations, the algebraic group >> is generated by the matrices >,\,\>|)>> where \\>\:\n,\=1|}>> is chosen arbitrarily. <\proof> Let > be the group generated by the matrices >,\,\>|)>>. Notice that each individual matrix >,\,\>|)>> generates =>,\,\>|)>:\\\>|}>>: assuming \1>, the variety > is irreducible of dimension and >,\,\>|)>> is not contained in an algebraic group of dimension . Now any \>> is a diagonal matrix >,\,\>|)>> for some multiplicative mapping :\\\>>. Hence <\equation*> Diag>,\,\>|)>=Diag>>,\,\>>|)>*\*Diag>>,\,\>>|)>\\. Conversely, each element <\equation*> \\Diag>,\,\>|)>*\*Diag>,\,\>|)>\\ determines a multiplicative mapping :\>*\*\>\\>;f>*\*f>\\>*\*\>> which may be further extended to> using Zorn's lemma and the fact that > is algebraically closed. It follows that\>>. Assume that *\\\> and let :\\\> be the transformation which sends to *\>, >> to *\*\>*z>> and |)>>> to |)>|)>>>. Then> preserves differentiation, so any solution to of the form () is sent to another solution of the same form. In particular, there exists a matrix 0>> with \=\0>*\>, called the around. We have 0>\\>>. <\proposition> Assume that \> is fixed under > and >. Then \|)>>. <\proof> We already know that \>. Interpreting *log z+\+c> as a polynomial in with 0\c\0>, we must have since <\equation*> M-f=2*\*\*k*c*log z+\=0. Consequently, is of the form \\>f>*z>> and <\equation*> M=\\>\*\*\>*f>*z>=\\>f>*z>=f, We conclude that *\*\>=1> for every \\> with >\0>, whence \|)>>. Let >>|]>|]>> be the differential >-algebra of infinitesimal Puiseux series in for =z*\> and consider a formal power series solution \\=\>>|]>|]>> to =0>. The process of accelero-summation enables to associate an analytic meaning to > in a sector near the origin of the Riemann surface |\>> of , even in the case when > is divergent. Schematically speaking, we obtain through a succession of transformations: <\equation> |||||||>||||||||>||~>>>\>||||||||>>>>>|>|\z>>>>|>|>|>|>|>|\z>>>>|>>>>> Each > is a \Presurgent function\Q which realizes |)>=> in the \Pconvolution model\Q with respect to the -th \Pcritical time\Q =>> (with \\>> and \\\k>). In our case, > is an analytic function which admits only a finite number of singularities above>. In general, the singularities of a resurgent function are usually located on a finitely generated grid. Let us describe the transformations |~>>, >\z>> and>>> in more detail. >We start by applying the to the series |)>==,r>,r>*z>*log z\\>>|]>|]>|]>>. This transformation sends each >*log z> to <\equation*> |~>> z>*log z|)>|)>=\-1>\>|)>*log \, where |)>=1/\|)>>, and extends by strong linearity: <\equation*> |)>=|~>> |)>|)>=\\>>>|\>>>>>>>*|~>> z>*log z|)>|)>, The result is a formal series \\1>*\>>|]>|]>|]>> in > which converges near the origin of |\>>. The formal Borel transform is a morphism of differential algebras which sends multiplication to the convolution product, |~>>=|~>> f|)>\|~>> g|)>>. >Given p>, the function > is defined near the origin of |\>>, can be analytically continued on the axis *\>*\>\|\>>, and admits a growth of the form |)>=exp O|\|>/-k|)>>|)>> at infinity. The next function > is obtained from > by an of the form <\equation*> |)>=\z>> |)>|)>=\\*\>*\>>K,k>,\|)>*|)>*\ \, where the acceleration kernel ,k>> is given by <\eqnarray*> ,k>,\|)>>||>>*K/k>|\/k>>>|)>>>|>|)>>||*\>*\>*\>\*z>>\ z.>>>> For large > on an axis with |\|>\|)>*\/2>, it can be shown that >|)>\expC*|\|>|)>>|)>> for some constant 0>. Assuming that > satisfies <\equation> *\-k*\|\|>\-k|)>*\/2, it follows that the acceleration> of > is well-defined for small > on >*\>>. The set \\> of directions> such > admits a singularity on *\>*\>> is called the set of . Accelerations are morphisms of differential >-algebras which preserve the convolution product. > The last function > is defined near the origin of |\>>, can be analytically continued on the axis *\>*\>\|\>> and admits at most exponential growth at infinity. The function is now obtained using the analytic <\equation*> f=f|)>=>> |)>|)>=\\*\>*\>>|)>*\\/z>*\ \. On an axis with <\equation> -\|\|>\\/2, the function > is defined for all sufficiently small >. The set > of Stokes directions is defined in a similar way as in the case of accelerations. The Laplace transform is amorphism of differential >-algebras which is inverse to the Borel transform and sends the convolution product to multiplication. <\remark> Intuitively speaking, one has \z>>=\>\\>>>. Given critical times \\\k> in >> and directions ,\,\> satisfying (), we say that a formal power series \|~>> is in the multi-direction =,\,\|)>> if the above scheme yields an analytic function > near the origin of any axis on |\>> satisfying(). We denote the set of such power series by ,\>>, where =,\,k|)>>. Inversely, given \\>, we denote by > the set of all triples =,\,z|)>> such that \\,\>> and so that > is well-defined. In that case, we write ,\>> and =|)>>. The set ,\>> forms a differential subring of > and the map \f> for \\,\>> is injective. If > and > are obtained from > and > by inserting a new critical time and an arbitrary direction, then we have ,\>\\,\>>. In particular, ,\>> contains =\>>|}>|}>>, where >>|}>|}>> denotes the ring of convergent infinitesimal Puiseux series. Let =\\\\\,\,\=\\\\\> be sets of directions such that each> is finite modulo>. Let > be the subset of \\\\> of multi-directions > which verify(). We denote ,\>=\\>\,\>>, >=>\,\>> and=>\>>. Taking =\>, the notion of accelero-summation extends to formal expressions of the form () and more general elements of > as follows. Given \\,\>>, \\>, =\|)>>\\> and =,\,z|)>\dom >, we simply define *z>*\|)>|)>=|)>*z>*\|)>>>. It can be checked that this definition is coherent when replacing *z>> by *|)>*z-k>> for some \>. \ By linearity, we thus obtain a natural differential subalgebra ,\>\\> of accelero-summable transseries with critical times > and in the multi-direction >. We also have natural analogues >> and > of >> and >. The main result we need from the theory of accelero-summation is the following theorem . <\theorem> Let \\> be a formal solution to =0>. Then \\>. <\corollary> Let \\> be the canonical basis of formal solutions to =0> at the origin. We have \\>. <\proof> Holonomy is preserved under multiplication with elements of >*\>. <\remark> We have aimed to keep our survey of the accelero-summation process as brief as possible. It is more elegant to develop this theory using resurgent functions and resurgence monomials. We say that \\,\>> is is for all ,\\\>, there exists a \\,\>> with ,\> =sum,\> >, and if the same property is recursively satisfied by >. We denote by |\>,\>> the differential subring of ,\>> which is stable under Stokes morphisms. The mappings ,\,\>:\sum,\>1> sum,\> > will be called and we denote by ,\>> the group of all such maps. <\proposition> Assume that \\,\>> is fixed under ,\>>. Then > is convergent. <\proof> Assume that one of the > admits a singularity at =\*\*\>\0> and choose maximal and > minimal. Modulo the removal of unnecessary critical times, we may assume without loss of generality that. Let > with =\> be a multi-direction satisfying (), such that \\> for all p>. Then <\eqnarray*> >>||,\,\,\-\|)>\\>>|>>||,\,\,\+\|)>\\>>>> for all sufficiently small \0>. Now =\>+\> -\>-\> > is obtained by integration around > along the axis *\>*\>>. By classical properties of the Laplace integral I.2>, the function > cannot vanish, since > admits a singularity in > (if the Laplace integrals corresponding to both directions \\> coincide, then the Laplace transform can be analytically continued to a larger sector, which is only possible if > is analytic in a sector which contains both directions \\>). We conclude that =g|)>=,\>>-sum,\>>|)>|)>\0>, so is not fixed under ,\>>. <\remark> Let > be a set of multi-directions > satisfying (), with \\> for exactly one, and so that for all i>, we have either =k*\/k> or *\/k\\> and =k*\\|)>/k> for some small \0>. For every \\>, we have <\eqnarray*> >>||,\,\,\-\,\,\,\|)>\\>>|>>||,\,\,\+\,\,\,\|)>\\.>>>> By looking more carefully at the proof of proposition , we observe that it suffices to assume that > is fixed under all Stokes morphisms of the form ,\>,\>>>, instead of all elements in ,\>>. We say that ,\\\> are equivalent, if -\\2*\*\*q> for all , where > is the denominator of >. We notice that > is finite modulo this equivalent relation. We denote by > a subset of > with one element in each equivalence class. Let us now come back to our differential equation . Given =,\,z|)>\dom \\dom h\\\dom h>, the map ,\>> induces an isomorphism between |)>> and |)>>. We denote by >\|)>> the unique matrix with =\>*sum,\> \>. Given a second =,\,z|)>\dom \>, the vector ,\>1> sum,\> \> is again in ,\>>, whence \|\>,\>> by repeating the argument. In particular, the Stokes morphism ,\,\>> induces the ,\\\|)>>=\>1>*\>>. We are now in the position that we can construct a finite set > of generators for the Galois group >>> in a regular point \\\\|}>\\>. <\named-algorithm-old|Compute_generators> <\math> |)>> an operator \|]>>> and a regular point \\\\|}>\\> a set > of generators for >>> <\algorithm-body> \\> \\> <\with|item*|>>>> <\itemize> Reduce to the case when =0> modulo a suitable transformation of the form z+c> orz1>>. Let > be an arbitrary path ,\,u|)>\dom \>> from > to a point > nearby >, composed with an arbitrary path from > to > on \\|}>\\>. Compute a finite set of generators > for ,\>>> using proposition and add >*\*\>1>> to > for all \\>. Add >*\z>*\>1>*> to >. For each \\> with > as in remark , add >*\,\,\>\\>|)>>*\>1>> to >. > <\theorem> With > constructed as above, the differential Galois group >>> is generated by > as a closed algebraic subgroup of |)>>. <\proof> Assume that \|h>,\,h>|\>> is fixed by each element of >. We have to prove that \>. Given a singularity >, let > be the \Pcontinuation\Q of along 1>> (which involves analytic continuation until > followed by \Pdecelero-unsummation\Q). By proposition , we have \\|)>>. From proposition and remark , we next deduce that > is convergent. Indeed, since \\|)>>, its realization > in the convolution model with critical time =z>=z/p>> is a function in |q>>. Consequently, ,\>,\>>=\,\>,\>>> whenever > and > are equivalent. At this point we have shown that is meromorphic at >. But a function which is meromorphic at all points of the Riemann sphere \\|}>> is actually a rational function. It follows that \>. <\remark> Theorem is essentially due to Ramis . Our presentation is a more constructive version of the one from . Notice that both proofs by Ramis crucially build upon Écalle's theory of resurgent functions and accelero-summability. In the Fuchsian case, in absence of divergence, the result is due to Schlesinger . <\remark> We have tried to keep our exposition as short as possible by considering only \Pdirectional Stokes-morphisms\Q. In fact, Écalle's theory of resurgent functions gives a more fine-grained control over what happens in the convolution model by considering the |\>>> for \|\>>. Modulo the identification of functions in the formal model, the convolution models and the geometric model via accelero-summation, the pointed alien derivatives commute with the usual derivation >. Consequently, if is a solution to , then we also have |\>> f=0>. In particular, given the canonical basis of solutions > to , there exists a unique matrix >> with <\equation*> |\>> \=B>*\. This equation is called the . Since > admits only a finite number of singularities and the alien derivations \Ptranslate singularities\Q, we have |\>> \=0> for some, so the matrices >> are nilpotent. More generally, if ,\,\\\>> are >-linearly independent, then all elements in the algebra generated by >,\,B>> are nilpotent. It is easily shown that the Stokes morphisms correspond to the exponentials |\>>>> of directional Alien derivations |\>>=\\*\>*\>>|\>>>. This yields a way to reinterpret the Stokes matrices in terms of the >> with\\*\>*\>>. In particular, the preceding discussion implies that the Stokes matrices are unipotent. \ The extra flexibility provided by pointwise over directional alien derivatives admits many applications, such as the preservation of realness. For further details, see . A complex number is said to be if there exists an for which takes \\>*2>> on input and which returns an >-approximation> \+\*\|)>*2>> of for which -z|\|>\\>. The of this approximation algorithm is the time > it takes to compute a >-approximation for . It is not hard to show that the set > of effective complex numbers forms a field. However, given \> the question whether is undecidable. The following theorems were proved in . <\theorem> Let \|]>>, \\\\>, \|)>> and \\>>. Given a broken line path \ =z\\\z> on \\>, we have <\enumerate-alpha> The value |)>> of the analytic continuation of at the end-point of > is effective. There exists an approximation algorithm of time complexity d*log log d|)>> for|)>>, when not counting the approximation time of the input data , > and >. There exists an algorithm which computes an approximation algorithm for |)>> as in () as a function of , > and >. <\theorem> Let \|]>> be regular singular in . Let \\\\>, \|)>> and \\>>. Then > is well-defined for all sufficiently small > on the effective Riemann surface |\>> of above >, and <\enumerate-alpha> |)>> is effective. There exists an approximation algorithm of time complexity d*log log d|)>> for|)>>, when not counting the approximation time of the input data , > and >. There exists an algorithm which computes an approximation algorithm for |)>> as in () as a function of , > and >. In general, the approximation of |)>> involves the existence of certain bounds. In each of the above theorems, the assertion () essentially states that there exists an algorithm for computing these bounds as a function of the input data. This property does not merely follow from () and () alone. The following theorem has been proved in . <\theorem> Let \|]>> be singular in . Let > be as in theorem and =,\,z|)>\dom \:\,\,\,z\\|}>>. Given \*\> with \|)>> and \\>, we have <\enumerate-alpha> |)>> is effective. There exists an approximation algorithm of time complexity d*log log d|)>> for|)>>, when not counting the approximation time of the input data , > and >. There exists an algorithm which computes an approximation algorithm for |)>> as in () as a function of , > and >. If we replace > by an arbitrary effective algebraically closed subfield > of >, then the assertions () and () in the three above theorems remain valid (see in the cases of theorems and ), but the complexity in () usually drops back to*log> d|)>>. Notice also that we may replace|)>> by the transition matrix along > in each of the theorems. The following theorem summarizes the results from section . <\theorem> Let > be an effective algebraically closed constant field of >. Then there exists an algorithm which takes \|]>> and \\\|}>> on input, and which computes a finite set \|)>>, such that <\enumerate-alpha> The group >>> is generated by > as a closed algebraic subgroup of |)>>. If =\>, then the entries of the matrices in > have time complexity d*log log d|)>>. <\proof> It is classical that the set > of effective complex numbers forms a field. Similarly, the set > of effective complex numbers with an approximation algorithm of time complexity d*log log d|)>> forms a field, since the operations >, >, >> and can all be performed in time >. In particular, the classes of matrices with entries in > > are stable under the same operations. Now in the algorithm , we may take broken-line paths with vertices above > for the >. Hence () and () follow from theorem () () and the above observations. Given \\>*2>>, we may endow > with an approximate zero-test for which if and only if \\>. We will denote this field by \>>. Clearly, this zero-test is not compatible with the field structure of >. Nevertheless, any finite computation, which can be carried out in > with an oracle for zero-testing, can be carried out in exactly the same way in \>> for a sufficiently small >. Given \>, we will denote by \>\\\>> the \Pcast\Q of to \>> and similarly for matrices with coefficients in >. <\remark> In practice , effective complex numbers usually come with a natural bound\>*2>> for >. Then, given \\>*2>> with \1>, it is even better to use the approximate zero-test if and only if \\*M>. Notice that the bound usually depends on the internal representation of and not merely on as a number in >. Let > be an effective algebraically closed subfield of >. Consider a monic linear differential operator +L*\+\+L\\|]>>, where =\>. In this section, we present an algorithm for finding a non-trivial factorization *K> with ,K\\|]>> whenever such a factorization exists. and invariant subspaces under >>> Let =,\,h|)>\\> be a basis of solutions for the equation , where \\> is an abstract differential field. We denote the Wronskian of > by <\equation*> W>=W,\,h>=>|>|>>|>||>>|>>|>|>>>>>>. It is classical (and easy to check) that <\equation> L f=,\,h>|W,\,h>>. When expanding the determinant ,\,h>> in terms of the matrices <\equation*> W=W,i>=>|>|>>|>||>>|>>|>|>>>|>>|>|>>>|>||>>|>>|>|>>>>>>, it follows that <\equation*> L=\-|W>*\+\+1|)>*|W>. Denoting by >> the logarithmic derivative of >, it can also be checked by induction that <\equation*> =-,\,h>|W,\,h>>|)>>|)>*\*-,h>|W>>|)>>|)>*-W>>|)> admits ,\,h> as solutions, whence =L>, using Euclidean division in the skew polynomial ring |]>>. <\proposition> <\enumerate-alpha> If admits a factorization *K>, then >> leaves > invariant. If is an invariant subvector space of >>, then admits a factorization K*K> with >. <\proof> Assume that admits a factorization *K>. Then, given ker K> and \>>, we have *f=0=M*K f=K*M*f>, whence ker K>. Conversely, assume that is an invariant subvector space of >> and let > be a basis of . Then we observe that ,i>=*W,i>> for all . Consequently, <\equation*> M*,i>|W,0>>=,i>|W,0>> for all , so that ,i>/W,0>\\>, by corollary . Hence <\equation> K=\-,1>|W,0>>*\+\+1|)>*,r>|W,0>> is a differential operator with coefficients in > which vanishes on . But this is only possible if > divides . <\lemma> Let > be a non-unitary algebra of nilpotent matrices in |)>>. Then there exists a basis of > in which is lower triangular for all \>. <\proof> Let \> be a matrix such that is a non-zero vector space of minimal dimension. Given \V> and \>, we claim that \ker M>. Assume the contrary, so that M*N*\\im M*N\V>. By the minimality hypothesis, we must have . In particular, \im M*N> and M*N*\\im M*N*M*N>. Again by the minimality hypothesis, it follows that . In other words, the restriction of to is an isomorphism on . Hence admits a non-zero eigenvector in , which contradicts the fact that is nilpotent. Let us now prove the lemma by induction over . If 1> or =0>, then we have nothing to do, so assume that 1> and \0>. We claim that > admits a non-trivial invariant subvector space . Indeed, we may take if *V=0> and *V> if *V\0>. Now consider a basis ,\,\|)>> of and complete it to a basis ,\,\|)>> of >. Then each matrix in > is lower triangular with respect to this basis. Let > and> be the algebras of lower dimensional matrices which occur as upper left lower right blocks of matrices in >. We conclude by applying the induction hypothesis on > and >. Let > be a finite set of non-zero nilpotent matrices. If all matrices in the >-algebra> generated by > are nilpotent, then it is easy to compute a basis for which all matrices in > are lower triangular. Indeed, setting =\>ker M> for all , we first compute a basis of >. We successively complete this basis into a basis of >, > and so on until =\>. If not all matrices in > are nilpotent, then the proof of lemma indicates a method for the computation of a matrix in > which is not nilpotent. Indeed, we start by picking an \> and set im M>, where is smallest with =0>. We next set \\\> and iterate the following loop. Take a matrix \> and distinguish the following three cases: <\description> >Set \\\> and continue. M*N*V\V>>Set M*N*M>, im M> and continue. >Return the non-nilpotent matrix . At the end of our loop, we either found a non-nilpotent matrix, or we have ker M> for all \>. In the second case, we obtain a non-trivial invariant subspace of > as in the proof of lemma and we recursively apply the algorithm on this subspace and a complement. In fact, the returned matrix is not even ( not of the form +N>, where is a nilpotent matrix), since it both admits zero and a non-zero number as eigenvalues. Proposition in combination with theorem implies that the factorization of linear differential operators in |]>> reduces to the computation of non-trivial invariant subvector spaces under the action of >> whenever they exist. In this section, we will first solve a slightly simpler problem: assuming that > is an effective algebraically closed field and given afinite set of matrices \|)>>, we will show how to compute a non-trivial invariant subspace of > under the action of>, whenever such a exists. >>Given a vector \\> it is easy to compute the smallest subspace >|)>> of > which is invariant under the action of > and which contains>. Indeed, starting with a basis =|}>>, we keep enlarging > with elements in *\\|)>> until saturation. Since > will never contain more than elements, this algorithm terminates. A \\> for generating a non-trivial invariant subspace of> is said to be if dim >|)>\n>. >-algebra generated by >>We notice that \> is an invariant subspace for>, if and only if is an invariant subspace for the >-algebra |)>> generated by>. Again it is easy to compute a basis for |)>>. We start with a basis > of |)>> and keep adjoining elements in \|)>> to > until saturation. We will avoid the explicit basis of |)>>, which may contain as much as > elements, and rather focus on the efficient computation of good candidate vectors. >-splittings>A decomposition =E\\\E>, where ,\,E> are non-empty vector spaces, will be called an >-splitting> of >, if the projections =P>> of > on > are all in |)>>. Then, given |)>>, we have |)>> if and only if *M*P\|)>> for all. If we choose a basis for > which is a union of bases for the >, we notice that the *M*P> are \dim E> block matrices. In the above algorithm for computing the >-algebra generated by > it now suffices to compute with block matrices of this form. In particular, the computed basis of |)>> will consist of such matrices. The trivial decomposition =\> is clearly an >-splitting. Given |)>>, we notice that any >-splitting is also an >-splitting. >-splittings>An >-splitting =F\\\F> is said to be than the >-splitting =E\\\E> if > is a direct sum of a subset of the > for each . Given an >-splitting =F\\\F> and an arbitrary element |)>>, we may obtain a finer >-splitting > as follows. Let ,k|}>> and consider =P*M*P>. If ,\,\> are the eigenvalues of >, then =ker -\|)>>\\\ker -\|)>>> is an *\*P|)>>-splitting of >, where =dim E>. Collecting these *\*P|)>>-splittings, we obtain a finer >-splitting \\\F> of >. This >-splitting, which is said to be >, has the property that >*M*P>> is monopotent on > for each, with unique eigenvalue>>. We now have the following algorithm for computing non-trivial >-invariant subspaces of > when they exist. <\named-algorithm-old|Invariant_subspace> <\math> |)>> a set of non-zero matrices in |)>> an >-invariant subspace of > or <\algorithm-body> [Initial >-splitting] <\indent> Compute a ``random non-zero element'' of |)>> Compute an >-splitting =E\\\E> and each \> \\> [One dimensional components] <\indent> For every > with =1> and \\>, do the following: <\indent> Pick a \E>> and compute >|)>> If >|)>\\> then return >|)>> Otherwise, set \\\E> If =1> for all then return [Higher dimensional components] <\indent> Let be such that \1> Let \*>|)>*P:M\\|}>> Let \E\\>ker M> If =0> then go to step 4 and otherwise to step 5 [Non-triangular case] <\indent> Let |)>> be non-monopotent on > (cf. previous section) Refine the >-splitting and return to step 2 [Potentially triangular case] <\indent> Choose \K> and compute >|)>> If >|)>\\> then return >|)>> Otherwise, let be in |)>> with *N*\\K> Refine the >-splitting If this yields a finer >-splitting then return to step 2 Otherwise, set \\\> and repeat step 5 The algorithm needs a few additional explanations. In step , we may take to be an arbitrary element in >. However, it is better to take a \Psmall random expression in the elements of >\Q for . With high probability, this yields an >-splitting which will not need to be refined in the sequel. Indeed, the subset of matrices in |)>> which yield non-maximal >-splittings is a closed algebraic subset of measure zero, since it is determined by coinciding eigenvalues. In particular, given an >-splitting =E\\\E> , it will usually suffice to check that each \> is monopotent on each>, in order to obtain an >-splitting the other elements in >. Throughout the algorithm, the >-splitting gets finer and finer, so the >-splitting ultimately remains constant. From this point on, the space > can only strictly decrease in step , so > also remains constant, ultimately. But then we either find a non-trivial invariant subspace in step 5, or all components of the >-splitting become one-dimensional. In the latter case, we either obtain a non-trivial invariant subspace in step 1, or a proof that >|)>=\> for every \E>\\\E>> (and thus for every \\\0>). <\remark> Assume that > is no longer an effective algebraically closed field, but rather a field \>> with an approximate zero-test. In that case, we recall that a number which is approximately zero is not necessarily zero. On the other hand, a number which is not approximately zero is non-zero. Consequently, in our algorithm for the computation of |)>>, the dimension of |)>> can be too small, but it is never too large. In particular, if the algorithm fails, then the approximate proof that >|)>=\> for every \E>\\\E>> yields a genuine proof that there are no non-trivial invariant subspaces. Putting together the results from the previous sections, we now have the following algorithm for finding a right factor of . <\named-algorithm-old|Right_factor> > +L*\+\+L\\|]>> a non-trivial right-factor of or <\algorithm-body> [Compute generators] <\indent> Choose \\\\> and let =\>> Compute a finite set \|)>> of generators for >> ( theorem ) [Initial precision] <\indent> max,\,deg L|)>+1> \232>> \min/M,j>:M\\,M,j>\/2>\0|}>\\> \\> \\/2> [Produce invariant subspace] <\indent> Let >\>|)>> If > then return Let \>|)>> be a column basis of Let \>B*\\|]>\>|]>|)>> [Produce and check guess] <\indent> Let \-,1>|W,0>>*\+\+1|)>*,r>|W,0>>> Divide by , producing \>|)>|]>|]>> with If 0 mod z> then go to step 5 Reconstruct ,\\|]>> from and with precision ,T|)>> If we obtain no good approximations or *> then go to step 5 Return > [Increase precision] <\indent> 2*T> \\/2> Go to step 3 The main idea behind the algorithm is to use proposition in combination with so as to provide good candidate right factors of in |)>|]>>. Using reconstruction of coefficients in > from Laurent series in |)>> with increasing precisions, we next produce good candidate right factors in >. We keep increasing the precision until we find a right factor or a proof that is irreducible. Let us detail the different steps a bit more: <\description> We will work with power series approximations of terms and approximate zero-tests in \>>. The degree of a rational function is defined by >. The initial precisions and log \> have been chosen as small as possible. Indeed, we want to take advantage of a possible quick answer when computing with a small precision (see also the explanations below of step 5). If fails, then there exists no factorization of , by remark. Effective power series and Laurent series are defined in a similar way as effective real numbers (in particular, we don't assume the existence of an effective zero-test). Efficient algorithm for such computations are described in . The reconstruction of > and > from and contains two ingredients: we use Padé approximation to find rational function approximations of degree > T> and the LLL-algorithm to approximate numbers \>> by numbers in>. Doubling the precision at successive steps heuristically causes the computation time to increase geometrically at each step. In particular, unsuccessful computations at lower precisions don't take much time with respect to the last successful computation with respect to the required precision. Instead of multiplying the precisions by two, we also notice that it would be even better to increase by a factor which doubles the estimated computation time at each step. Of course, this would require a more precise complexity analysis of the algorithm. The problem of reconstructing elements in > from elements in \>> is an interesting topic on its own. In theory, one may consider the polynomial algebra over > generated by all coefficients occurring in and the number we wish to reconstruct. We may then apply the LLL-algorithm on the lattice spanned by > monomials of smallest total degree (for instance) and search for minimal > >-digit relations. If =\> is the algebraic closure of >, then we may simply use the lattice spanned by the first powers of . At a sufficiently large precision , the LLL-algorithm will ultimately succeed for all coefficients of a candidate factorization which need to be reconstructed. If there are no factorizations, then the algorithm will ultimately fail at step 3. This proofs the termination of . <\remark> In practice, and especially if \\>, it would be nice to use more of the structure of the original problem. For instance, a factorization of actually yields relations on the coefficients which we may try to use. For high precision computations, it is also recommended to speed the LLL-algorithm up using a similar dichotomic algorithm as for fast computations . <\remark> Notice that we did not use bounds for the degrees of coefficients of possible factors in our algorithm. If a bound > is available, using techniques from , then one may take min|)>> instead of 2*T> in step 5. Of course, bounds for the required precision > are even harder to obtain. See for some results in that direction. Throughout this section, > will stand for the field \>> of effective complex number with the approximate zero-test at precision \0>. This field has the following properties: <\description> We have an effective zero-test in >. There exists an algorithm which takes on input \>|)>> and which computes a finite set of generators for the >-vector space of integers \\> with>=1>. There exists an algorithm which takes on input \\> and which computes a finite set of generators for the >-vector space of integers \\> with \\=0>. > is closed under exponentiation and logarithm. Indeed, we obtain and using the LLL-algorithm. Some of the results in this section go through when only a subset of the conditions are satisfied. In that case, we notice that >, > and >(>). Given a finite set of matrices \|)>>, we give a numerical algorithm for the computation of the smallest closed algebraic subgroup =|\|\>> of |)>> which contains>. We will represent > by a finite set \|)>> and the finite basis \|)>> of a Lie algebra> over >, such that <\equation*> \=\*\>, and each \> corresponds to a unique connected component >=\>*N> of>. We will also prove that there exists a precision > such that the algorithm yields the theoretically correct result for all \\>. Let |)>> be the group of invertible diagonal matrices. Each matrix has the form |)>>, where =,\,\|)>> is the vector in >|)>> of the elements on the diagonal of . The coordinate ring > of |)>> is the set ,\1>|]>> of Laurent polynomials in >. Now consider the case when > consists of a single diagonal matrix |)>>. Let \\> be the ideal which defines |M|\>\|)>>. Given a relation >=1\\|)>> between the>, any power =Diag|)>> satisfies the same relation |)>>=1>, whence >-1\\>. Let > be the ideal generated by all >-1>, such that >=1>. <\lemma> We have =\>. <\proof> We already observed that \\>. Assuming for contradiction that \\>, choose <\equation*> f=f*\>\\\\ such that is minimal. If j>, then -\>\1>, since otherwise -\>\\> and *\>+f*\>\\\\> has less than terms. In particular, the vectors >,\,\*\>|)>> with ,r|}>> are linearly independent. But this contradicts the fact that |)>=f*\>=0> for all ,r-1|}>>. By , we may compute a minimal finite set ,\,\> of generators for the >-vector space of \\> with >=1>. We may also compute a basis > for >, where :\\\;\\\\,\,\\\|)>>. Then>=\|)>>> is the connected component of |M|\>>, since >|)>>=1> for all , and > cannot be further enlarged while conserving this property. Let =*\\\\\*\|)>\\>. We construct a basis ,\,\> of >, by taking > to be shortest in > (if p>) or > (if p>), such that \,\,\|)>>. This basis determines a toric change of coordinates \\> with |)>> such that ,\,\\\\0> with respect to the new coordinates. Similarly, we may construct a basis ,\,\> of >, by taking each > to be shortest in \,\,\|)>> such that =min \>:r*\\\*\\\\\*\|}>> is maximal. This basis determines a second toric change of coordinates \\> with |)>> such that =r*\> (,p>) with respect to the new coordinates. After the above changes of coordinates, the ideal > is determined by the equations >=\=\>=1>. Setting <\equation*> \=*\*s/r>,\,\*\*s/r>,1,\,1|)>:\\\,s\r,\,s\r|}>, it follows that |M|\>=\*\>>. Rewriting > with respect to the original coordinates now completes the computation of |M|\>>. Let us now consider the case when > consists of a single arbitrary matrix . Then we first compute the multiplicative Jordan decomposition of . Modulo a change of basis of >, this means that <\equation*> M=D*U=U*D, where > and > are the and parts of : <\equation*> D=*I>>||>||>|>|||*I>>>>>>,U=>>||>||>|>|||>>>>>>, where <\equation*> J=|||>|||>|>|||>|>||||>>>>. <\proposition> We have |U|\>=*log U|)>:\\\|}>>. <\remark*> Notice that =>f*N=f*N> is well-defined for power series \|]>> and nilpotent matrices |)>>; in this case, >> and . <\proof> The assertion is clear if >, so assume I>. Let =*log U|)>:\\\|}>>. We clearly have |U|\>\\>, since > is a closed algebraic group which contains . Moreover, the set ,U,\> is infinite, so |U|\>\1>. Since > is irreducible and =1>, we conclude that |U|\>=\>. <\proposition> We have |M|\>=|D|\>*|U|\>>. <\proof> Since |M|\>> is a commutative group, implies that |M|\>=|M|\>*|M|\>>, where |M|\>=:N\|M|\>|}>> and |M|\>=:N\|M|\>|}>> are closed subgroups of |M|\>>. Now |D|\>> and |U|\>> are closed subgroups of |M|\>> |M|\>>, so |D|\>*|U|\>> is a closed subgroup of |M|\>>. Since |D|\>*|U|\>>, it follows that |M|\>=|D|\>*|U|\>>. <\corollary> If |D|\>=\*\>>, then |M|\>=\*\+\*log U>>. In order to compute the closure of the product of a finite number of algebraic groups of the form *\>>, an important subproblem is to test whether a given matrix |)>> belongs to >>. We first observe that \>> implies |M|\>\\>>. After the computation of > and > with |M|\>=\*\>> it therefore suffices to check that \\> and \\>>. In fact, it suffices to check whether \\>>, where > is the unique matrix in > with M*\>>. Modulo a suitable base change, we have thus reduced the general problem to the case when is a diagonal matrix whose eigenvalues are all roots of unity. Assume that \>> and \\> are such that \*\>>. Since and > commute, it follows that and > can be diagonalized a common basis. The elements of this basis are elements of the different eigenspaces of . In other words, if *I>,\,\*I>|)>> with pairwise distinct >, then 1>*\*P> is diagonal for some block matrix ,\,P|)>> with \>|)>> for each . It follows that =Diag,\,\|)>> for certain \>|)>>. Without loss of generality, we may therefore replace > by the intersection of > with >|)>,\,>|)>|)>>. From now on, we assume that the above two reductions have been made. Let =Diag,\,\|)>> be a diagonal matrix in >. By lemma , we have \*\>> if and only if any >-linear relation \\=0> induces a relation |)>>=1>, where |)>=+\+l>,\,l>+\+l|)>>. Now consider a random matrix in >, a linear combination of the basis elements with small random integer coefficients. We compute its blockwise Jordan normal form 1>*R*P> so that Diag>|)>,\,>|)>|)>> and let > be the restriction of to the diagonal. We have \*\>\M\\*J>\M=P*M*P1>\\*R>>. Computing a basis for the >-linear relations of the form \\=0> using , the above criterion now enables us to check whether \*R>>. If the check whether \*R>> succeeds, then we are clearly done. Otherwise, since was chosen in a random way, the relation \\> is very likely to be satisfied for all possible choices of \> (up to permutations of coordinates inside each block). Indeed, the for which this is not the case lie on a countable union > of algebraic variety of a lower dimension, so> has measure . Heuristically speaking, we may therefore conclude that \>> if the check fails (at least temporarily, modulo some final checks when the overall computation of |\|\>> will be completed). Theoretically speaking, we may perform the above computations with =\>> \*B> instead of , where > is a basis of > and the > are formal parameters. We then check whether the relation \\> is still satisfied for the analogue =Diag,\,\|)>> of >. If so, then we are sure that \>>. Otherwise, we keep trying with other random elements of>. It is likely that a more efficient theoretical algorithm can be designed for testing >-linear relations between the eigenvalues of elements in >. One of the referees suggested to use similar methods as in . However, we did not study this topic in more detail, since our final algorithm for the computation of Galois groups will be based on heuristics anyway. We also notice that a \Preally good\Q random number generator should actually generate points which satisfy non-trivial algebraic relations. >> A Lie algebra > is said to be , if it is the Lie algebra of some algebraic group, if >> is an algebraic subset of |)>>. It is classical that the smallest Lie algebra generated by a finite number of algebraic Lie algebras is again algebraic. The Lie algebras we will consider in our algorithms will always assumed to be algebraic. Given a finite number ,\,\> of algebraic Lie algebras and a basis > for +\+\>, it is easy to enrich > so that =|)>> is a Lie algebra: as long as ,\|]>\\> for two elements ,\\\>, we add ,\|]>> to >. By what precedes, the computed Lie algebra > is again algebraic. Putting together the ingredients from the previous sections, we now have the following algorithm for computing the smallest closed algebraic group |\|\>> which contains>. <\named-algorithm-old|Closure> (>) A subset =,\,M|}>> of |)>> a numeric approximation of |\|\>> <\algorithm-body> [Initialize algorithm] <\indent> Compute |M|\>=\*\>> for each ,m|}>> Let \\\\\\> (notice that \>) Let \+\+\|)>> [Closure] <\indent> While there exists an \\> with *N1>\\> set \+N*\*N1>|)>> While there exists an \\> with \>> set \\\> While there exists \> with \*\>> do <\indent> Compute |N|\>=\*\>> If \\> then set \+\|)>>, quit loop and repeat step 2 Otherwise, set \\\> Return *\>> The termination of this algorithm relies on a lemma, whose proof was kindly communicated to the author by J.-Y. Hée. <\lemma> Let > be a closed algebraic subgroup of |)>> and let ,\,M\|)>> be afinite number of matrices in the normalizer of >. Denote by > the group generated by> and,\,M>. If all elements in /\> have finite order, then /\> is finite. <\proof> In the case when =>, the result is classical . In the general case, the normalizer > of > is a closed algebraic subgroup of |)>> and > is a normal subgroup of >. By , it follows that/\> is an affine algebraic group which is isomorphic to a closed algebraic matrix group. This reduces the general case to the special case when =>. <\theorem> There exists an \\>*2>> such that, for every \\>*2>> with \\>, the set *\>> returned by >, considered as a subset of |)>>, coincides with the smallest closed algebraic subgroup |\|\>> of |)>> which contains >. <\proof> Clearly, the dimension of > increases throughout the execution of the algorithm, so it remains ultimately constant. At this point, the set > will keep growing and the lemma implies that> ultimately stabilizes. When this happens, > is closed under multiplication modulo >>, as well as under multiplicative inverses, since each element in > has finite order modulo >>. We conclude that *\>> is indeed the smallest closed algebraic subgroup of |)>> which contains>, provided that the approximate zero-test always returns the right result. In order to prove the correctness at a sufficient precision, we assume that we use the theoretic membership test from section and that the random number generator successively generates the same random numbers each time we relaunch the algorithm at a higher precision. Now consider the trace of the execution of our algorithm when using an infinite precision. Let > be a sufficient precision such that all zero-tests in this execution tree are still correct when we replace the infinite precision by a precision \\>. Then the trace of the execution any finite precision \\> coincides with the trace of the execution at infinite precision. This completes the proof. <\remark> The main improvement of the algorithm the algorithm from lies in the more efficient treatment of the connected component (using linear algebra). On the other hand, the mere enumeration of representatives in each connected component can be very unefficient (although a Gröbner basis might be of the same size). Fortunately, we will see in the next sections how to remove this drawback. Assume now that > is the set of generators for >>> as computed in theorem . Assume that we have computed a reasonable candidate *\>> for |\|\>>, expressed in the original basis corresponding to >>. We still have to reconstruct |~>\|)>> and |~>=|~>|)>> with |~>\|)>> such that *\>\|)>=|~>*\|~>>\|)>>. In the case of |~>>, by selecting a suitable basis of |)>>, we may consider |~>> as a big n> matrix whose first columns are linearly independent. We compute the row-echelon form of this basis: <\equation*> E=|||>|>|>>||>||>||>>||||>|>|>>>>>. The entries of must be in >: provided that |~>> is indeed generated by a basis of matrices with entries in >, the row-echelon form of this second basis coincides with . It therefore suffices to reconstruct the entries of using the LLL-algorithm. In the case of a matrix \>, the set |~>>> is an algebraic variety of dimension over>. Now choose \M*\|~>>> close to in such a way that independent coordinates of > are all in \\>. Then the other coordinates of >, considered as elements of >, are easily found using Newton's method. Since |~>>> is an algebraic variety, these other coordinates are actually in >, and we reconstruct them using the LLL-algorithm. The algorithm from the previous section is quite inefficient when the set > becomes large. It is therefore useful to seek for a better computational representation of>. For finite groups >, one classical idea is to search for a sequence of subgroups <\equation> 1=\\\\\\\=\ such that the indices \> are small. Then we may represent elements in > by sequences ,\,a|)>> with \\/\> for each . This representation is particularly useful if > operates on a set > and if there exists points ,\,a> in > such that <\equation*> \=S,\,a> is the stabilizer of the set ,\,a|}>> for each . Then the set ,\,a>/S,\,a>> corresponds to the orbit of > while leaving ,\,a> fixed . In the case of matrix groups, one often takes > for > . However, this approach only yields interesting results when there exist non-trivial invariant subspaces under the action of the group, which will usually not be the case for us (otherwise we may factor and consider smaller problems). A theoretical way out of this is to also consider the action of> on exterior powers \>. However, this approach is very expensive from a computational point of view. In our more specific context of matrices with complex entries, we will therefore combine two other approaches: non-commutative lattice reduction and the operation of > on |)>/\>> via conjugations M*N*M>. The algebra |)>> admits a natural (multiplicative) norm, given by <\equation*> |M|\<\|\|\>>=sup :V\\,=1|}>, where \|> stands for the Euclidean norm on >. If =|\|\>/\>> is finite, this enables us to construct =1,\,\,\> as in () as follows. Assuming that ,\,\> have been constructed, we consider a matrix \|\|\>\\*\>> for which |M-1|\<\|\|\>>> is minimal, and let > be the set generated by *\>> and > in >. This construction allows us to rapidly identify a big commutative part of >. More precisely, we have <\proposition> Let |)>> be such that =|A-1|\<\|\|\>>\1> and =|B-1|\<\|\|\>>\1>. Then we have <\equation*> |A*B*A1>*B1>-1|\<\|\|\>>\B,\|)>=|1-\>+|1-\>+*\||)>*|)>>. <\proof> Writing > and >, we expand 1>=1-\+\+\> and 1>=1-\+\+\> in *B1>>. This yields a non-commutative power series in > and > whose terms in > and > vanish. It follows that <\equation*> |A*B*A1>*B1>-1|\<\|\|\>>\|)>*|)>*>*>-1-2*\-2*\=B,\|)>. The proposition implies that |A*B*A1>*B1>-1|\<\|\|\>>\min,\|)>> whenever ,\|)>\5->. Now take > and > with j>, where the > are as above. Then it follows that and commute whenever ,\|)>\|M-1|\<\|\|\>>>. What is more, proposition shows that taking commutators is a convenient way to construct matrices close to identity from a set of non-commutative generators. However, from the effective point of view, we will not compute the computation of minimal representatives > in cosets of algebraic groups in detail. We will rather simulate such a computation in a way which is sufficient for our purpose. If \> is such that |M-1|\<\|\|\>>> is small, then we will also try to use the fact that the centralizer > of is often a big subgroup of |\|\>/\>>, so the orbit of N*M*N> is small. Let > be a closed algebraic subgroup of |)>> with associated Lie-algebra >. In this section, we will show how to compute efficiently with elements of the finite group =\/\>>. Until the very end of this section, we assume that > is included in the connected component of the normalizer of >> in |)>>. We denote by > the Lie algebra of this connected component. By , we have =|)>:|]>\\|}>>. Let \> and recall that belongs to the normalizer of>>. If |M-1|\<\|\|\>>\1>, then |)>> also belongs to the normalizer of >>. Since \*X>> lies in the connected component of this normalizer, we have \>. Now consider the orthogonal supplement >> of > for the Hermitian product on |)>>. We define >=\>, where is the orthogonal projection of on >>. From |]>\\>, it follows that >\M*\>>, and we denote |M|\<\|\|\>>>=|\>|\<\|\|\>>>. Since >> is connected, the function log M> may actually be analytically continued to a multivalued function >\\>. After choosing branch cuts (the way this is done is not crucial for what follows, provided that we make the standard choice for with |M-1|\<\|\|\>>\1>), this allows us to extend the definitions of >> and |\|\<\|\|\>>>> to the case when |M-1|\<\|\|\>>\1>. >>Let \> and > be such that <\itemize> >\\>. >> generates *X>\\|)>/\>>. |M|\<\|\|\>>>\|M|\<\|\|\>>>> whenever \M>> is another such generator. Let *\*p> be the prime-decomposition of the order of modulo >>, with \\\p>. Let =X> and =M*\*p>> for all ,l|}>>. Let > be the subgroup of > of elements which commute with > modulo >>, so that \\\\=\>. For ,r|}>>, we represent elements in the quotient /\> by elements in the orbit of the action >:N\A*N*A> modulo >. Since |]>\\>, the set =\\\*X> is a Lie algebra whose normalizer contains >. Consequently, \M>\\/\>>, and we represent elements in > by products *P>, with \> and >\\/\>>. The elements in /\>> are represented in a similar way as the elements in >, using recursion. The successive matrices for /\>>, /\>>, will be called a for >. A basis ,\,B|)>> is said to be if |B|\<\|\|\>>>\\\|B|\<\|\|\>>>>. Let ,\,B|)>> be a sorted basis for =\/\>> and assume that we want to compute the extension |^>=|\,N|\>> of > by a new matrix. Whenever we hit an element *\>\|^>=|^>/\>> with ||\<\|\|\>>>\|B|\<\|\|\>>>> during our computations, then we start the process of basis reduction, which is described below. Whenever we find an element in |^>\\>, then we abort all computations and return this element (indeed, in that case, we may continue with the closure of the connected component in ). Let >, , be as above. We start by computing the orbit of |^>> modulo > for >>. Whenever we hit an element 1> (modulo >>) with |B*P*B1>*P1>|\<\|\|\>>>\|B|\<\|\|\>>>> or |P|\<\|\|\>>>\|B|\<\|\|\>>>>, then we start the process of basis reduction. Otherwise, we obtain a finite orbit, together with a finite number of matrices by which we have to extend >. We keep doing this using the same method for > until >. At the end, we still have to show how to extend > with a new matrix >. Now recursive application of the algorithm to |~>=\/\>> and > yields a sorted basis ,\,>>. When keeping track of the corresponding powers of > during the computations, we also obtain a finite system of generators for |^>\\*X>>. Using computations we either obtain aminimal generator > or a new element in the connected component. In the first case, we return ,,\,>|)>> if ||\<\|\|\>>>\||\<\|\|\>>>> and apply basis reduction otherwise. Let ,\,B> be in > with |B|\<\|\|\>>>\\\|B|\<\|\|\>>>>. We call ,\,B|)>> a . In the above algorithms, raw bases occur when we are given an ordered basis ,\,B|)>> for >, and we find a new element > with |B|\<\|\|\>>>\|B|\<\|\|\>>>>. Using the above base extension procedure, we may transform a raw basis ,\,B|)>> into a basis for >: starting with |)>>, we successively add ,\,B>. However, it is more efficient to reduce ,\,B|)>> first. More precisely, let us now describe a procedure which tries to replace ,\,B|)>> by a better raw basis ,\,>|)>>, with |,\,>|\>=|B,\,B|\>>, and whose elements are closer to identity. Of course, we may always return the original basis if a better one could not be found. We first test whether all basis elements are roots of unity modulo >. If not, then we found a new element in the connected component. We next test whether there exist with |B*B*B1>*B1>|\<\|\|\>>>\|B|\<\|\|\>>>>, in which case we keep adding the smallest such commutator to the basis. Whenever this stops, we write =\>,\,B=\>> with ,\,X\\>> and consider all lattice reductions \X+k*X\|)>> proposed by the LLL-algorithm in the commutative vector space >>. Whenever |B*B|\<\|\|\>>>\|B|\<\|\|\>>>, for one such reduction, then we perform the corresponding reduction \B*B> on our basis and keep repeating the basis reduction process. We still have to show how to deal with the case when > is not included in the connected component >> of the normalizer of >> in |)>>. In that case, we start with the computation of a basis for >, using linear algebra. Since >\\> is a normal subgroup of >, we have \/\>|)>*>\\|)>>. Now we have explained above how to compute with elements in >\\>. If \\>, then may use recursion for computations in the finite group /\>>. If =\>, then elements in /\>> have necessarily small order, so we simply list the elements of /\>>. We hope that we provided convincing evidence that analytic methods may be used for the efficient computation of differential Galois groups and related problems like the factorization of linear differential operators. The two main remaining challenges are the concrete implementation of the algorithms presented here (as part of a more general library for the computation with analytic functions such as ) and the development of or methods for ensuring the correctness of the computed result. Some ideas into this direction are as follows: <\itemize> Use theoretical bounds on the number of connected components of the computed Galois group and related bounds on the sizes of the basis elements in and. See for some results. Use the classification theory for algebraic groups in order to gather more information about the computed Galois group >. In particular, it is useful to compute the radical (or unipotent radical) of >, thereby reducing the study of > to the study of a finite group, a semisimple (or reductive) group and a solvable (or unipotent) group125>. We refer to for computational aspects of the corresponding Lie algebras. Use the classical theory of invariant subspaces in symmetric products or exterior powers as an correctness check and search for an effective version of Chevalley's theorem . One may start with generalizing and notice that a better knowledge of the Galois group > helps to further restrict the number of monomials ( \Pgeneralized exponents\Q) to be considered. Indeed, if > is an arbitrary algebraic subgroup of >, for which the ring of invariants is easy to compute, then the invariants for > must be searched in this ring. Also, their are known algorithms for computing the invariants for certain types of algebraic groups, like linearly reductive groups . The representation for algebraic groups > we used in section is efficient for computations (we merely do linear algebra in dimension >, lattice reduction and computations with small finite groups). Nevertheless, it may be interesting to reconstruct the algebraic equations for > and search for equations which are particularly sparse with respect to suitably chosen coordinates. For instance, a big cyclic group admits a particularly nice ( large) Gröbner basis well chosen ( badly chosen) coordinates. Conversely, it may be interesting to switch back from a Gröbner basis representation to our representation. Carefully identify those parts of the algorithm which either prove or disprove certain matrices to belong to the Galois group. For instance, we know that all Stokes matrices are unipotent. Given a non-zero transcendental number >, we may then reliably conclude that a Stokes matrix of the form |>>||>>>>> generates the group |>>||>>>>:\\\|}>>. An interesting idea to get rid of the transcendental part of the computations might be to quotient the values of the functions in our basis > of solutions by the action of the Galois group. For instance, if > and > are close regular points in >, is it true that the orbit of >|)>> under the action of the Galois group necessarily contains a point in >? This is clearly the case for finite Galois groups and the full Galois group, as well as for the equations =f> and |)>=0>. More generally, as soon as >|)>> becomes more transcendental, its orbit under the action of the Galois group becomes larger, so the likelihood of finding a point in the intersection with> increases. Besides the above ideas for improving the algorithms, this paper also raises a few other interesting questions: <\itemize> Are there more efficient approaches for the reconstruction of elements in > in section, both in the cases when =\> and when > is more general? Also, as pointed out above, we may want to reconstruct equations for > from the variety. Does there exists an efficient membership test in section which does not rely on probabilistic arguments? Can the approach of section be adapted to the computation of a \Pbasis\Q for the usual topological closure of a finitely generated matrix group? Of course, a better mastering of the algorithms in this paper may also lead to more efficient algorithms for other computations which rely on differential Galois theory, like the computation of Liouvillian or other forms of solutions. More generally, our algorithms may be used for other computations with algebraic matrix groups over > and other fields of characteristic . We also expect all results to generalize to holonomic systems of linear partial differential equations. The author would like to thank Hée, de Graaf, Zara, Écalle and the referees for several helpful comments and references. <\bibliography|bib|elsart-harv|all.bib> <\bib-list|51> Beke, E., 1894. Die Irreduzibilität der homogenen linearen Differentialgleichungen. Math. Ann. 45. Bertrand, D., 1995. Minimal heights and polarizations on group varieties. Duke Math. J. 80(1), 223\U250. Bertrand, D., Beukers, F., 1985. équations différentielles linéaires et majorations de multiplicités. Ann. Sci. de l'École Norm. Sup. 28(4-5), 473\U494. Borel, A., 1991. Linear algebraic groups, 2nd Edition. Springer-Verlag. Braaksma, B., 1991. Multisummability and Stokes multipliers of linear meromorphic differential equations. J. Diff. Eq 92, 45\U75. Braaksma, B., 1992. Multisummability of formal power series solutions to nonlinear meromorphic differential equations. Ann. Inst. Fourier de Grenoble 42, 517\U540. al.(1993)Candelberger, Nosmas, and Pham>Candelberger, B., Nosmas, J., Pham, F., 1993. Approche de la résurgence. Actualités mathématiques. Hermann. Chudnovsky, D., Chudnovsky, G., 1990. Computer algebra in the service of mathematical physics and number theory (computers in mathematics, stanford, ca, 1986). In: Lect. Notes in Pure and Applied Math. Vol. 125. Dekker, New-York, pp. 109\U232. Cluzeau, T., 2004. Algorithmique modulaire des équations différentielles linéaires. Ph.D. thesis, Université de Limoges. Compoint, E., Singer, M., 1998. Computing Galois groups of completely reducible differential equations. JSC 11, 1\U22. Graaf(2000)>deGraaf, W., 2000. Lie Algebras: Theory and Algorithms. Vol.56 of North Holland Mathematical Library. Elsevier science. Derksen, H., 1999. Computation of reductive group invariants. Adv. in Math. 141, 366\U384. al.(2003)Derksen, Jaendel, and Koiran>Derksen, H., Jaendel, E., Koiran, P., 2003. Quantum automata and algebraic groups. Tech. Rep. 2003-39, LIP, École Norm. Sup. de Lyon, presented at MEGA 2003; to appear in JSC. Dixon, J., 1971. The structure of linear groups. Van Nostrand Reinhold Company. Écalle, J., 1985. Les fonctions résurgentes I\UIII. Publ. Math. d'Orsay 1981 and 1985. Écalle, J., 1987. L'accélération des fonctions résurgentes (survol), unpublished manuscript. Écalle, J., 1992. Introduction aux fonctions analysables et preuve constructive de la conjecture de Dulac. Hermann, collection: Actualités mathématiques. Écalle, J., 1993. Six lectures on transseries, analysable functions and the constructive proof of Dulac's conjecture. In: Schlomiuk, D. (Ed.), Bifurcations and periodic orbits of vector fields. Kluwer, pp. 75\U184. Fabry, E., 1885. Sur les intégrales des équations différentielles linéaires à coefficients rationnels. Ph.D. thesis, Paris. Humphreys, J., 1981. Linear algebraic groups. Graduate Texts in Math. Springer. Kaplansky, I., 1957. An introduction to differential algebra. Hermann. Kolchin, E., 1973. Differential algebra and algebraic groups. Academic Press, New York. al.(1982)Lenstra, Lenstra, and Lovász>Lenstra, A., Lenstra, H., Lovász, L., 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 515\U534. Martinet, J., Ramis, J.-P., 1991. Elementary acceleration and multisummability. Ann. Inst. Henri Poincaré 54(4), 331\U401. Masser, D., 1988. Linear relations on algebraic groups. In: Baker, A. (Ed.), New advances in transendence theory. Cambridge Univ. Press, pp. 248\U262. Menous, F., 1996. Les bonnes moyennes uniformisantes et leur application à la resommation réelle. Ph.D. thesis, Université Paris-Sud, France. Mitschi, C., 1996. Differential Galois groups of confluent generalized hypergeometric equations: an approach using stokes multipliers. Pac. J. Math. 176(2), 365\U405. Moenck, R., 1973. Fast computation of gcds. In: Proc. of the 5th ACM Annual Symposium on Theory of Computing. ACM Press, New York, pp. 142\U171. Murray, S.H., O'Brien, E.A., 1995. Selecting base points for the Schreier-Sims algorithm for matrix groups. J.S.C. 18, 577\U584. Pan, V.Y., Wang, X., July 2002. Acceleration of euclidean algorithm and extensions. In: Mora, T. (Ed.), Proc. ISSAC '02. Lille, France, pp. 207\U213. Ramis, J.-P., 1985. Phénomène de Stokes et filtration Gevrey sur le groupe de Picard-Vessiot. Notes aux CRAS 301(I/5), 165\U167. Ritt, J., 1950. Differential algebra. Amer. Math. Soc., New York. Schlesinger, L., 1895. Handbuch der Theorie der linearen Differentialgleichungen. Vol.I. Teubner, Leipzig. Schlesinger, L., 1897. Handbuch der Theorie der linearen Differentialgleichungen. Vol.II. Teubner, Leipzig. Sims, C., 1970. Computational problems in abstract algebra. Pergamon press, Oxford, Ch. Computational methods in the study of permutation groups, pp. 169\U183. Sims, C., 1971. Determining the conjugacy classes of permutation groups. In: Birkhoff, G., Jr., M.H. (Eds.), Computers in algebra and number theory. Vol.4 of Proc. A.M.S. A.M.S., New York, pp. 191\U195. Singer, M., Ulmer, F., 1993. Galois groups of second and third order linear differential equations. J.S.C. 16, 9\U36. der Hoeven(1999)>vander Hoeven, J., 1999. Fast evaluation of holonomic functions. TCS 210, 199\U215. der Hoeven(2001)>vander Hoeven, J., 2001. Complex transseries solutions to algebraic differential equations. Tech. Rep. 2001-34, Univ. d'Orsay. der Hoeven(2001)>vander Hoeven, J., 2001. Fast evaluation of holonomic functions near and in singularities. JSC 31, 717\U743. der Hoeven(2002)>vander Hoeven, J., 2002. Relax, but don't be too lazy. JSC 34, 479\U542. der Hoeven(2003)>vander Hoeven, J., 2003. Majorants for formal power series. Tech. Rep. 2003-15, Université Paris-Sud, Orsay, France. der Hoeven(2005)>vander Hoeven, J., 2005. Effective complex analysis. J.S.C. 39, 433\U449. der Hoeven(2005)>vander Hoeven, J., 2005. Efficient accelero-summation of holonomic functions. Tech. Rep. 2005-54, Université Paris-Sud, Orsay, France, submitted to JSC. der Hoeven(2006)>vander Hoeven, J., 2006. Computations with effective real numbers. TCS 351, 52\U60. der Hoeven et al.(2002--2005)>vander Hoeven et al., J., 2002\U2005. Mmxlib: the standard library for Mathemagix. . der Put(1995)>vander Put, M., 1995. Differential equations modulo . Compositio Mathematica 97, 227\U251. der Put and Singer(2003)>vander Put, M., Singer, M., 2003. Galois Theory of Linear Differential Equations. Vol. 328 of Grundlehren der mathematischen Wissenschaften. Springer. van Hoeij, M., 1996. Factorization of linear differential operators. Ph.D. thesis, Univ. of Nijmegen, The Netherlands. van Hoeij, M., 1997. Factorization of differential operators with rational functions coefficients. J.S.C. 24, 537\U561. van Hoeij, M., Weil, J., 1997. An algorithm for computing invariants of differential Galois groups. J. Pure Appl. Algebra 117\U118, 353\U379. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > |->|-0.3em|>|0em||0em|>>al.(1993)Candelberger, Nosmas, and Pham|37>> > > |->|-0.3em|>|0em||0em|>>al.(2003)Derksen, Jaendel, and Koiran|37>> > > > > > > > > > > |->|-0.3em|>|0em||0em|>>al.(1982)Lenstra, Lenstra, and Lovász|38>> > > > > > > > > > > > > > > |->|-0.3em|>|0em||0em|>>Graaf(2000)|37>> > > > |->|-0.3em|>|0em||0em|>>der Hoeven(2005|a>)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven(2006)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven(1999)|38>> |->|-0.3em|>|0em||0em|>>der Hoeven(2003)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven et al.(2002--2005)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven(2001|a>)|38>> |->|-0.3em|>|0em||0em|>>der Hoeven(2002)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven(2005|b>)|39>> |->|-0.3em|>|0em||0em|>>der Hoeven(2001|b>)|38>> |->|-0.3em|>|0em||0em|>>der Put(1995)|39>> |->|-0.3em|>|0em||0em|>>der Put and Singer(2003)|39>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> Kap57 Kap57 vdPS03 vdPS03 Kol73 Kol73 Beke94 Beke94 SU93 SU93 Hum81 Hum81 vHW97 vHW97 vH97b vH97b vH:phd vH:phd Cl04 Cl04 vdP95 vdP95 vdPS03 vdPS03 Ec85 Ec85 Ec87 Ec87 Ec92 Ec92 Ec93 Ec93 Br91 Br91 Br92 Br92 Ram85b Ram85b MR91 MR91 vdH:hol vdH:hol vdH:singhol vdH:singhol vdH:reshol vdH:reshol DJK03 DJK03 LLL82 LLL82 Sims70 Sims70 Sims71 Sims71 MOB95 MOB95 DJK03 DJK03 vdH:mml vdH:mml Kol73 Kol73 Ritt50 Ritt50 Kap57 Kap57 vdH:reshol vdH:reshol Fab1885 Fab1885 vH:phd vH:phd vdH:osc vdH:osc vdH:osc vdH:osc Ec87 Ec87 Br91 Br91 Ec85 Ec85 CNP93 CNP93 CNP93 CNP93 Ram85b Ram85b MR91 MR91 MR91 MR91 Schl95 Schl95 Schl97 Schl97 Men96 Men96 Ec85 Ec85 Ec87 Ec87 Ec92 Ec92 Ec93 Ec93 CC90 CC90 vdH:hol vdH:hol vdH:singhol vdH:singhol vdH:reshol vdH:reshol vdH:effan vdH:effan vdH:maj vdH:maj vdH:effreal vdH:effreal vdH:relax vdH:relax LLL82 LLL82 Moe73 Moe73 PW02 PW02 BBeuk85 BBeuk85 vH97b vH97b vdPS03 vdPS03 BBeuk85 BBeuk85 Hum81 Hum81 Mas88 Mas88 Ber95 Ber95 CS98 CS98 Bor91 Bor91 Dix71 Dix71 Bor91 Bor91 DJK03 DJK03 Sims70 Sims70 Sims71 Sims71 MOB95 MOB95 Hum81 Hum81 vdH:mml vdH:mml DJK03 DJK03 Hum81 Hum81 dG00 dG00 Hum81 Hum81 vHW97 vHW97 CS98 CS98 Der99 Der99 Mit96 <\associate|toc> |math-font-series||1Introduction> |.>>>>|> |math-font-series||2Preliminaries> |.>>>>|> |2.1Notations |.>>>>|> > |2.2Differential Galois groups |.>>>>|> > |2.3Monodromy |.>>>>|> > |2.4The process of accelero-summation |.>>>>|> > |1|The Borel transform> |.>>>>|> > |2|Accelerations> |.>>>>|> > |3|The Laplace transform> |.>>>>|> > |2.5The Stokes phenomenon |.>>>>|> > |2.6Effective complex numbers |.>>>>|> > |math-font-series||3Factoring linear differential operators> |.>>>>|> |3.1Factoring |L> and invariant subspaces under |\>> |.>>>>|> > |3.2A lemma from linear algebra |.>>>>|> > |3.3Computation of non-trivial invariant subspaces |.>>>>|> > |1Good candidate vectors |\> |.>>>>|> > |2The |\>-algebra generated by |\> |.>>>>|> > |3|\>-splittings |.>>>>|> > |4Refining |\>-splittings |.>>>>|> > |3.4Factoring linear differential operators |.>>>>|> > |math-font-series||4Computing differential Galois groups> |.>>>>|> |4.1Introduction |.>>>>|> > |4.2The algebraic group generated by a diagonal matrix |.>>>>|> > |4.3The algebraic group generated by a single matrix |.>>>>|> > |4.4Membership testing for the connected component |.>>>>|> > |4.5Computing the closure of |\> |.>>>>|> > |4.6Fast computations with the connected components |.>>>>|> > |4.7Non-commutative lattice reduction |.>>>>|> > |1Orthogonal projection |.>>>>|> > |2Representation of the elements in |\> |.>>>>|> > |3Adding new elements to a basis |.>>>>|> > |4Basis reduction |.>>>>|> > |5The general case |.>>>>|> > |math-font-series||5Conclusion and final notes> |.>>>>|> |6Acknowledgment |.>>>>|> > |math-font-series||References> |.>>>>|>