## On the evaluation of some sparse polynomials

HTML articles powered by AMS MathViewer

- by Dorian Nogneng and Éric Schost PDF
- Math. Comp.
**87**(2018), 893-904 Request permission

## Abstract:

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

- Tom M. Apostol,
*Introduction to analytic number theory*, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR**0434929** - A. Arnold, M. Giesbrecht, and D. S. Roche,
*Faster sparse interpolation of straight-line programs*, CASC 2013, Springer, 2013, pp. 61–74. - 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**, DOI 10.1145/2608628.2608671 - Richard Bellman,
*A brief introduction to theta functions*, Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1961. MR**0125252**, DOI 10.1017/s0025557200044491 - M. Ben-Or and P. Tiwari,
*A deterministic algorithm for sparse multivariate polynomial interpolation*, STOC’88, ACM, 1988, pp. 301–309. - 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. - 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. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR**877728** - J. Canny, E. Kaltofen, and Y. Lakshman,
*Solving systems of non-linear polynomial equations faster*, ISSAC’89, ACM, 1989, pp. 121–128. - David G. Cantor and Erich Kaltofen,
*On fast multiplication of polynomials over arbitrary algebras*, Acta Inform.**28**(1991), no. 7, 693–701. MR**1129288**, DOI 10.1007/BF01178683 - Régis Dupont,
*Fast evaluation of modular functions using Newton iterations and the AGM*, Math. Comp.**80**(2011), no. 275, 1823–1847. MR**2785482**, DOI 10.1090/S0025-5718-2011-01880-6 - Andreas Enge,
*The complexity of class polynomial computation via floating point approximations*, Math. Comp.**78**(2009), no. 266, 1089–1107. MR**2476572**, DOI 10.1090/S0025-5718-08-02200-X - 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**, DOI 10.1016/j.tcs.2009.03.030 - Joachim von zur Gathen and Jürgen Gerhard,
*Modern computer algebra*, 2nd ed., Cambridge University Press, Cambridge, 2003. MR**2001757** - 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**, DOI 10.1145/1993886.1993909 - W. B. Hart,
*Fast library for number theory: An introduction*, ICMS’10 (Berlin, Heidelberg), Springer-Verlag, 2010, http://flintlib.org, pp. 88–91. - Ghaith Ayesh Hiary,
*Fast methods to compute the Riemann zeta function*, Ann. of Math. (2)**174**(2011), no. 2, 891–946. MR**2831110**, DOI 10.4007/annals.2011.174.2.4 - 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**, DOI 10.4007/annals.2011.174.2.3 - F. Johansson,
*Arb: a C library for ball arithmetic*, ACM Communications in Computer Algebra**47**(2013), no. 4, 166–169. - 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**, DOI 10.1007/3-540-51084-2_{4}4 - Erich Kaltofen and Wen-shin Lee,
*Early termination in sparse interpolation algorithms*, J. Symbolic Comput.**36**(2003), no. 3-4, 365–400. International Symposium on Symbolic and Algebraic Computation (ISSAC’2002) (Lille). MR**2004034**, DOI 10.1016/S0747-7171(03)00088-9 - H. Labrande,
*Computing Jacobi’s $\theta$ in quasi-linear time*, https://hal.inria.fr/hal-01227699, 2015. - 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**, DOI 10.1145/2608628.2608664 - D. Mumford,
*Tata Lectures on Theta, 1*, Modern Birkhauser Classics, Springer, 2007. - 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** - V. Ja. Pan,
*On means of calculating values of polynomials*, Uspehi Mat. Nauk**21**(1966), no. 1 (127), 103–134 (Russian). MR**0207178** - Terence Tao, Ernest Croot III, and Harald Helfgott,
*Deterministic methods to find primes*, Math. Comp.**81**(2012), no. 278, 1233–1246. MR**2869058**, DOI 10.1090/S0025-5718-2011-02542-1 - Richard Zippel,
*Interpolating polynomials from their values*, J. Symbolic Comput.**9**(1990), no. 3, 375–403. MR**1056633**, DOI 10.1016/S0747-7171(08)80018-1

## Additional Information

**Dorian Nogneng**- Affiliation: LIX, Bâtiment Alan Turing, Campus de l’École Polytechnique, 91120 Palaiseau, France
- MR Author ID: 1122361
- Email: dorian.nogneng@lix.polytechnique.fr
**Éric Schost**- Affiliation: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
- MR Author ID: 672551
- Email: eschost@uwaterloo.ca
- 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
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp.
**87**(2018), 893-904 - MSC (2010): Primary 68W30; Secondary 11Y16
- DOI: https://doi.org/10.1090/mcom/3231
- MathSciNet review: 3739222