Algorithms for sparse rational interpolation
Dima Yu. Grigoriev, Marek Karpiński · 1991
We present two algorithms for interpolating sparse rational functions.The first is the interpolation algorithm in a sense of sparse partial fraction representation of rational functions.The second is the algorithm for computing the entier and the remainder of a rational function.The first algorithm works without apriori known bound on the degree of a rational function, the second one is in the parallel class NC provided that the degree is known.The presented algorithms complement the sparse interpolation results of [GKS 90].