Fast amortized multi-point evaluation

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper,...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2021-12, Vol.67, p.101574, Article 101574
Main Authors: van der Hoeven, Joris, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Algorithm
Complexity
Computational Complexity
Computer algebra
Computer Science
Evaluation
Interpolation
Mathematical Software
Multivariate polynomial
Symbolic Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and “sufficiently generic”. Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2021.101574