search

flintlib / flint

FLINT (Fast Library for Number Theory)
http://www.flintlib.org
GNU Lesser General Public License v3.0
404 stars 236 forks source link

Polynomial evaluation at geometric sequences #1904

Open sumiya11 opened 3 months ago

sumiya11 commented 3 months ago

Hi,

Does Flint have multi-point evaluation of multivariate polynomials at geometric sequences over finite fields ?

For example, something like the matrix-vector product with a transposed Vandermonde matrix from section 3a in https://dl.acm.org/doi/10.1145/74540.74556.

Unless I am missing something, I have only seen functions for evaluating at one point at a time.

Also, is there linear system solving with a (transposed) Vandermonde matrix in Flint ?

Thanks.

fredrik-johansson commented 3 months ago

No, there's no multivariate multipoint evaluation AFAIK.

There's something for unvariate geometric sequences in PML (https://github.com/vneiger/pml/tree/master/flint-extras/nmod_poly_extra/src) that we ought to merge. There's also standard univariate multipoint evaluation in FLINT, but of course that's log(n) slower than something specialized for geometric sequences.