Title: Sparse interpolation of rational functions

Topics: symbolic computation, high performance computing

Address

Research team: MAX, Algebraic modeling and symbolic computation

Contacts

Context

The MAX team is searching for PhD candidates on the themes of the “ODELIX” ERC Advanced Grant. 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.

Applying

Applications can be sent by email to the above contact persons; they should include a CV, a transcript of records, a letter of motivation, and optional recommendation letters. Note that we have no hard deadlines; new applications will be considered at any time of the year, as long as the Odelix project runs.

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.