Mark Giesbrecht and Daniel S. Roche
We consider the problem of interpolating an unknown multivariate polynomial with coefficients taken from a finite field or as numerical approximations of complex numbers. Building on the recent work of Garg and Schost, we improve on the best-known algorithm for interpolation over large finite fields by presenting a Las Vegas randomized algorithm that uses fewer black box evaluations. Using related techniques, we also address numerical interpolation of sparse complex polynomials, and provide the first provably stable algorithm (in the sense of relative error) for this problem, at the cost of modestly more interpolation points. A key new technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing what we call a diverse polynomial. Another departure of our algorithms from most previous approaches is that they do not rely on root finding as a subroutine. We show how these improvements affect the practical performance with trial implementations.
We implemented our algorithms over finite fields and over approximations to complex numbers. The software is released under a MIT-style license and is available from the links below.