Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
share
Suppose 𝕂 is a large enough field and 𝒫⊂𝕂^2 is a fixed, generic set of points which is available for precomputation. We introduce a technique called reshaping which allows us to design quasi-linear algorithms for both: computing the evaluations of an input polynomial f ∈𝕂[x,y] at all points of 𝒫; and computing an interpolant f ∈𝕂[x,y] which takes prescribed values on 𝒫 and satisfies an input y-degree bound. Our genericity assumption is explicit and we prove that it holds for most point sets over a large enough field. If 𝒫 violates the assumption, our algorithms still work and the performance degrades smoothly according to a distance from being generic. To show that the reshaping technique may have an impact on other related problems, we apply it to modular composition: suppose generic polynomials M ∈𝕂[x] and A ∈𝕂[x] are available for precomputation, then given an input f ∈𝕂[x,y] we show how to compute f(x, A(x)) rem M(x) in quasi-linear time.
READ FULL TEXT