Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 


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
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?)

  • [1] Tom M. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
  • [2] A. Arnold, M. Giesbrecht, and D. S. Roche, Faster sparse interpolation of straight-line programs, CASC 2013, Springer, 2013, pp. 61-74.
  • [3] Andrew Arnold, Mark Giesbrecht, and Daniel S. Roche, Sparse interpolation over finite fields via low-order roots of unity, ISSAC 2014--Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 27-34. MR 3239905,
  • [4] Richard Bellman, A Brief Introduction to Theta Functions, Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1961. MR 0125252
  • [5] M. Ben-Or and P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, STOC'88, ACM, 1988, pp. 301-309.
  • [6] L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics AU-18 (1970), 451-455.
  • [7] Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1987. MR 877728
  • [8] J. Canny, E. Kaltofen, and Y. Lakshman, Solving systems of non-linear polynomial equations faster, ISSAC'89, ACM, 1989, pp. 121-128.
  • [9] David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693-701. MR 1129288,
  • [10] Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, Math. Comp. 80 (2011), no. 275, 1823-1847. MR 2785482,
  • [11] Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089-1107. MR 2476572,
  • [12] Sanchit Garg and Éric Schost, Interpolation of polynomials given by straight-line programs, Theoret. Comput. Sci. 410 (2009), no. 27-29, 2659-2662. MR 2531108,
  • [13] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
  • [14] Mark Giesbrecht and Daniel S. Roche, Diversification improves interpolation, ISSAC 2011--Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2011, pp. 123-130. MR 2895203,
  • [15] W. B. Hart, Fast library for number theory: An introduction, ICMS'10 (Berlin, Heidelberg), Springer-Verlag, 2010,, pp. 88-91.
  • [16] Ghaith Ayesh Hiary, Fast methods to compute the Riemann zeta function, Ann. of Math. (2) 174 (2011), no. 2, 891-946. MR 2831110,
  • [17] Ghaith Ayesh Hiary, A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals, Ann. of Math. (2) 174 (2011), no. 2, 859-889. MR 2831109,
  • [18] F. Johansson, Arb: a C library for ball arithmetic, ACM Communications in Computer Algebra 47 (2013), no. 4, 166-169.
  • [19] Erich Kaltofen and Lakshman Yagati, Improved sparse multivariate polynomial interpolation algorithms, Symbolic and algebraic computation (Rome, 1988) Lecture Notes in Comput. Sci., vol. 358, Springer, Berlin, 1989, pp. 467-474. MR 1034749,
  • [20] Erich Kaltofen and Wen-shin Lee, Early termination in sparse interpolation algorithms, J. Symbolic Comput. 36 (2003), no. 3-4, 365-400. MR 2004034,
  • [21] H. Labrande, Computing Jacobi's $ \theta $ in quasi-linear time,, 2015.
  • [22] François Le Gall, Powers of tensors and fast matrix multiplication, ISSAC 2014--Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296-303. MR 3239939,
  • [23] D. Mumford, Tata Lectures on Theta, 1, Modern Birkhauser Classics, Springer, 2007.
  • [24] A. Ostrowski, On two problems in abstract algebra connected with Horner's rule, Studies in mathematics and mechanics presented to Richard von Mises, Academic Press Inc., New York, 1954, pp. 40-48. MR 0066030
  • [25] V. Ja. Pan, On means of calculating values of polynomials, Uspehi Mat. Nauk 21 (1966), no. 1 (127), 103-134 (Russian). MR 0207178
  • [26] Terence Tao, Ernest Croot III, and Harald Helfgott, Deterministic methods to find primes, Math. Comp. 81 (2012), no. 278, 1233-1246. MR 2869058,
  • [27] Richard Zippel, Interpolating polynomials from their values, J. Symbolic Comput. 9 (1990), no. 3, 375-403. MR 1056633,

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

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

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