dc.contributor.author | Schost, Eric | |
dc.contributor.author | Nogneng, Dorian | |
dc.contributor.author | Nogneng, Dorian | |
dc.date.accessioned | 2023-03-21 19:03:04 (GMT) | |
dc.date.available | 2023-03-21 19:03:04 (GMT) | |
dc.date.issued | 2018 | |
dc.identifier.uri | https://doi.org/10.1090/mcom/3231 | |
dc.identifier.uri | http://hdl.handle.net/10012/19220 | |
dc.description.abstract | We give algorithms for the evaluation of sparse polynomials of the form P=p0 + p1 x + p2 x^4 + ... + p_{n-1} x^{(N-1)^2}
for various choices of coefficients . First, we take p_i=p^i, for some fixed p; in this case, we address the question of fast evaluation at a given point in the base ring, and we obtain a cost quasi-linear in sqrt{N}. We present experimental results that show the good behavior of this algorithm in a floating-point context, for the computation of Jacobi theta functions.
Next, we consider the case of arbitrary coefficients; for this problem, we study the question of multiple evaluation: we show that one can evaluate such a polynomial at N values in the base ring in subquadratic time. | en |
dc.language.iso | en | en |
dc.publisher | American Mathematical Society | en |
dc.relation.ispartofseries | Mathematics of Computatation; | |
dc.subject | sparse polynomials | en |
dc.subject | evaluation | en |
dc.title | On the evaluation of some sparse polynomials | en |
dc.type | Article | en |
dcterms.bibliographicCitation | Nogneng, D., & Schost, É. (2017). On the evaluation of some sparse polynomials. Mathematics of Computation, 87(310), 893–904. https://doi.org/10.1090/mcom/3231 | en |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.contributor.affiliation2 | David R. Cheriton School of Computer Science | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Reviewed | en |
uws.scholarLevel | Faculty | en |