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
DOI: https://doi.org/10.1090/mcom/3231
Published electronically: September 7, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give algorithms for the evaluation of sparse polynomials of the form

$\displaystyle 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
Email: dorian.nogneng@lix.polytechnique.fr

Éric Schost
Affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Email: eschost@uwaterloo.ca

DOI: https://doi.org/10.1090/mcom/3231
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

American Mathematical Society