Sparse polynomial interpolation with Bernstein polynomials

We present an algorithm for interpolating an unknown univariate polynomial f that has a t sparse representation ( t

PDF

___

[1] Prony R. Essai expérimental et analytique sur les lois de la Dilatabilité de fluides élastiques et sur celles de la Force expansive de la vapeur de l’eau et de la vapeur de l’alkool, à différentes températures. J. de l’École Polytechnique, 1795, (1):24–76 (in French).
[2] Ben-Or M, Tiwari P. A deterministic algorithm for sparse multivariate polynomial interpolation. ACM STOC ’88, 1988, 301–309.
[3] Brezinski B. History of continued fractions and Padé approximations. Heidelberg, Germany: Springer Verlag, 1991.
[4] Roche DS. Efficient computation with sparse and dense polynomials. PhD, University of Waterloo, Waterloo, ON, Canada, 2011.
[5] Arnold A. Sparse polynomial interpolation and testing. PhD, University of Waterloo, Waterloo, ON, Canada, 2016.
[6] Lakshman YN, Saunders BD. Sparse polynomial interpolation in non-standard bases. SIAM J. Comput., 1995, 24(2):387-397.
[7] Peter T, Plonka G, Rosca D. Representation of sparse Legendre expansions. Journal of Symbolic Computation, 2013, (50):159-169.
[8] Arnold A, Kaltofen EL. Error-correcting sparse interpolation in the Chebyshev basis. In: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC’15, 2015, 21-28.
[9] Potts D, Taschee M. Sparse polynomial interpolation in Chebyshev bases. Linear Algebra and its Applications, 2014, (441):61-87.
[10] Imamoglu E, Kaltofen EL, Yang Z. Sparse polynomial interpolation with arbitrary orthogonal polynomial bases. In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC’18, 2018, 223-230.
[11] Kaltofen, EL, Trager B. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 296-305. IEEE, 1988.
[12] Farouki, RT. The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design, 2012, 29(6):379-419.
[13] Farin G. Curves and surfaces for computer aided geometric design. Boston, MA, USA: Academic Press, 1993.
[14] Kaltofen EL, Lee W. Early termination in sparse interpolation algorithms. Journal of Symbolic Computation, 2003, 36(3):365-400.