Show simple item record

dc.contributor.authorSchost, Eric
dc.contributor.authorNogneng, Dorian
dc.contributor.authorNogneng, Dorian
dc.date.accessioned2023-03-21 19:03:04 (GMT)
dc.date.available2023-03-21 19:03:04 (GMT)
dc.date.issued2018
dc.identifier.urihttps://doi.org/10.1090/mcom/3231
dc.identifier.urihttp://hdl.handle.net/10012/19220
dc.description.abstractWe 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.isoenen
dc.publisherAmerican Mathematical Societyen
dc.relation.ispartofseriesMathematics of Computatation;
dc.subjectsparse polynomialsen
dc.subjectevaluationen
dc.titleOn the evaluation of some sparse polynomialsen
dc.typeArticleen
dcterms.bibliographicCitationNogneng, D., & Schost, É. (2017). On the evaluation of some sparse polynomials. Mathematics of Computation, 87(310), 893–904. https://doi.org/10.1090/mcom/3231en
uws.contributor.affiliation1Faculty of Mathematicsen
uws.contributor.affiliation2David R. Cheriton School of Computer Scienceen
uws.typeOfResourceTexten
uws.peerReviewStatusRevieweden
uws.scholarLevelFacultyen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record


UWSpace

University of Waterloo Library
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4883

All items in UWSpace are protected by copyright, with all rights reserved.

DSpace software

Service outages