@inproceedings{6ef300a6c9d64db39bdbc70ea944b8be,

title = "Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation",

abstract = "Suppose K is a large enough field and P ⊂ K2 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 ∈ K [x, y] at all points of P and computing an interpolant f ∈ K[x, y] which takes prescribed values on P 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 P 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 ∈ K[x] and A ∈ K[x] are available for precomputation, then given an input f ∈ K[x, y] we show how to compute f (x, A(x)) rem M(x) in quasi-linear time.",

keywords = "Bivariate polynomials, Interpolation, Modular composition, Multi-point evaluation, Precomputation",

author = "Vincent Neiger and Johan Rosenkilde and Grigory Solomatov",

year = "2020",

month = jul,

day = "20",

doi = "10.1145/3373207.3404032",

language = "English",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

pages = "388--395",

editor = "Angelos Mantzaflaris",

booktitle = "Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation",

publisher = "Association for Computing Machinery",

address = "United States",

note = "45<sup>th</sup> International Symposium on Symbolic and Algebraic Computation, ISSAC 2020 ; Conference date: 20-07-2020 Through 23-07-2020",

}