On the Moser- and super-reduction algorithms of systems of linear differential equations and their complexity

The notion of irreducible forms of systems of linear differential equations with formal power series coefficients as defined by Moser [Moser, J.. 1960. The order of a singularity in Fuchs' theory. Math. Z. 379-398] and its generalisation, the super-irreducible forms introduced in Hilali and Wazner I Hilali, A., Wazner, A., 1987. Formes super-irreductibles des systemes differentiels lineaires. Numer. Math. 50, 429-449], are important concepts in the context of the symbolic resolution of systems of linear differential equations [Barkatou, M., 1997. An algorithm to compute the exponential part of a formal fundamental matrix solution of a linear differential system. Journal of App. Alg. in Eng. Comm. and Comp.). 8 (1). 1-23; Pflugel, E., 1998. Resolution symbolique des systemes differentiels lineaires. Ph.D. Thesis, LMC-IMAG; Pflugel, E., 2000. Effective formal reduction of linear differential systems. Appl. Alg. Eng. Comm. Comp., 10 (2) 153-187]. In this paper, we reduce (lie task of computing a super-irreducible form to that of computing one or several Moser-irreducible forms, using a block-reduction algorithm. This algorithm works on the system directly Without converting it to more general types of systems as needed in Our previous paper [Barkatou, M., Pflugel, E., 2007. Computing super-irreducible forms of systems of linear differential equations Via Moser-reduction: A new approach. In: Proceedings of ISSAC'07. ACM Press, Waterloo, Canada, pp. 1-8]. We perform a cost analysis of our algorithm in order to give the complexity of the super-reduction in terms of the dimension and the Poincare-rank of the input system. We compare Our method with previous algorithms and show that, for systems of big size, the direct block-reduction method is more efficient. (C) 2009 Elsevier Ltd. All rights reserved.