Alladi Ramakrishnan Hall

Fast Numerical Multivariate Multipoint Evaluation

Prahladh Harsha

TIFR

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of evaluation inputs. A straightforward algorithm for this problem is to just iteratively evaluate the polynomial at each of the inputs. The question of obtaining faster-than-naive (and ideally, close to linear time) algorithms for this problem is a natural and basic question in computational algebra.

The classical FFT algorithm gives such an algorithm for the special case of univariate polynomials and a well-structured set of evaluation points (say roots of unity). Only as recently as last year, was the multivariate version of this problem for all sets of evaluation points resolved for finite fields due to the works of Bhargava, Ghosh, Guo, Kumar & Umans.

The case of infinite fields (eg, reals, rationals) is complicated due to subtleties arising from the bit-complexity of the output compelling one to work with either an approximate version of the problem or an exact version where the algorithm is allowed to run in time nearly-linear in the output size. Only as recently as 2021, was the univariate version of this problem over infinite fields resolved by Moroz.

In this talk, we will show how to extend these results to obtain similar nearly-linear time results for the multivariate version of the problem over infinite fields such as rationals, reals both in the approximate and exact setting.

[Joint work with Sumanta Ghosh, Simao Herdade, Mrinal Kumar and Ramprasad Saptharishi]