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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the 45th International Symposium on Symbolic and Algebraic Computation
EditorsAngelos Mantzaflaris
PublisherAssociation for Computing Machinery
Publication date20 Jul 2020
Pages388-395
ISBN (Electronic)9781450371001
DOIs
Publication statusPublished - 20 Jul 2020
Event45th International Symposium on Symbolic and Algebraic Computation - Virtual event, Kalamata, Greece
Duration: 20 Jul 202023 Jul 2020

Conference

Conference45th International Symposium on Symbolic and Algebraic Computation
LocationVirtual event
CountryGreece
CityKalamata
Period20/07/202023/07/2020
SponsorATHENA Research and Innovation Center, Computer Algebra Research Group, Wilfrid Laurier University, Fachgruppe Computer Algebra, MapleSoft, National and Kapodistrian University of Athens, National Institute for Research in Digital Science and Technology
SeriesProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Keywords

  • Bivariate polynomials
  • Interpolation
  • Modular composition
  • Multi-point evaluation
  • Precomputation

Fingerprint Dive into the research topics of 'Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation'. Together they form a unique fingerprint.

Cite this