M2 internship proposal 2023–2024

Title: Sparse interpolation of rational functions

Topics: symbolic computation, high performance computing

Address

Director of the laboratory: Mr Gilles Schaeffer (schaeffe@lix.polytechnique.fr)

Research team: MAX, Algebraic modeling and symbolic computation

Contacts

Context

The MAX team is searching for PhD candidates on the themes of the ANR “NODE” project. The present M2 internship proposal allows applicants to familiarize themselves with these themes. Upon successful completion of the internship, there will be an opportunity to pursue with a PhD. The ANR NODE project provides funding for two PhD grants.

Description

Large-scale symbolic computations lead to the manipulation of very large mathematical expressions. Often, such expressions can be regarded as so-called sparse polynomials or rational functions in suitable variables. For instance, a sparse polynomial of degree in , , and is a polynomial , for which the number of non-zero terms is significantly lower than .

One typical motivating example of a sparse polynomial is the determinant of the symbolic matrix

Indeed, is a polynomial of degree in variables, with terms. The entries of the matrix inverse of are typical examples of sparse rational functions.

One notorious enemy in symbolic computation is intermediate expression swell. For instance, when computing symbolically, using Gaussian elimination, the intermediate expressions tend to become much larger than the final result. A magic way to defeat this enemy is sparse interpolation. The idea is to evaluate the determinant for a sufficient number of well chosen values of the variables and then to reconstruct from these evaluations.

The idea of sparse interpolation for polynomials goes back a long while [6, 1, 7]. Various methods have been proposed to generalize it to rational functions [5, 2]. Recently, particularly efficient methods for these tasks have been proposed [3, 4], but not yet implemented. The purpose of this internship is to learn and implement these new ideas and further improve them, if possible. If successful, then this may lead to significantly faster future implementations of many basic tasks in computer algebra.

Bibliography

[1]

M. Ben-Or and P. Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proc. ACM STOC '88, pages 301–309. New York, NY, USA, 1988.

[2]

A. Cuyt and W.-S. Lee. Sparse interpolation of multivariate rational functions. TCS, 412:1445–1456, 2011.

[3]

J. van der Hoeven and G. Lecerf. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. Technical Report, HAL, 2019. https://hal.archives-ouvertes.fr/hal-02382117.

[4]

J. van der Hoeven and G. Lecerf. On sparse interpolation of rational functions and gcds. ACM SIGSAM Commun. Comput. Algebra, 55(1):1–12, 2021.

[5]

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

[6]

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:24–76, 1795. Cahier 22.

[7]

D. S. Roche. What can (and can't) we do with sparse polynomials? In Proc. ISSAC '18, pages 25–30. New York, NY, USA, 2018. ACM.