Abstract
In this manuscript we introduce three new algorithms: (1) An algorithm to recover an unknown polynomial in terms of Dickson polynomials of the first kind, (2) an algorithm to recover an unknown polynomial in terms Dickson polynomials of the second kind, (3) an algorithm to recover an unknown polynomial in terms of Bernstein basis polynomials, from given black boxes for the polynomial itself and its first derivative. In each algorithm, we assume that the unknown polynomial has a sparse representation in the corresponding basis. The methods presented use transformations from Dickson polynomials to Laurent polynomials, a transformation from Bernstein basis polynomials to Laurent polynomials, and a recently developed algorithm as a middle step.
Keywords
Hermite İnterpolasyonu Seyrek Polinomlar Dickson Polinomları Bernstein Baz Polinomları Algoritmalar
References
- [1] Von Zur Gathen J, Gerhard J. Modern computer algebra. Cambridge university press, 2013.
- [2] Kaltofen EL. Sparse polynomial Hermite interpolation. In: ISSAC 2022 The International Symposium on Symbolic and Algebraic Computation Conference; 4-7 July 2022; Lille, France: ACM ISSAC’22, 469-478.
- [3] Prony R. Essai experimental et analytique: sur les lois de la dilatabilite des fluides elastique et sur celles de la force expansive de la vapeur de l'eau et de la vapeur de l'alkool, a differentes temperatures. J. de l’Ecole Polytechnique, 1795; (1):24-76.
- [4] Ben-Or M, Tiwari P. A deterministic algorithm for sparse multivariate polynomial interpolation. In: The twentieth annual ACM Symposium on Theory of Computing; 1988 New York, USA; 301-309.
- [5] Kaltofen E, Trager B.M. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation 1990; 9(3), 301-320.
- [6] Dickson LE. The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Ann Math 1896; 1; 6, 65-120.
- [7] Lindl R. Theory and applications of Dickson polynomials. World Scientific, 1991.
- [8] Lindl R, Niederreiter H. Finite fields. Cambridge University Press, 1997.
- [9] Mullen GL, Panario D. Handbook of finite fields. CRC Press. 2013.
- [10] Farouki RT. The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design 2012; 29(6), 379-419.
- [11] Farin G. Curves and surfaces for computer aided geometric design. Academic Press, 1993.
- [12] Imamoglu E, Kaltofen EL. A note on sparse polynomial interpolation in Dickson polynomial basis. ACM Communications in Computer Algebra 2020; 54(4), 125-128.
- [13] Imamoglu E. Sparse polynomial interpolation with Bernstein polynomials. Turkish Journal of Mathematics 2021; 45(5), 2103-2107.
Abstract
In this manuscript we introduce three new algorithms: (1) An algorithm to recover an unknown polynomial in terms of Dickson polynomials of the first kind, (2) an algorithm to recover an unknown polynomial in terms Dickson polynomials of the second kind, (3) an algorithm to recover an unknown polynomial in terms of Bernstein basis polynomials, from given black boxes for the polynomial itself and its first derivative. In each algorithm, we assume that the unknown polynomial has a sparse representation in the corresponding basis. The methods presented use transformations from Dickson polynomials to Laurent polynomials, a transformation from Bernstein basis polynomials to Laurent polynomials, and a recently developed algorithm as a middle step.
Keywords
Hermite Interpolation Sparse Polynomials Dickson Polynomials Bernstein Basis Polynomials Algorithms
References
- [1] Von Zur Gathen J, Gerhard J. Modern computer algebra. Cambridge university press, 2013.
- [2] Kaltofen EL. Sparse polynomial Hermite interpolation. In: ISSAC 2022 The International Symposium on Symbolic and Algebraic Computation Conference; 4-7 July 2022; Lille, France: ACM ISSAC’22, 469-478.
- [3] Prony R. Essai experimental et analytique: sur les lois de la dilatabilite des fluides elastique et sur celles de la force expansive de la vapeur de l'eau et de la vapeur de l'alkool, a differentes temperatures. J. de l’Ecole Polytechnique, 1795; (1):24-76.
- [4] Ben-Or M, Tiwari P. A deterministic algorithm for sparse multivariate polynomial interpolation. In: The twentieth annual ACM Symposium on Theory of Computing; 1988 New York, USA; 301-309.
- [5] Kaltofen E, Trager B.M. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation 1990; 9(3), 301-320.
- [6] Dickson LE. The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Ann Math 1896; 1; 6, 65-120.
- [7] Lindl R. Theory and applications of Dickson polynomials. World Scientific, 1991.
- [8] Lindl R, Niederreiter H. Finite fields. Cambridge University Press, 1997.
- [9] Mullen GL, Panario D. Handbook of finite fields. CRC Press. 2013.
- [10] Farouki RT. The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design 2012; 29(6), 379-419.
- [11] Farin G. Curves and surfaces for computer aided geometric design. Academic Press, 1993.
- [12] Imamoglu E, Kaltofen EL. A note on sparse polynomial interpolation in Dickson polynomial basis. ACM Communications in Computer Algebra 2020; 54(4), 125-128.
- [13] Imamoglu E. Sparse polynomial interpolation with Bernstein polynomials. Turkish Journal of Mathematics 2021; 45(5), 2103-2107.
Details
| Primary Language | English |
|---|---|
| Subjects | Algebra and Number Theory |
| Journal Section | Articles |
| Authors | |
| Publication Date | August 28, 2023 |
| Published in Issue | Year 2023 Volume: 11 Issue: 2 |