Diversification improves interpolation

Details Diversification improves interpolation Diversification improves interpolation

2011-01-19

arxiv.org/abs/1101.3682v3

Computer Science

Symbolic Computation

26 pages, pdfLaTeX. Preliminary version to appear at ISSAC 2011

Scientific paper

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 polynomials with complex coefficients, and provide the first provably stable algorithm (in the sense of relative error) for this problem, at the cost of modestly more evaluations. 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 from most previous approaches is that our algorithms do not rely on root finding as a subroutine. We show how these improvements affect the practical performance with trial implementations.

Affiliated with

Also associated with

No associations

Rating

Diversification improves interpolation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Diversification improves interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diversification improves interpolation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156584