What is/are the lower bounds for finding a something akin to complex residue?
So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N). I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better. I imagine that a bounds related to the length of the function description may be possible...


There are different measures of polynomial sparseness in the literature and you haven't been very clear on which one you might mean. However, your optimism is likely not well founded. 

Take (x-2) / x^32. It's almost maximally sparse by any reasonable measure, but the coefficients in its Laurent series grow exponentially fast. If multiplication is unit cost you can still use the binary exponentiation method to keep up with the exponential growth in sublinear time in the total degree of the series, but the example suggests that things aren't rosy. This is an area littered with hardness results for division and related problems, at least in realistic models of computation where multiplication isn't constant time.

Jacques Carette is an expert in this area, so let's hope he posts a definitive answer.