Polynomial and series solutions of linear operator equations

Many algorithms in computer algebra require finding polynomial solutions of linear operator equations. The straightforward method of undetermined coefficients reduces to solving linear systems with $N+1$ unknowns where $N$ is the degree of solutions and can be very time-consuming when $N$ is large. We show that by careful choice of basis the number of unknowns can be reduced to $r$ where $r$ denotes the order of the equation. In particular, we consider differential, difference, and $q$-difference equations. A typical example is computation of the $n$-th Legendre polynomial where {\em Maple}'s {\tt orthopoly} function cannot compete with our general-purpose algorithm. This is joint work with S.\ Abramov and M.\ Bronstein.