nach oben

Applicable Algebra in Engineering, Communication and Computing

27.04.2024 | Original Paper

Sparse polynomial interpolation: faster strategies over finite fields

verfasst von: Joris van der Hoeven, Grégoire Lecerf

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Consider a multivariate polynomial \(f \in K [x_1, \ldots , x_n]\) over a field K, which is given through a black box capable of evaluating f at points in \(K^n\), or possibly at points in \(A^n\) for any K-algebra A. The problem of sparse interpolation is to express f in its usual form with respect to the monomial basis. We analyze the complexity of various old and new algorithms for this task in terms of bounds D and T for the total degree of f and its number of terms. We mainly focus on the case when K is a finite field and explore possible speed-ups.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781–793 (2004)MathSciNetCrossRef

Arnold, A., Giesbrecht, M., Roche, D.S.: Sparse interpolation over finite fields via low-order roots of unity. In ISSAC ’14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp 27–34. ACM Press, (2014)

Arnold, A., Giesbrecht, M., Roche, D.S.: Faster sparse multivariate polynomial interpolation of straight-line programs. J. Symb. Comput. 75, 4–24 (2016)MathSciNetCrossRef

Arnold, A., Roche, D.S.: Multivariate sparse interpolation using randomized Kronecker substitutions. In ISSAC ’14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp 35–42. ACM Press, (2014)

Arratia, R., Gordon, L.: Tutorial on large deviations for the binomial distribution. Bull. Math. Biol. 51(1), 125–131 (1989)MathSciNetCrossRef

Baker, R.C., Harman, G., Pintz, J.: The difference between consecutive primes, II. Proc. London Math. Soc. 83(3), 532–562 (2001)MathSciNetCrossRef

Baur, W., Strassen, V.: The complexity of partial derivatives. Theor. Comput. Sci. 22, 317–330 (1983)MathSciNetCrossRef

Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In STOC ’88: Proceedings of the Twentieth AAnnual ACM Symposium on Theory of Computing, pp 301–309. ACM Press (1988)

Bennett, M.A., Martin, G., O’Bryant, K., Rechnitzer, A.: Explicit bounds for primes in arithmetic progressions. Illinois J. Math. 62(1–4), 427–532 (2018)MathSciNet

10.

Bostan, A., Lecerf, G., Schost, É.: Tellegen’s principle into practice. In: ISSAC ’03: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pp 37–44. ACM Press, (2003)

11.

Brent, R.P., Gustavson, F.G., Yun, D.Y.Y.: Fast solution of Toeplitz systems of equations and computation of Padé approximants. J. Algor. 1(3), 259–295 (1980)CrossRef

12.

Canny, J., Kaltofen, E., Lakshman, Y.: Solving systems of non-linear polynomial equations faster. In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, pp 121–128. ACM Press, (1989)

13.

Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587–592 (1981)MathSciNetCrossRef

14.

Díaz, A., Kaltofen, E.: FOXFOX: a system for manipulating symbolic objects in black box representation. In ISSAC ’98: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, pp 30–37. ACM Press, (1998)

15.

Ernvall-Hytönen, A.-M., Palojärvi, N.: Explicit bound for the number of primes in arithmetic progressions assuming the Generalized Riemann Hypothesis. Math. Comput. 91, 1317–1365 (2022)MathSciNet

16.

Freeman, T.S., Imirzian, G.M., Kaltofen, E., Lakshman, Y.: DAGWOOD: a system for manipulating polynomials given by straight-line programs. ACM Trans. Math. Softw. 14, 218–240 (1988)CrossRef

17.

Garg, S., Schost, É.: Interpolation of polynomials given by straight-line programs. Theor. Comput. Sci. 410(27–29), 2659–2662 (2009)MathSciNetCrossRef

18.

Giesbrecht, M., Roche, D.S.: Diversification improves interpolation. In ISSAC ’11: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp 123–130. ACM Press, (2011)

19.

Giorgi, P., Grenet, B., Perret du Cray, A.: Essentially optimal sparse polynomial multiplication. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ISSAC ’20, pp 202–209. New York, NY, USA, 2020. ACM Press

20.

Giorgi, P., Grenet, B., Perret du Cray, A., Roche, D.S.: Random primes in arithmetic progressions. Techn. Rep. (2022) arXiv:2202.05955

21.

Giorgi, P., Grenet, B. Perret du Cray, A., Roche, D.S.: Sparse polynomial interpolation and division in soft-linear time. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pp 459–468. New York, NY, USA, 2022. ACM Press

22.

Grenet, B., van der Hoeven, J., Lecerf, G.: Randomized root finding over finite fields using tangent Graeffe transforms. In ISSAC ’15: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, pp 197–204. New York, NY, USA, 2015. ACM Press

23.

Grenet, B., van der Hoeven, J., Lecerf, G.: Deterministic root finding over finite fields using Graeffe transforms. Appl. Algebra Engrg. Comm. Comput. 27(3), 237–257 (2016)MathSciNetCrossRef

24.

Grigoriev, D.Y., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pp 166–172. IEEE Computer Society, (1987)

25.

Harvey, D., van der Hoeven, J.: Polynomial multiplication over finite fields in time \(O (n \log n)\). J. ACM 69(2), 1–40 (2022)CrossRef

26.

Harvey, D., van der Hoeven, J., Lecerf, G.: Faster polynomial multiplication over finite fields. J. ACM 63(6), 52 (2017)MathSciNetCrossRef

27.

Heintz, J., Schnorr, C.P.: Testing polynomials which are easy to compute. In Logic and algorithmic (Zurich, 1980), volume 30 of Monograph. Enseign. Math., pages 237–254. Geneva, 1982. Univ. Genève

28.

van der Hoeven, J., Larrieu, R.: The Frobenius FFT. In ISSAC ’17: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 437–444. New York, NY, USA, 2017. ACM Press

29.

J. van der Hoeven, R. Lebreton, and É. Schost. Structured FFT and TFT: symmetric and lattice polynomials. In ISSAC ’13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pages 355–362. New York, NY, USA, 2013. ACM Press

30.

van der Hoeven, J., Lecerf, G.: On the bit-complexity of sparse polynomial and series multiplication. J. Symb. Comput. 50, 227–254 (2013)MathSciNetCrossRef

31.

van der Hoeven, J., Lecerf, G.: Sparse polynomial interpolation in practice. ACM Commun. Comput. Algebra 48(3/4), 187–191 (2015)CrossRef

32.

J. van der Hoeven and G. Lecerf. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. Techn. Rep. HAL, (2019). https://hal.science/hal-02382117v1

33.

J. Hu and M. B. Monagan. A fast parallel sparse polynomial GCD algorithm. In S. A. Abramov, E. V. Zima, and X.-S. Gao, editors, ISSAC ’16: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp 271–278. New York, NY, USA, 2016. ACM Press

34.

Huang, M.A., Rao, A.J.: Interpolation of sparse multivariate polynomials over large finite fields with applications. In SODA ’96: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 508–517. Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics

35.

Huang, M.-D.A., Rao, A.J.: Interpolation of sparse multivariate polynomials over large finite fields with applications. J. Algor. 33(2), 204–228 (1999)MathSciNetCrossRef

36.

Huang, Q.L., Gao, X.S.: Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients. In V. Gerdt, V. Koepf, W. Seiler, and E. Vorozhtsov, editors, Computer Algebra in Scientific Computing. 19th International Workshop, CASC 2017, Beijing, China, September 18-22, 2017, Proceedings., volume 10490 of Lect. Notes Comput. Sci. Springer, Cham, (2017)

37.

Q.-L. Huang. Sparse polynomial interpolation over fields with large or zero characteristic. In ISSAC ’19: Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, pp 219–226. New York, NY, USA, 2019. ACM Press

38.

Huang, Q.L., Gao, X.S.: Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs. J. Symb. Comput. 101, 367–386 (2020)MathSciNetCrossRef

39.

Javadi, M., Monagan, M.: Parallel sparse polynomial interpolation over finite fields. In M. Moreno Maza and J.-L. Roch, editors, PASCO ’10: Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, pp 160–168. New York, NY, USA, 2010. ACM Press

40.

Kaltofen, E.: Computing with polynomials given by straight-line programs I: greatest common divisors. In STOC ’85: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp 131–142. ACM Press, (1985)

41.

E. L. Kaltofen. Fifteen years after DSC and WLSS2 what parallel computations I do today: invited lecture at PASCO 2010. In PASCO ’10: Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, pp 10–17. ACM Press, 2010

42.

E. Kaltofen, Y. N. Lakshman, and J.-M. Wiley. Modular rational sparse multivariate polynomial interpolation. In ISSAC ’90: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp 135–139. New York, NY, USA, 1990. ACM Press

43.

Kaltofen, E., Lee, W.: Early termination in sparse interpolation algorithms. J. Symb. Comput. 36(3), 365–400 (2003)MathSciNetCrossRef

44.

Kaltofen, E., Trager, B.M.: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comput. 9(3), 301–320 (1990)MathSciNetCrossRef

45.

Kaltofen, E., Yagati, L.: Improved sparse multivariate polynomial interpolation algorithms. In ISSAC ’88: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp 467–474. Springer Verlag, (1988)

46.

R. Moenck. Fast computation of gcds. In Proc. of the 5th ACM Annual Symposium on Theory of Computing, pp 142–171. New York, 1973. ACM Press

47.

Murao, H., Fujise, T.: Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation. J. Symb. Comput. 21, 377–396 (1996)MathSciNetCrossRef

48.

Okamoto, M.: Some inequalities relating to the partial sum of binomial probabilities. Ann. Inst. Stat. Math. 10(1), 29–35 (1959)MathSciNetCrossRef

49.

A. Perret du Cray. Algorithmes pour les polynômes creux : interpolation, arithmétique, test d’identité. PhD thesis, Université de Montpellier (France), 2023

50.

R. Prony. Essai expérimental et analytique sur les lois de la dilatabilité des 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 Floréal et Plairial, an III, 1(cahier 22):24–76, 1795

51.

Risler, J.-J., Ronga, F.: Testing polynomials. J. Symb. Comput. 10(1), 1–5 (1990)MathSciNetCrossRef

52.

D. S. Roche. What can (and can’t) we do with sparse polynomials? In C. Arreche, editor, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18, pages 25–30. New York, NY, USA, 2018. ACM Press

53.

Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inform. 7, 395–398 (1977)MathSciNetCrossRef

54.

A. Sedunova. A partial Bombieri–Vinogradov theorem with explicit constants. Publications mathématiques de Besançon. Algèbre et théorie des nombres, pp 101–110, 2018

55.

R. Zippel. Probabilistic algorithms for sparse polynomials. In E. W. Ng, editor, Symbolic and Algebraic Computation. Eurosam ’79, An International Symposium on Symbolic and Algebraic Manipulation, Marseille, France, June 1979, vol 72 of Lect. Notes Comput. Sci., pp 216–226. Springer-Verlag, (1979)

Titel: Sparse polynomial interpolation: faster strategies over finite fields
verfasst von: Joris van der Hoeven
Grégoire Lecerf
Publikationsdatum: 27.04.2024
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-024-00655-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"