  In 2012 Chen and Singer introduced the notion of discrete residues for
rational functions as a complete obstruction to rational summability. More
explicitly, for a given rational function f(x), there exists a rational
function g(x) such that f(x) = g(x+1) - g(x) if and only if every discrete
residue of f(x) is zero. Discrete residues have many important further
applications beyond summability: to creative telescoping problems, thence to
the determination of (differential-)algebraic relations among hypergeometric
sequences, and subsequently to the computation of (differential) Galois groups
of difference equations. However, the discrete residues of a rational function
are defined in terms of its complete partial fraction decomposition, which
makes their direct computation impractical due to the high complexity of
completely factoring arbitrary denominator polynomials into linear factors. We
develop a factorization-free algorithm to compute discrete residues of rational
functions, relying only on gcd computations and linear algebra.
