Fast Algorithms for Polynomial Solutions of Linear Differential Equations

A. Bostan, T. Cluzeau, B. Salvy


We investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzer polynomial solutions, the determination of the dimension of the vector space of polynomial solutions, the computation of a basis of this space. Previous algorithms have a bit complexity that is at least quadratic in an integer N (that can be computed from the equation), even for merely detecting the existence of nonzero polynomial solutions.

We give a deterministic algorithm that computes a compact representation of a basis of polynomial solutions in O(N log^3 N) bit operations. We also give a probabilistic algorithm that computes the dimension of the space of polynomial solutions in O(sqrt(N) log^2 N) bit operations. In general, the integer N is not bounded polynomially in the bit size of the input differential equation. We isolate a class of equations for which detecting nonzero polynomial solutions can be performed in polynomial complexity. We discuss implementation issues and possible extensions.