Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the evaluation of some sparse polynomials

Authors: Dorian Nogneng and Éric Schost
Journal: Math. Comp. 87 (2018), 893-904
MSC (2010): Primary 68W30; Secondary 11Y16
Published electronically: September 7, 2017
MathSciNet review: 3739222
Full-text PDF

Abstract | References | Similar Articles | Additional Information


We give algorithms for the evaluation of sparse polynomials of the form \[ P=p_0 + p_1 x + p_2 x^4 + \cdots + p_{N-1} x^{(N-1)^2},\] for various choices of coefficients $p_i$. 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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 11Y16

Retrieve articles in all journals with MSC (2010): 68W30, 11Y16

Additional Information

Dorian Nogneng
Affiliation: LIX, Bâtiment Alan Turing, Campus de l’École Polytechnique, 91120 Palaiseau, France
MR Author ID: 1122361

Éric Schost
Affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
MR Author ID: 672551

Keywords: Sparse polynomials, evaluation
Received by editor(s): February 16, 2016
Received by editor(s) in revised form: February 23, 2016, and September 16, 2016
Published electronically: September 7, 2017
Article copyright: © Copyright 2017 American Mathematical Society