English | Français
The MAX computer algebra seminar
Home | People | Software | Seminar | ANR NODE

The MAX seminar takes place in the Alan Turing building at the campus of École polytechnique. Click here for more information on how to join us.

Upcoming talks

2024, June 10

Guillaume Chèze (Institut de Mathématiques de Toulouse)

Partage de gâteaux sans-envie: une grande probabilité d'avoir un nombre de requêtes polynomial

Time: from 11h00 to 12h00

Room: Emmy Noether

Le problème du partage d'un gâteau entre convives consiste à effectuer un découpage afin que chaque convive reçoive sa «juste» part. Les convives peuvent avoir des goûts différents et le gâteau peut avoir plusieurs saveurs (chocolat, vanille, fraise, etc.). Dans cet exposé, nous allons présenter comment le problème du partage d'un gâteau peut être modélisé et quel modèle de calcul est utilisé pour étudier la complexité des algorithmes. Nous verrons aussi qu'il existe différentes notions de «juste part». Ensuite, nous verrons qu'il existe un algorithme qui évite la jalousie entre les convives et qui possède la qualité suivante: lorsque nous considérons des convives «au hasard» alors la probabilité de leur poser beaucoup de questions pour effectuer le partage est petite.

Past talks

2024, May 27 (Postponed until the Fall)

Vincent Neiger (Sorbonne University)

Faster modular composition of polynomials

Time: from 11h00 to 12h00

Room: Grace Hopper

This talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials and over a commutative field, modular composition asks to compute for some given , while the minimal polynomial problem is to compute of minimal degree such that . We propose algorithms whose complexity bound improves upon previous algorithms and in particular upon Brent and Kung's approach (1978); the new complexity bound is subquadratic in the degree of and even when using cubic-time matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals, and from efficient operations with these bases thanks to fast univariate polynomial matrix algorithms. We will also report on experimental results using the Polynomial Matrix Library.

Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard.

The corresponding article may be found here or here.

2024, April 29

Antoine Etesse (ENS Lyon)

On the structure of differentially homogeneous polynomials

Time: from 11h00 to 12h00

Room: Grace Hopper

The goal of the talk is to discuss the structure of differentially homogeneous polynomials in variables, and its interpretation. We will mainly talk about the structure of vector space: it is a graded algebra, whose -th graded component has dimension . This was predicted by the so-called Schmidt-Kolchin conjecture. We will also (briefly) talk about the expected structure as an algebra: it is an ongoing work, being finalized.

2024, April 22

Raphaël Pagès

Factoring differential operators in positive characteristic through geometric means

Time: from 15h30 to 16h30

Room: Henri Poincaré

We focus on the porblem of factoring a given linear differential operator, whose coefficients are elements of an algebraic function field of characteristic . After a brief presentation of the previous works in that domain, in large part due to van der Put, we will focus on the case of central operators which are irreducible in the center of the ring of differential operators. This case is very important as the factorisation of any differential operator is brought back to one of those. We shall see that their factorisation is the same as solving a particular equation which we call the -Riccati equation over a finite separable extension of . We will show that solving this equation can be done in polynomial time in and the genus of through the use of Riemann-Roch spaces and the Divisor Class Group of . If the time allows it, we shall also present an irreducibility test relying on description of the Brauer group of in terms of its local Brauer groups. The irreducibility test can be done in polynomial time in and the genus of .

2024, March 25

Matías R. Bender (Inria - CMAP, École Polytechnique)

Multigraded Castelnuovo-Mumford regularity and Groebner bases

Time: from 11h00 to 12h00

Room: Grace Hopper

Groebner bases (GBs) are the “Swiss Army knife” of symbolic computations with polynomials. They are a special set of generators of an ideal which allow us to manipulate extremely complicated objects, so computing them is an intrinsically hard problem. To estimate the complexity of such computations, an extended approach is to bound the maximal degrees of the polynomials appearing in the GBs. One of the most important results in this direction is due to Bayer and Stillman, who showed in the 80s that, in generic coordinates, the maximal degree of an element in a GB of an homogeneous ideal with respect to the reverse lexicographical order is determined by the Castelnuovo-Mumford regularity of the ideal — an algebraic invariant independent of the GB. In this talk, I will present a generalization of their results for multi-homogeneous systems and show how the extension of the Castelnuovo-Mumford regularity to multi-graded ideals relates to the maximal degrees appearing in the computation of a GB. This talk is based on ongoing work with Laurent Busé, Carles Checa, and Elias Tsigaridas.


2024, March 18

Maxime Breden (CMAP, École polytechnique)

An introduction to computer-assisted proofs via a posteriori validation

Time: from 11h00 to 12h00

Room: Grace Hopper

The goal of a posteriori validation methods is to get a quantitative and rigorous description of some specific solutions of nonlinear ODEs or PDEs, based on numerical simulations. The general strategy consists in combining a priori and a posteriori error estimates, interval arithmetic, and a fixed point theorem applied to a quasi-Newton operator. Starting from a numerically computed approximate solution, one can then prove the existence of a true solution in a small and explicit neighborhood of the numerical approximation.

I will first present the main ideas behind these techniques on a simple example, and then describe how they can be used for rigorously integrating some differential equations.


2024, March 11

François Fages (Inria)

On rule-based models of dynamical systems

Time: from 11h00 to 12h00

Room: Grace Hopper

Chemical reaction networks (CRN) constitute a standard formalism used in systems biology to represent high-level cell processes in terms of low-level molecular interactions. A CRN is a finite set of formal kinetic reaction rules with well-defined hypergraph structure and several possible dynamics. One CRN can be interpreted in a hierarchy of formal semantics related by either approximation or abstraction relationships, including

We shall show how these different semantics come with different analysis tools which can reveal various dynamical properties of the other interpretations. In our CRN modeling software BIOCHAM (biochemical abstract machine), these static analysis tools are complemented by dynamic analysis tools based on quantitative temporal logic, and by an original CRN synthesis symbolic computation pipeline for compiling any computable real function in an elementary CRN over a finite set of abstract molecular species.


2024, February 26

Michel Fliess (LIX, École polytechnique)

Approximate flatness-based control via a case study: Drugs administration in some cancer treatments

Time: from 11h00 to 12h00

Room: Grace Hopper

We present some “in silico” experiments to design combined chemo- and immunotherapy treatment schedules. We introduce a new framework by combining flatness-based control, which is a model-based setting, along with model-free control. The flatness property of the used mathematical model yields straightforward reference trajectories. They provide us with the nominal open-loop control inputs. Closing the loop via model-free control allows to deal with the uncertainties on the injected drug doses. Several numerical simulations illustrating different case studies are displayed. We show in particular that the considered health indicators are driven to the safe region, even for critical initial conditions. Furthermore, in some specific cases there is no need to inject chemotherapeutic agents.

Joint work with C. Join, K. Moussa, S.M. Djouadi, M.W. Alsager.


2023, December 8

Mizuka Komatsu (Kobe University)

Application of differential elimination for physics-based deep learning and computing

Time: from 14h00 to 15h00

Room: Darboux amphitheater, Institut Henri Poincaré (11 Rue Pierre et Marie Curie, Paris)

In the field of differential algebra, differential elimination refers to the elimination of specific variables and/or their derivatives from differential equations. One well-known application of differential elimination is in the model identifiability analysis. Recently, there has been a growing demand for further applications in addition to this.

In this talk, we introduce two recent applications in the field related to physics. The first application field is physics-based deep learning. In particular, we introduce the application of differential elimination for Physics-Informed Neural Networks (PINNs), which are types of deep neural networks integrating governing equations behind the data. The second application is about physics-based computing, or, physical computing. This refers to information processing leveraging the dynamics of physical systems such as soft materials and fluids. In this talk, we show the application of differential elimination to time-series information processing via physical computing.

2023, April 24

Eric Goubault (LIX)

Set-based methods for the analysis of dynamical systems

Time: from 11h00 to 12h00

Room: Grace Hopper

In this talk, I will describe some set-based methods (i.e. «guaranteed» numerical methods) that we developed for helping analyze and validate dynamical (and control) systems. I will go through a number of problems, ranging from plain reachability, reach-avoid, robust reachability to invariance and general temporal specifications. The robust reachability and general temporal specifications will introduce the problem of solving some form of quantifier elimination, for which we will give a simple set-based method for inner and outer-approximating the set of solutions. Based on joint works with Sylvie Putot.


2023, April 17

Jacques Laskar (IMCCE)

Calcul formel et diffusion chaotique des mouvements planétaires dans le système solaire

Time: from 11h00 to 12h00

Room: Henri Poincaré

La mise en évidence du mouvement chaotique des planètes dans le système solaire a été obtenu grâce à une intégration des équation modernisées de leur mouvement (Laskar, 1989). Ce système d'équations contenant plus de 150 000 termes avait été obtenu par des méthodes de calcul formel très dédiées, dont l'adaptation n'était pas aisée. depuis 1988 a commencé la construction d'un système de calcul formel général, TRIP, spécialement adapté aux calculs de la mécanique céleste. Nous avons utilisé ce système récemment pour obtenir une meilleure compréhension de l'origine du chaos dans le système solaire, et pour étudier la diffusion chaotique du mouvement des planètes sur des durées bien supérieures à l'âge de l'univers.

2023, March 27

Alexander Demin (HSE University)

Finding exact linear reductions of dynamical models

Time: from 11h00 to 12h00

Room: Grace Hopper

Dynamical models described by systems of polynomial differential equations are a fundamental tool in the sciences and engineering. Exact model reduction aims at finding a set of combinations of the original variables which themselves satisfy a self-contained system. There exist algorithmic solutions which are able to rapidly find linear reductions of the lowest dimension under certain additional constraints on the input or output.

In this talk, I will present a general algorithm for finding exact linear reductions. The algorithm finds a maximal chain of reductions by reducing the question to a search for invariant subspaces of matrix algebras. I will describe our implementation and show how it can be applied to models from literature to find reductions which would be missed by the earlier approaches.

This is a joint work with Elizaveta Demitraki and Gleb Pogudin.


2023, March 20

Sebastian Falkensteiner (Max Planck Institute for Mathematics in the Sciences)

Using Algebraic Geometry for Solving Differential Equations

Time: from 11h00 to 12h00

Room: Henri Poincaré

Given a first order autonomous algebraic ordinary differential equation, i.e. an equation of the form with polynomial F and complex coefficients, we present a method to compute all formal power series solutions with fractional exponents. By considering y and y′ as independent variables, results from Algebraic Geometry can be applied to the implicitly defined plane curve. This leads to a complete characterization of initial values with respect to the number of distinct solutions extending them. Furthermore, the computed formal solutions are convergent in suitable neighborhoods and for any given point in the complex plane there exists a solution of the differential equation which defines an analytic curve passing through this point. These results can be generalized to systems of ODEs which implicitly define a space curve and to local solutions with real coefficients only. This is a joint work with Jose Cano, Rafael Sendra and Daniel Robertz.


2023, February 20

Thi Xuan Vu (Arctic University of Norway)

Faster algorithms for symmetric polynomial systems

Time: from 11h00 to 12h00

Room: Philippe Flajolet

Many important polynomial systems have additional structure, for example, generating polynomials invariant under the action of the symmetric group. In this talk we consider two problems for such systems. The first focuses on computing the critical points of a polynomial map restricted to an algebraic variety, a problem which appears in many application areas including polynomial optimization. Our second problem is to decide the emptiness of algebraic varieties over real fields, a starting point for many computations in real algebraic geometry. In both cases we provide efficient probabilistic algorithms for which take advantage of the special invariant structure. In particular in both instances our algorithms obtain their efficiency by reducing the computations to ones over the group orbits and make use of tools such as weighted polynomial domains and symbolic homotopy methods.


2022, December 12

Joris van der Hoeven (LIX)

Session dedicated to the Computer Mathematics research group

Sparse interpolation

Time: from 11h00 to 12h00

Room: Grace Hopper

Computer algebra deals with exact computations with mathematical formulas. Often, these formulas are very large and often they can be rewritten as polynomials or rational functions in well chosen variables. Direct computations with such expressions can be very expensive and may lead to a further explosion of the size of intermediate expressions. Another approach is to systematically work with evaluations. For a given problem, like inverting a matrix with polynomial coefficients, evaluations of the solution might be relatively cheap to compute. Sparse interpolation is a device that can then be used to recover the result in symbolic form from sufficiently many evaluations. In our talk, we will survey a few classical and a new approach for sparse interpolation, while mentioning a few links with other subjects.


2022, December 5

Marc Moreno Maza (University of Western Ontario)

Cache complexity in computer algebra

Time: from 11h00 to 12h00

Room: Grace Hopper

In the computer algebra literature, optimizing memory usage (e.g. minimizing cache misses) is often considered only at the software implementation stage and not at the algorithm design stage, which can result in missed opportunities, say, with respect to portability or scalability.

In this talk, we will discuss ideas for taking cache complexity, in combination with other complexity measures, at the algorithm design stage. We will start by a review of different memory models (I/O Complexity, cache complexity, etc.). We will then go through illustrative examples considering both multi-core and many-core architectures.


2022, November 14

Cyril Banderier (CNRS/Université Sorbonne Paris Nord)

Analytic combinatorics and partial differential equations

Time: from 11h00 to 12h00

Room: Grace Hopper

Many combinatorial structures and probabilistic processes lead to generating functions satisfying partial differential equations, and, in some cases, they even satisfy ordinary differential equations (they are D-finite).

In my talk, I will present results from these last 3 years illustrating this principle, and asymptotic consequences of this, on fundamental objects like Pólya urns, Young tableaux with walls, increasing trees, posets…

I will also prove that some cases are differentially algebraic (not D-finite), and possess surprising stretched exponential asymptotics involving exponents which are zeroes of the Airy function. The techniques are essentially extensions of the methods of analytic combinatorics (generating functions and complex analysis), as presented in the eponymous wonderful book of Flajolet and Sedgewick. En passant, I will also present a new algorithm for uniform random generation (the density method), and new universal distributions, establishing the asymptotic fluctuations of the surface of triangular Young tableaux.

This talk is based on joint work with Philippe Marchal and Michael Wallner:

Periodic Pólya urns, the density method, and asymptotics of Young tableaux, Annals of Probability, 2020.

Young tableaux with periodic walls: counting with the density method, FPSAC, 2021.

2022, November 7

Louis Roussel (Université de Lille)

Integral Equation Modelling and Deep Learning

Time: from 11h00 to 12h00

Room: Gilles Kahn

Considering models with integro-differential equations is motivated by the following reason: on some examples, the introduction of integral equations increases the expressiveness of the models, improves the estimation of parameter values from error-prone measurements, and reduces the size of the intermediate equations.

Reducing the order of derivation of a differential equation can sometimes be achieved by integrating it. An algorithm was designed by the CFHP team for that purpose. However, successfully integrating integro-differential equations is a complex problem. Unfortunately, there are still plenty of differential equations for which the algorithm does not apply. For example, computing an integrating factor might be required.

Rather than integrating the differential equation, we can perform an integral elimination. We are currently working on this technique which also implies some integration problems. To try to overcome these problems, we are also using deep learning techniques with the hope of finding small calculus tips.

2022, June 28

Antonio Jiménez-Pastor (LIX)

Exact nonlinear reductions of dynamical systems

Time: from 11h00 to 12h00

Room: Grace Hopper

Dynamical systems of the form are widely used in many sciences. Numerical procedures, such as simulation and parameter estimation do not work efficiently due to the high dimension of the dynamical systems. We studied exact reductions of the system, i.e., computing macro-variables that satisfy self-consistent differential systems. Thanks to the software CLUE, we can reduce the dimension of polynomial and rational dynamical systems by a linear change of variables (i.e., macro-variables are linear combinations of the original variables) preserving some linear quantities from the original state variables. In this talk we are going to present a new method to reduce the dimension of these dynamical systems even further by performing a nonlinear change of variables. We are going to show how to look for reductions of this type, how to preserve some information from the original system and how to compute the new self-consistent system that the new macro-variables satisfy.

2022, May 24

Marc Mezzarobba (LIX)

Session dedicated to the Computer Mathematics research group

Asymptotic Expansions with Error Bounds for Solutions of Linear Recurrences

Time: from 11h00 to 12h00

Room: Grace Hopper

When a sequence of real or complex numbers satisfies a linear recurrence relation with polynomial coefficients, it is usually routine to determine its asymptotic behavior for large . Well-known algorithms and readily available implementations are often able, given a recurrence satisfied by and some additional information on the particular solution, to compute an explicit asymptotic expansion

up to any desired order . If, however, one wishes to prove an inequality satisfied by for all , a big-Oh error term is not sufficient and an explicit error bound on the difference between the sequence and its asymptotic approximation is required. In this talk, I will present a practical algorithm for computing such bounds, under the assumption that the generating series of the sequence is solution of a differential equation with regular (Fuchsian) dominant singularities. I will show how it can be used to verify the positivity of a certain explicit sequence, which T. Yu and J. Chen recently proved to imply uniqueness of the surface of genus one in of minimal bending energy when the isoperimetric ratio is prescribed.

Based on joint work with Ruiwen Dong and Stephen Melczer.

2022, May 10

François Ollivier (LIX)

Generalized flatness and motion planning for aircraft models

Time: from 11h00 to 12h00

Room: Grace Hopper

If one neglects the forces created by controls, an aircraft is modeled by a flat system. First, one uses a feedback to compensate model errors and keep the trajectory of the full non flat system close to the trajectory computed for the flat approximation. In a second time, the values of the controls provided by the flat approximation are used in the full model for better precision and the process is iterated, which provides a very precise motion planning for the full model. Some examples are provided to illustrate the possibilities of a Maple package.

This new approach is called generalized flatness. The provided parametrization depends on an infinite number of flat outputs, which comforts a conjecture claiming that all controllable systems are flat if one allows parametrization depending on an infinite number of derivatives. On should notice that the necessary flatness conditions of Sluis and Rouchon express the fact that the order of the parametrization is finite. In the linear case, one may provide some theoretical interpretation.

2022, April 19

Ilaria Zappatore (INRIA Saclay)

Simultaneous Rational Function Reconstruction with Errors: Handling Poles and Multiplicities.

Time: from 11h00 to 12h00

Room: Grace Hopper

In this talk I focus on an evaluation-interpolation technique for reconstructing a vector of rational functions (with the same denominator), in presence of erroneous evaluations. This problem is also called Simultaneous Rational Function Reconstruction with errors (SRFRwE) and it has significant applications in computer algebra (e.g.for the parallel resolution of polynomial linear systems) and in algebraic coding theory (e.g. for the decoding of the interleaved version of the Reed-Solomon codes). Indeed, an accurate analysis of this problem leads to interesting results in both these scientific domains. Starting from the SRFRwE, we then introduce its multi-precision generalization, in which we include evaluations with certain precisions. Our goal is to reconstruct a vector of rational functions, given, among other information, a certain number of evaluation points. Thus, these evaluation points may be poles of the vector that we want to recover. Our multi-precision generalization also allows us to handle poles with their respective orders. The main goal of this work is to determine a condition on the instance of this SRFRwE problem (and its generalized version) which guarantee the uniqueness of the interpolating vector. This condition is crucial for the applications: in computer algebra it affects the complexity of the corresponding SRFRwE resolution algorithm, while in coding theory, it affects the number of errors that can be corrected. We determine a condition which allows us to correct any errors. Then we exploit and revisit results related to the decoding of interleaved Reed-Solomon codes in order to introduce a better condition for correcting random errors.

2021, December 14

Rim Rammal (Université Toulouse III - Paul Sabatier)

Differential flatness for fractional order dynamic systems

Time: from 11h00 to 12h00

Room: Henri Poincaré

Differential flatness is a property of dynamic systems that allows the expression of all the variables of the system by a set of differentially independent functions, called flat output, depending on the variables of the system and their derivatives. The differential flatness property has many applications in automatic control theory, such as trajectory planning and trajectory tracking. This property was first introduced for the class of integer order systems and then extended to the class of fractional order systems. This talk will present the flatness of the fractional order linear systems and more specifically the methods for computing fractional flat outputs.


2021, December 7

Mohab Saefey El Din (Sorbonne Université)

msolve: a library for solving multivariate polynomial systems

Time: from 11h00 to 12h00

Room: Grace Hopper

In this talk, we present a new open source library, developed with J. Berthomieu (Sorbonne Univ.) and C. Eder (TU Kaiserslautern) named msolve, for solving multivariate polynomial systems through computer algebra methods. Its core algorithmic framework relies on Gröbner bases and linear algebra based algorithms. This includes J.-C. Faugère's F4 algorithm, recent variants of the FGLM change of ordering and real root isolation.

This talk will cover a short presentation of the current functionalities provided by msolve, followed by an overview of the implemented algorithms which will motivate the design choices underlying the library. We will also compare the practical performances of msolve with leading computer algebra systems such as Magma, Maple, Singular, showing that msolve can tackle systems which were out of reach by the computer algebra software state-of-the-art. If time permits, we will report on new algorithmic developments for ideal theoretic operations (joint work with J. Berthomieu and C. Eder) and change of orderings algorithms (joint work with J. Berthomieu and V. Neiger).


2021, October 19

Mirco Tribastone (IMT Lucca)

Reconciling discrete and continuous modeling for the analysis of large-scale Markov chains

Time: from 11h00 to 12h00

Room: Grace Hopper

Markov chains are a fundamental tool for stochastic modeling across a wide range of disciplines. Unfortunately, their exact analysis is often hindered in practice due to the massive size of the state space - an infamous problem plaguing many models based on a discrete state representation. When the system under study can be conveniently described as a population process, approximations based on mean-field theory have proved remarkably effective. However, since such approximations essentially disregard the effect of noise, they may potentially lead to inaccurate estimations under conditions such as bursty behavior, separation of populations into low- and high-abundance classes, and multi-stability. This talk will present a new analytical method that combines an accurate discrete representation of a subset of the state space with mean-field equations to improve accuracy at a user-tunable computational cost. Challenging examples drawn from queuing theory and systems biology will show how the method significantly outperforms state-of-the-art approximation methods.

This is joint work with Luca Bortolussi, Francesca Randone, Andrea Vandin, and Tabea Waizmann.

2021, October 5

Rida Ait El Manssour (Max Planck Institute for Mathematics in the Sciences, Leipzig)

Linear PDE with constant coefficients

Time: from 11h00 to 12h00

Room: Henri Poincaré

I will present a work about practical methods for computing the space of solutions to a system of linear PDE with constant coefficients. These methods are based on the Fundamental Principle of Ehrenpreis–Palamodov from the 1960s which assert that every solution can be written as finite sum of integrals over some algebraic varieties. I will first present the main historical results and then recent algorithm for computing the space of solutions.

This is a joint work with Marc Harkonen and Bernd Sturmfels.


2021, September 28

Antonio Jiménez-Pastor (MAX team, École polytechnique)

DD-finite functions: a computable extension for holonomic functions

Time: from 11h00 to 12h00

Room: Grace Hopper

D-finite or holonomic functions are solutions to linear differential equations with polynomial coefficients. It is this property that allow us to exactly represent these functions on the computer. in this talk we present a natural extension of this class of functions: the DD-finite functions. These functions are the solutions of linear differential equations with D-finite coefficients. We will see the properties these functions have and how we can algorithmically compute with them.


2021, June 7

Thierry Combot (University of Burgundy)

Réduction des intégrales premières des champs de vecteurs du plan

Time: from 14h00 to 15h00

Online broadcast

Les intégrales premières symboliques d'un champ de vecteur rationnel du plan sont de 4 types: rationnelles, darbouxiennes, liouvilliennes et de Riccati. Il est possible de les rechercher jusqu'à un certain degré, mais en trouver une ne signifie pas qu'il n'en existe pas d'autres plus simples mais de degré plus élevé. Le problème de Poincaré consiste à trouver les intégrales premières rationnelles d'un tel champ de vecteur. Nous y ajouterons l'hypothèse qu'une intégrale première symbolique est donnée d'avance, et il nous “suffira” ainsi de savoir si l'on peut la simplifier. Nous présenterons des algorithmes de simplification d'intégrales premières pour le cas Ricatti et liouvilien, et nous verrons, qu'à l'exception d'un cas particulier, cela est aussi possible pour le cas darbouxien. Nous détaillerons un exemple résistant et ses liens avec les courbes elliptiques.


2021, May 10

François Boulier (Université de Lille)

Algèbre différentielle et géométrie différentielle tropicale

Time: from 14h00 to 15h00

Online broadcast

Dans cet exposé, je ferai un lien entre l'algèbre différentielle de Ritt et Kolchin et la géométrie différentielle tropicale initiée par Grigoriev, sur la question de l'existence de solutions en séries entières formelles. Sur la fin de l'exposé, je m'attarderai sur un théorème d'approximation qui constitue la partie difficile du théorème fondamental de la géométrie différentielle tropicale.


2021, April 12

Evelyne Hubert (INRIA Méditerranée)

Sparse Interpolation in terms of multivariate Chebyshev polynomials

Time: from 15h00 to 16h00

Online broadcast: https://greenlight.lal.cloud.math.cnrs.fr/b/oll-ehe-mn3

Sparse interpolation refers to the exact recovery of a function as a short linear combination of basis functions from a limited number of evaluations. For multivariate functions, the case of the monomial basis is well studied, as is now the basis of exponential functions. Beyond the multivariate Chebyshev polynomial obtained as tensor products of univariate Chebyshev polynomials, the theory of root systems allows to define a variety of generalized multivariate Chebyshev polynomials that have connections to topics such as Fourier analysis and representations of Lie algebras. We present a deterministic algorithm to recover a function that is the linear combination of at most r such polynomials from the knowledge of r and an explicitly bounded number of evaluations of this function.

This is a joint work with Michael Singer (https://hal.inria.fr/hal-02454589v1).

Video of a talk on the same topic.

2021, March 29

Viktor Levandovskyy (University of Kassel)

Gröbner technology over free associative algebras over rings: semi-decidability, implementation and applications

Time: from 14h00 to 15h00

Online broadcast: https://webconf.math.cnrs.fr/b/pog-m6h-mec

Computations with finitely presented associative algebras traditionally boil down to computations over free associative algebras. In particular, there is a notion of Gröbner(–Shirshov) basis, but generally its computation does not terminate, and thus the ideal membership problem is not solvable. However, many important special cases can be approached.

The Letterplace correspondence for free algebras, introduced by La Scala and Levandovskyy, allows to reformulate the Gröbner theory and to use highly tuned commutative data structures in the implementation and to reuse parts of existing algorithms in the free non-commutative situation. We report on the newest official release of the subsystem of Singular called Letterplace. With it, we offer an unprecedented functionality, some of which for the first time in the history of computer algebra. In particular, we present practical tools for elimination theory (via truncated Gröbner bases and via supporting several kinds of elimination orderings), dimension theory (Gel'fand-Kirillov and global homological dimension), and for further homological algebra (such as syzygy bimodules and lifts for ideals and bimodules) to name a few.

Another activity resulted in the extension of non-commutative Gröbner bases for supporting the coefficients in principal ideal rings including . Such computations are of big value (for example, in representation theory), since the results can be treated as universal for fields of arbitrary characteristic. Quite nontrivial examples illustrate the powerful abilities of the system we have developed and open the way for new applications.


2021, March 22

Huu Phuoc Le (Sorbonne Université)

Fast algorithm and sharp degree bounds for one block quantifier elimination over the reals

Time: from 14h00 to 15h00

Online broadcast

Quantifier elimination over the reals is one of the most important algorithmic problem in effective real algebraic geometry. It finds applications in several areas of computing and engineering sciences such as program verification, computational geometry, robotics and biology to cite a few. Geometrically, eliminating one block of quantifiers consists in computing a semi-algebraic formula which defines the projection of the set defined by the input polynomial constraints on the remaining set of variables (which we call parameters).

In this work, we design a fast algorithm computing a semi-algebraic formula defining a dense subset in the interior of that projection when the input is composed of a polynomial system of equations. Using the theory of Groebner bases, we prove that, on generic inputs, its complexity is where is the maximum degree in the output formulas and is the number of parameters. We provide a new explicit bound on which improves the state-of-the-art and make explicit the determinantal nature of these formulas which make them easier to evaluate than the formulas delivered by the previous algorithms. Our implementation shows the practical efficiency of our approach as it allows us to tackle examples which are out of reach of the state-of-the-art software.

This is joint work with Mohab Safey El Din.


2021, March 8

Mickaël Matusinski (Université de Bordeaux)

Surreal numbers with exponential and omega-exponentiation

Time: from 13h00 to 14h00

Online broadcast

Surreal numbers have been introduced by Conway while working on game theory: they allow to evaluate partial combinatorial games of any size! This is so because they consist in a proper class containing “all numbers great and small”, but also due to the richness of the structure we can endow them with: an ordered real closed field. Moreover, surreal numbers can be seen as formal power series with exp, log and derivation. This turns them into an important object also in model theory (universal domain for many theories) and real analytic geometry (formal counterpart for non oscillating germs of real functions).

In this talk, I will introduce these fascinating objects, starting with the very basic definitions, and will give a quick overview, with a particular emphasis on exp (which extends exp on the real numbers) and the omega map (which extends the omega-exponentiation for ordinals). This will help me to subsequently present our recent contributions with A. Berarducci, S. Kuhlmann and V. Mantova concerning the notion of omega-fields (possibly with exp). One of our motivations is to clarify the link between composition and derivation for surreal numbers.


2021, February 22

Yairon Cid-Ruiz (Ghent University)

Primary ideals and differential operators

Time: from 14h00 to 15h00

Online broadcast

The main objective will be to describe primary ideals with the use of differential operators. These descriptions involve the study of several objects of different nature, so to say; the list includes: differential operators, differential equations with constant coefficients, Macaulay's inverse systems, symbolic powers, Hilbert schemes, and the join construction.

As an interesting consequence, we will introduce a new notion of differential powers which coincides with symbolic powers in many interesting non-smooth settings, and so it could serve as a generalization of the Zariski-Nagata Theorem. I will report on some joint work with Roser Homs and Bernd Sturmfels.


2020, December 1

Thi Xuan Vu (Sorbonne Université, Univeristy of Waterloo)

Algebraic geometry codes from surfaces over finite fields

Time: from 15h00 to 16h00

Online broadcast

Let be a polynomial ring in variables with coefficients in a field of characteristic zero. Consider a sequence of polynomials in and a polynomial matrix in with rows and columns such that is at most and . We are interested in the algebraic set of point in an algebraic closure of at which all polynomials in and all -minors of vanish. Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry.

We investigate the structures of to provide bounds on the number of isolated points in depending on the maxima of the degrees in rows (resp. columns) of or the mixed volumes of column supports of when we study the total degrees of all polynomials and all entries of or when these polynomials are sparse. In addition, we design probabilistic homotopy algorithms for computing the isolated points with our algorithms running in time that is polynomial in the bound on the number of isolated points. We also derive complexity bounds for the particular but important case where and the columns of satisfy weighted degree constraints. Such systems arise naturally in the computation of critical points of maps restricted to algebraic sets when both are invariant by the action of the symmetric group.

This is joint work with J.-C. Faugère, J. D. Hauenstein, G. Labahn, M. Safey El Din and É. Schost.

2020, November 24

Michela Ceria (Univeristy of Milan)

Degroebnerization and error correcting codes: Half Error Locator Polynomial

Time: from 15h00 to 16h00

Online broadcast

The concept of “Degroebnerization” has been introduced by Mora within his books on the bases of previous results by Mourrain, Lundqvist, Rouiller.

Since the computation of Gröbner bases is inefficient and sometimes unfeasible, the Degroebnerization proposes to limit their use to the cases in which it is really necessary, finding other tools to solve problems that are classically solved by means of Gröbner bases. We propose an example of such problems, dealing with efficient decoding of binary cyclic codes by means of the locator polynomial. Such a polynomial has variables corresponding to the syndromes, as well as variables each corresponding to each error location. Decoding consists then in evaluating the polynomial at the syndromes and finding the roots in the corresponding variable. It is necessary to look for a sparse polynomial, so that the evaluation is not too inefficient. In this talk we show a preliminary result in this framework; a polynomial of this kind can be found—for error correction capability —in a degroebnerized fashion, and it has linear growth on the length of the code. We will also give some hints on potential extensions to more general codes.

2020, October 27

Elena Berardini

Algebraic geometry codes from surfaces over finite fields

Time: from 14h00 to 15h00, Room: Grace Hopper

Online broadcast: https://webconf.math.cnrs.fr/b/pog-4rz-uec

Algebraic geometry codes were introduced by Goppa in 1981 on curves defined over finite fields and were extensively studied since then. Even though Goppa construction holds on varieties of dimension higher than one, the literature is less abundant in this context. However, some work has been undertaken in this direction, especially on codes from surfaces. The goal of this talk is to provide a theoretical study of algebraic geometry codes constructed from surfaces defined over finite fields, using tools from intersection theory. First, we give lower bounds for the minimum distance of these codes in two wide families of surfaces: those with strictly-nef or anti-nef canonical divisor, and those which do not contain absolutely irreducible curves of small genus. Secondly, we specialize and improve these bounds for particular families of surfaces, for instance in the case of abelian surfaces and minimal fibrations, using the geometry of these surfaces.

The results appear in two joint works with Y. Aubry, F. Herbaut and M. Perret, preprints: https://arxiv.org/pdf/1904.08227.pdf and https://arxiv.org/abs/1912.07450.

2020, October 13

Ruiwen Dong

A new algorithm for finding the input-output equations of differential models

(Joint work with Christian Goodbreak, Heather Harrington, and Gleb Pogudin)

Time: from 14h00 to 15h00, Room: Gilles Kahn

The input-output equations of a differential model are consequences of the differential model which are also “minimal” equations depending only on the input, output, and parameter variables. One of their most important applications is the assessment of structural identifiability.

In this talk, we present a new resultant-based method to compute the input-output equations of a differential model with a single output. Our implementation showed favorable performance on several models that are out of reach for the state-of-the-art software. We will talk about ideas and optimizations used in our method as well as possible ways to generalize them.

2020, July 7

Simon Abelard

Computing Riemann–Roch spaces in subquadatric time

(Joint work with A. Couvreur and G. Lecerf)

Time: from 14h00 to 15h00, Room: teleconference

Given a divisor (i.e. a formal sum of points on a curve), the Riemann–Roch space is the set of rational functions whose poles and zeros are constrained by . These spaces are important objects in algebraic geometry and computing them explicitly has applications in various fields: diophantine equations, symbolic integration, arithmetic in Jacobians of curves and error-correcting codes.

Since the 1980's, many algorithms were designed to compute Riemann–Roch paces, incorporating more and more efficient primitives from computer algebra. The state-of-the-art approach ultimately reduces the problem to linear algebra on matrices of size comparable to the input.

In this talk, we will see how one can replace linear algebra by structured linear algebra on polynomial matrices of smaller size. Using a complexity bound due to Neiger, we design the first subquadratic algorithm for computing Riemann–Roch spaces.

2020, June 23

Gleb Pogudin

Exact model reduction by constrained linear lumping

(Joint work with A. Ovchinnikov, I.C. Perez Verona, and M. Tribastone)

Time: from 14h00 to 15h00, Room: teleconference

We solve the following problem: given a system of ODEs with polynomial right-hand side, find the maximal exact model order reduction by a linear transformation that preserves the dynamics of user-specified linear combinations of the original variables. Such transformation can reduce the dimension of a model dramatically and lead to new insights about the model. We will present an algorithm for solving the problem and applications of the algorithm to examples from literature. Then I will describe directions for further research and their connections with the structure theory of finite-dimensional algebras.

2020, June 9

Vincent Bagayoko

Asymptotic differential algebra

Time: from 14h00 to 15h00, Room: teleconference

I will describe a research program put forward by Joris van der Hoeven and his frequent co-authors Lou van den Dries and Matthias Aschenbrenner, in the framework of asymptotic differential algebra. This program sets out to use formal tools (log-exp transseries) and number theoretic / set-theoretic tools (surreal numbers) to select and study properties of “monotonically regular” real-valued functions.

2020, May 26

Simon Aberlard

Counting points on hyperelliptic curves defined over finite fields of large characteristic: algorithms and complexity

Time: from 14h00 to 15h00, Room: teleconference

Counting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this talk, we focus on counting points on hyperelliptic curves over finite fields of large characteristic . In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in . However, their dependency in the genus of the curve is exponential, and this is already a problem even for .

Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in of the exponent of . For hyperelliptic curves, previous work showed that it was quasi-quadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.

In genus 3, we proposed an algorithm based on those of Schoof and Gaudry–Harley–Schost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64-bit prime field.

In this talk, we will carefully reduce the problem of counting points to that of solving polynomial systems. More precisely, we will see how our results are obtained by considering either smaller or structured systems and choosing a convenient method to solve them.

2020, May 12

François Ollivier

Shortest paths… from Königsberg to the tropics

Time: from 14h00 to 15h00, Room: teleconference

Trying to avoid technicalities, we underline the contribution of Jacobi to graph theory and shortest paths problems. His starting point is the computation of a maximal transversal sum in a square matrix, that is choosing terms in each row and each column. This corresponds to the tropical determinant, which was so discovered in Königsberg, on the shores of the Baltic.

The key ingredient of Jacobi's algorithm for computing the tropical determinant is to build paths between some rows of the matrix, until all rows are connected, which allows to compute a canon, that is a matrix where one can find maximal terms in their columns, located in all different rows, by adding the same constant to all the terms of the same row.

Jacobi gave two algorithms to compute the minimal canon, the first when one already knows a canon, the second when one knows the terms of a maximal transversal sum. They both correspond to well known algorithms for computing shortest paths, the Dijkstra algorithm, for positive weights on the edges of the graph, and the Bellman–Ford algorithm, when some weights can be negative.

After a short tour with Euler over the bridges of Königsberg, a reverence to Kőnig's, Egerváry's and Kuhn's contributions, we will conclude with the computation of a differential resolvent.

2020, April 28

Marc Mezzarobba

Interval Summation of Differentially Finite Series

Time: from 14h00 to 15h00, Room: teleconference

I will discuss the computation of rigorous enclosures of sums of power series solutions of linear differential equations with polynomial coefficients ("differentially finite series"). The coefficients of these series satisfy simple recurrences, leading to a simple and fast iterative algorithm for computing the partial sums. When however the initial values (and possibly the evaluation point and the coefficients of the equation) are given by intervals, naively running this algorithm in interval arithmetic leads to an overestimation that grows exponentially with the number of terms. I will present a simple (but seemingly new!) variant of the algorithm that avoids interval blow-up. I will also briefly talk about other aspects of the evaluation of sums of differentially finite series and a few applications.

2020, April 7

Gleb Pogudin

Identifiability from multiple experiments

(Joint work with A. Ovchinnikov, A. Pillay, and T. Scanlon)

Time: from 14h00 to 15h00, Room: teleconference

For a system of parametric ODEs, the identifiability problem is to find which functions of the parameters can be recovered from the input-output data of a solution assuming continuous noise-free measurements.

If one allows to use several generic solutions for the same set of parameter values, it is natural to expect that more functions become identifiable. Natural questions in this case are: which function become identifiable given that enough experiments are performed and how many experiments would be enough? In this talk, I will describe recent results on these two questions.

2020, March 10

François Ollivier

Computing linearizing outputs of a flat system

(Joint work with Jean Lévine (Mines de Paris) and Jeremy Kaminski (Holon Institute of Technology))

Time: from 14h to 15h, Room: Flajolet

A flat system is a differential system of positive differential dimension, that is a system with controls for the control theorist, such that its general solution can be parametrized on some dense open set, using arbitrary functions, called “linearizing outputs”. The complementary of this open set corresponds to singular points for flatness. There also exist points for which classical flat outputs are singular, but for which alternative flat outputs may work, meaning that these are “apparent” singularities.

We present available methods to compute linearizing outputs of a flat system, with a special interest to apparent singularities: how to design, assuming it exists, regular alternative flat outputs. We will consider, as examples, classical models of quadcopters and planes.

2019, November, 18

Luis Miguel Pardo

Une preuve élémentaire de l'inégalité de Bézout de Heintz

Time: from 14h to 16h, Room: Grace Hopper

À l'occasion de la rédaction d'un texte sur l'algorithme « Kronecker » accessible à une large audience, nous avons été amenés à écrire une preuve complète de l'inégalité de Bézout de Heintz pour les variétés algébriques avec des arguments mathématiques disons élémentaires. Dans le même temps nous fournissons une extension de cette inégalité pour les ensembles constructibles, ainsi que quelques applications nouvelles à certains problèmes algorithmiques. Cet exposé présentera les grandes lignes de ces preuves élémentaires. Les applications, vers la fin de l'exposé, seront liées a quelques idées nouvelles autour des ensembles questeurs ("correct test sequences") pour les systèmes d'équations polynomiales.

2019, June, 24

Raphaël Rieu-Helft

How to get an efficient yet verified arbitrary-precision integer library

(Joint work with Guillaume Melquiond, joint seminar with GRACE team)

Time: 14h, Room: Grace Hopper

We present a fully verified arbitrary-precision integer arithmetic library designed using the Why3 program verifier. It is intended as a verified replacement for the mpn layer of the state-of-the-art GNU Multi-Precision library (GMP).

The formal verification is done using a mix of automated provers and user-provided proof annotations. We have verified the GMP algorithms for addition, subtraction, multiplication (schoolbook and Toom-2/2.5), schoolbook division, and divide-and-conquer square root. The rest of the mpn API is work in progress. The main challenge is to preserve and verify all the GMP algorithmic tricks in order to get good performance.

Our algorithms are implemented as WhyML functions. We use a dedicated memory model to write them in an imperative style very close to the C language. Such functions can then be extracted straightforwardly to efficient C code. For medium-sized integers (less than 1000 bits, or 100,000 for multiplication), the resulting library is performance-competitive with the generic, pure-C configuration of GMP.

2019, June, 3

Yirmeyahu Kaminiski

On singularities of flat affine systems with states and controls

(Joint work with Jean Lévine and François Ollivier)

Time: 11h, Room: Grace Hopper

We study the set of intrinsic singularities of flat affine systems with controls and states using the notion of Lie-Bäcklund atlas, previously introduced by the authors. For this purpose, we prove two easily computable sufficient conditions to construct flat outputs as a set of independent first integrals of distributions of vector fields, the first one in a generic case, namely in a neighborhood of a point where the control vector fields are independent, and the second one at a degenerate point where control vector fields are dependent of the others, with . We show that the set of intrinsic singularities includes the set of points where the system does not satisfy the strong accessibility rank condition and is included in the set where the distribution of vector fields, introduced in the generic case, is singular. We conclude this analysis by three examples of apparent singularites of flat systems in generic and non generic degenerate cases.

2019, May, 27

Time: 10h00–12h30, Room: Gilles Kahn

Joint seminar with the Cosynus team of LIX.

2019, May, 13

Gleb Pogudin

Global identifiability of differential models

Time: 10h30, Room: Grace Hopper

Many important real-world processes are modeled using systems of ordinary differential equations (ODEs) involving unknown parameters. The values of these parameters are usually inferred from experimental data. However, due to the structure of the model, there might be multiple parameter values that yield the same observed behavior even in the case of continuous noise-free data. It is important to detect such situations a priori, before collecting actual data. In this case, the only input is the model itself, so it is natural to tackle this question by methods of symbolic computation.

In this talk, I will present our new theoretical results on this problem and new reliable algorithms based on these results that can tackle problems that could not be tackled before, and software SIAN implementing the algorithms. This is a joint work with H. Hong, A. Ovchinnikov, and C. Yap.

2019, March, 6

Anand Kumar Narayanan

Fast computation of isomorphisms between finite fields using elliptic curves

Time: 14h, Room: Grace Hopper

Every finite field has prime power cardinality, for every prime power there is a finite field of that cardinality and every two finite fields of the same cardinality are isomorphic. This well known fact poses an algorithmic problem: compute an isomorphism between two explicitly presented finite fields of the same cardinality. We present a randomized algorithm to compute isomorphisms between finite fields using elliptic curves. Prior to this work, the best known run time dependence on the extension degree was quadratic. Our run time dependence is at worst quadratic but is subquadratic if the extension degree has no large prime factor. In particular, the extension degree for which our run time is nearly linear have natural density at least 3/10. The crux of our approach is finding a point on an elliptic curve of a prescribed prime power order or equivalently finding preimages under the Lang map on elliptic curves over finite fields. We formulate this as an open problem whose resolution would solve the finite field isomorphism problem with run time nearly linear in the extension degree.

Talk based on: Narayanan A. K. Fast Computation of isomorphisms between finite fields using elliptic curves. In: Budaghyan L., Rodríguez-Henríquez F. (eds.). Arithmetic of Finite Fields. WAIFI 2018. Lecture Notes in Computer Science, vol 11321. Springer, Cham, 2018.

2019, February, 21

Yacine Bouzidi

Some contributions to the intersection problem with polydisks

Time: 10h30, Room: Marcel-Paul Schützenberger

An important class of systems in control theory is the class of multidimensional systems in which information propagates in more than one independent direction. At the core of the study of such systems is the effective computation over the ring of rational fractions which have no poles in the closed unit polydisk . In this context, two important questions related to the stability and the stabilisation of these systems are

In [1], M. Strintzis states a fundamtental theorem showing that the first question can be simplified in the case of principal ideals. Namely, the theorem shows that the existence of complex zeros of a polynomial in is equivalent to the existence of complex zeros of at one face of the polydisk, i.e., , or at the poly-circle i.e., . The second question known in the literature as the polydisk nullstelensatz is still open for general systems.

In this presentation, we extend the fundamental result of Strintzis to some specific algebraic varieties, namely varieties of dimension one in (algebraic curves). We also propose an effective polydisk nullstellensatz in the case of zero-dimensional ideals. As a consequence, important questions about the stabilization of multidimensional systems can be answered using simple algorithms based on computer algebra techniques.

[1] Strintzis, M. Tests of stability of multidimensional filters. IEEE Transactions on Circuits and Systems, 24(8):432–437, 1977.

2019, February, 19

Cyrille Chenavier

Opérateurs de réduction : complétion, syzygies et dualité de Koszul

Time: 10h30, Room: Marcel-Paul Schützenberger

La réécriture est une théorie combinatoire des relations d'équivalences où les propriétés de celles-ci sont déduites de leurs orientations. Une de ces propriétés est la confluence qui garantie la cohérence des calculs. Dans cet exposé, je présente une description des systèmes de réécriture à travers leurs représentations par des opérateurs de réduction. Cela permet d'obtenir des formulations de la confluence et de la procédure de complétion en termes de treillis. Je présente également des applications de cette approche au calcul des syzygies des systèmes de réécriture linéaires et à la dualité de Koszul. De celle-ci est issue la construction du complexe de Koszul, qui, lorsqu'il est acyclique, est une résolution minimale d'algèbres. Un critère introduit par Roland Berger garantie que le complexe de Koszul est une telle résolution minimale. En exploitant la structure de treillis des opérateurs de réduction, je propose via une homotopie contractante une preuve constructive de ce critère.

2019, February, 18

Thibaut Verron

Calcul de bases de Gröbner avec signatures à coefficients dans un anneau principal

(Joint work with Maria Francis)

Time: 10h30, Room: Grace Hopper

Les algorithmes à signatures sont devenus une approche classique pour le calcul de bases de Gröbner pour des polynômes à coefficients dans un corps, et l'extension de cette technique à des polynômes à coefficients dans des anneaux a fait l'objet de travaux récents.

Dans ce travail, nous nous intéressons à deux algorithmes dûs à Möller (1988). Le premier de ces algorithmes permet de calculer des bases de Gröbner dites faibles, pourvu que l'anneau de coefficients soit noethérien et effectif. Nous montrons que, dans le cas où l'anneau des coefficients est principal, cet algorithme peut être adapté pour calculer des bases de Gröbner avec signatures. En particulier, l'algorithme garantit l'absence de chutes de signatures, ce qui permet d'adapter les critères de signatures classiques comme le critère singulier ou le critère F5.

Le second de ces algorithmes de Möller est quant à lui spécifique au cas des anneaux principaux, et permet de calculer une base de Gröbner forte de manière plus efficace que l'algorithme général. Nous montrons que cet algorithme peut également être adapté pour prendre en compte les signatures, et éviter un grand nombre de calculs redondants ou inutiles.

L'algorithme dédié aux anneaux principaux, contrairement à l'algorithme général, est également compatible avec les critères de Buchberger, notamment le critère de chaîne, et nous montrons que ce critère peut être ajouté de manière compatible avec les signatures.

Nous présentons enfin des résultats expérimentaux en termes de nombres de S-polynômes calculés, réduits ou écartés par les différents critères, mesurés sur une implantation « jouet » des algorithmes en Magma.

2018, December, 10

Pierre-Vincent Koseleff

Computing Chebyshev knot diagrams

(Joint work with D. Pecker, F. Rouillier, and C. Tran)

Time: 10h30, Room: Grace Hopper

Avec D. Pecker, nous avons montré que tout nœud de est un nœud de Chebyshev, i.e. admet une représentation polynomiale de la forme sont des entiers, et est le polynôme de Chebyshev . Avec F. Rouillier et C. Tran, nous avons proposé un algorithme pour identifier les nœuds de Chebyshev à 2 ponts (cas , , fixé et variant). L'exposé abordera les différents aspects de ce problème et sa généralisation. Il apparaît judicieux, de travailler dans des extensions cyclotomiques réelles et d'utiliser la base des polynômes unitaires de Chebyshev .

See: https://hal.archives-ouvertes.fr/hal-01232181

2018, February, 12

Yirmeyahu Kaminski

Intrinsic and Apparent Singularities in Flat Differential Systems

(Joint work with Jean Lévine and François Ollivier)

Time: 14h, Room: Grace Hopper

We study the singularities of locally flat systems, motivated by the solution, if it exists, of the global motion planning problem for such systems. More precisely, flat outputs may be only locally defined because of the existence of points where they are singular (a notion that will be made clear later), thus preventing from planning trajectories crossing these points. Such points are of different types. Some of them can be easily ruled out by considering another non singular flat output, defined on an open set intersecting the domain of the former one and well defined at the point in question. However, it might happen that no well-defined flat outputs exist at all at some points. We call these points intrinsic singularities and the other ones apparent. A rigorous definition of these points is introduced in terms of atlas and charts in the framework of the differential geometry of jets of infinite order and Lie-Bäcklund isomorphisms. We then give a criterion allowing to effectively compute intrinsic singularities. Finally, we show how our results apply to global motion planning of the well-known example of non-holonomic car. Flat differential systems, singularities, global motion planning.

2018, January, 8

Dan Roche

Integer polynomial sparse interpolation with near-optimal complexity

Time: 14h, Room: Henri Poincaré

We investigate algorithms to discover the nonzero coefficients and exponents of an unknown sparse polynomial, provided a way to evaluate the polynomial over any modular ring. This problem has been of interest to the computer algebra community for decades, and its uses include multivariate polynomial GCD computation, factoring, and sparse polynomial arithmetic. Starting with the early works of Zippel, Ben-Or and Tiwari, and Kaltofen, one line of investigation has a key advantage in achieving the minimal number of evaluations of the polynomial, and has received considerable attention and improvements over the years. It is closely related to problems in coding theory and exponential analysis. The downside, however, is that these methods are not polynomial-time over arbitrary fields. A separate line of work starting with Garg and Schost has developed a different approach that works over any finite field. After years of improvements, the complexity of both approaches over is currently the same. They scale well in most aspects except for the degree; the bit complexity in both cases is currently cubic in the bit-lengths of the exponents. By careful combination of the techniques in both approaches and a few new tricks, we are now able to overcome this hurdle. We present an algorithm whose running time is softly-linear in the size of the output and performs nearly the minimal number of evaluations of the unknown polynomial. Preliminary implementation results indicate good promise for practical use when the unknown polynomial has a moderate number of variables and/or large exponents.

2017, December 11

Fredrik Johansson

Numerical integration in complex interval arithmetic

Time: 10h30, Room: Grace Hopper

We present a new implementation of validated arbitrary-precision numerical evaluation of definite integrals , available in the Arb library. The code uses a version of the Petras algorithm, which combines adaptive subdivision with Gauss-Legendre (GL) quadrature, evaluating the integrand on complex intervals surrounding the path of integration to obtain rigorous error bounds. The first part of the talk discusses the general algorithm and its performance for interesting families of integrals. The second part, which is based on joint work with Marc Mezzarobba, discusses the fast computation of GL quadrature nodes with rigorous error bounds. It is well known that GL quadrature achieves a nearly optimal rate of convergence for analytic integrands with singularities well isolated from the path of integration, but due to the cost of generating GL quadrature nodes, the more slowly converging Clenshaw-Curtis and double exponential quadrature rules have often been favored when an accuracy of several hundreds or thousands of digits is required. We consider the asymptotic and practical aspects of this problem. An order-of-magnitude speedup is obtained over previous code for computing GL nodes with simultaneous high degree and precision, which makes GL quadrature viable even at very high precision.

— Lunch break from 11h45 until 13h45 —

Jean-Claude Yakoubsohn

Numerical approximation of multiple isolated roots of analytic systems

(Joint work with Marc Giusti)

Time: 14h, Room: Henri Poincaré

It is classical that the convergence of the Newton's method at the neighborhood of a singular isolated root of a system of equations is no longer quadratic. It may even diverge. To fix this problem we purpose a new operator, named singular Newton operator, generalizing the classical Newton operator defined regular case. To do so we construct a finite sequence of equivalent systems named deflation sequence where the multiplicity of the root drops strictly between two successive elements of the sequence. Hence the root is a regular root for the last system. Then there exits a regular square system extracted of this one named deflated system. The Singular Newton operator is defined as the classical Newton operator associated to this deflated system.

The main idea of the construction of the deflation sequence is the following. Since the Jacobian matrix is rank deficient at the root, it means that there exists relation between the lines (respectively columns) of this Jacobian matrix. These relations are given by the Schur complement of the Jacobian matrix. The result is that when the elements of the Schur complement are added to the initial system, we call this operation kernelling, one obtains an equivalent system where the multiplicity of the root has dropped. In this way, a sequence of equivalent system can be defined iteratively.

Finally we perform a local -theory of Smale of this Singular Newton operator.

2017, November 6

François Ollivier

Indécidabilité de l'appartenance à un idéal aux dérivées partielles de type fini (d'après Umirbaiev)

Time: 10h30, Room: Grace Hopper

On sait que l'appartenance à un idéal différentiel est indécidable [1]. On montre aussi que l'appartenance à un idéal différentiel premier ou radiciel est décidable, ce qui est une conséquence directe de la théorie des ensembles caractéristiques développée par Ritt [2]. On a également des résultats de décidabilité pour des idéaux différentiels isobares [1]. Le problème restait ouvert pour des idéaux différentiels de type fini. Dans un article récent, Umirbaiev [3] a montré que l'appartenance à un idéal aux dérivées partielles (donc avec au moins 2 dérivations) est indécidable. La démonstration repose sur une construction permettant d'associer à une machine de Minsky à 2 bandes un idéal stable pour 2 dérivations. Une machine de Minsky est une variante des machines de Turing. Les deux bandes sont finies à un bout et infini à l'autre. Il n'y a rien d'écrit dans chaque case, pas même la position, mais on peut repérer que la machine est sur la première case d'une bande. On peut associer à tout sous ensemble récursivement énumérable de une machine de Minsky sans cycle qui, partant de la case s'arrête si et seulement si le nombre est dans . L'appartenance à l'idéal différentiel correspondant ne peut être décidée en général, puisqu'il existe des ensembles de nombres entiers récursivement énumérables mais non récursifs. Ce travail laisse ouvert la situation d'un idéal différentiel ordinaire de type fini, sur laquelle nous tenterons de jeter quelques lumières.

[1] G. Gallo, B. Mishra, F. Ollivier (1991), « Some constructions in rings of differential polynomials », In: Mattson H.F., Mora T., Rao T.R.N. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1991. Lecture Notes in Computer Science, vol 539. Springer, Berlin, Heidelberg.

[2] J. F. Ritt, Differential algebra, AMS, 1950.

[3] U. Umirbaiev, « Algorithmic problems for differential polynomial algebras », Journal of Algebra, Volume 455, 1 June 2016, Pages 77-92.

— Lunch break from 11h45 until 13h45 —

Thierry Combot

Calcul symbolique des intégrales premières de champs de vecteur polynomiaux du plan

Time: 14h, Room: Grace Hopper

Soit un champ de vecteur polynomial du plan. Nous présenterons un algorithme calculant les invariant différentiels rationnels de jusqu'à une certaine borne donnée par l'utilisateur. Ces invariant différentiels pour un feuilletage associé à un champ de vecteur du plan ont été classifiés par G. Casale et il s'avère qu'il correspondent aux intégrales premières de d'un certain type, précisément rationnels, darbouxien, liouvillien et ricatti. Dans chaque cas, nous introduirons une notion de courbe extatique, généralisant celle pour les intégrales premières rationnelles. Une nouveauté est que ces courbes extatiques peuvent détecter (dans des cas non génériques) des intégrales premières de degré plus grand que . La sortie de l'algorithme est une équation différentielle dont les solutions correspondent aux intégrales premières recherchées. Ces solutions peuvent parfois être simplifiées, pouvant mener à des intégrales premières de degré très élevé dus à des phénomènes arithmétiques. Le cout probabiliste de l'algorithme est en , et peut être transformé en algorithme déterministe avec un cout supplémentaire.

2017, October, 9

Pierre Fortin

Task-based parallelism and heterogeneous deployment for the N-body problem

Time: 14h, Room: Grace Hopper

The -body problem, describing the computation of all pairwise interactions among bodies, is one of the key kernels for high performance computing (e.g. in astrophysics, molecular dynamics, electromagnetics, fluid mechanics…). Efficient algorithms (Fast Multipole Method, Dual Tree Traversal) have been introduced to solve this -body problem with linear runtime complexity. Their deployment on both multi-core and many-core architectures is crucial, but can raise multiple challenges, regarding performance, portability and programmability. We will here present how these difficulties can be overcome on several (homogeneous and heterogeneous) parallel architectures for astrophysical simulations.

2017, June, 8

Manuel Eberl

Automatic Asymptotics in Isabelle/HOL

Time: 14h, Room: Henri Poincaré

Isabelle/HOL is an interactive theorem prover (also called ‘proof assistant'); it provides a logical environment in which mathematical concepts can be defined and theorems about them can be proven. The system guides and assists the user in writing formal proofs, while every step of the proof is computer-checked, which minimises the possibility of mistakes.

This talk will give a brief overview of Isabelle/HOL, followed by a more detailed excursion into my project of bringing more tools for asymptotic analysis into Isabelle/HOL; in particular, this includes a procedure to automatically prove limits and ‘Big-O' estimates of real-valued functions similarly to computer algebra systems like Mathematica and Maple – but while proving every step of the process correct.

2017, March, 6

Robin Larrieu

Morphisme de Frobenius et FFT

Time: 10h30, Room: Claude Shannon

On considère un polynôme à coefficients dans le corps fini dont on souhaite calculer la transformée de Fourier discrète est une racine primitive -ième de l'unité. En général, une telle racine existe seulement dans une certaine extension de corps . Nous verrons comment il est possible, en exploitant les propriétés du morphisme de Frobenius, de gagner un facteur par rapport au calcul de la transformée de Fourier d'un polynôme à coefficients dans . Ce travail est l'analogue pour les corps finis du résultat bien connu selon lequel la transformée de Fourier est 2 fois plus rapide à calculer pour un polynôme à coefficients réels que pour un polynôme à coefficients complexes.

— Lunch break from 11h45 until 13h45 —

Nicholas Coxon

Fast systematic encoding of multiplicity codes

Time: 14h00, Room: Grace Hopper

Multiplicity codes are a relatively new family of polynomial codes introduced by Kopparty, Saraf and Yekhanin (STOC'11). They generalise the classical family of Reed-Muller codes by augmenting their construction to include the evaluations of Hasse derivatives up to a given order. In this talk, we present a quasi-linear time systematic encoding algorithm for multiplicity codes. For the special case of Reed-Muller codes, the encoding algorithm simply applies existing multivariate interpolation and evaluation algorithms of van der Hoeven and Schost (2013). The general encoding algorithm is obtained by generalising their algorithms to address Hermite type interpolation and evaluation problems.

2016, December, 12

Simone Naldi

SPECTRA: a Maple library for linear matrix inequalities

Time: 14h15, Room: Grace Hopper

Linear matrix inequalities (LMI) are a class of convex feasibility problems appearing in different applicative contexts. For instance, checking the asymptotic stability à la Lyapunov for linear differential systems, or computing nonnegativity certificates for multivariate polynomials, are LMI. I will discuss an approach based on techniques from real algebraic geometry to compute exact solutions to LMI, and what informations are carried by this representation. The related algorithms are implemented in a Maple library called SPECTRA, and part of the talk will be dedicated to discuss results on experiments on interesting examples.

Robin Larrieu

Généralisation de la transformée de Fourier tronquée pour des ordres quelconques

Time: 15h45, Room: Grace Hopper

La transformée de Fourier tronquée (TFT) vise à calculer seulement certaines valeurs d'une FFT classique. En évitant de calculer les valeurs intermédiaires qui n'interviennent pas dans le calcul des points d'évaluation souhaités, on réduit de manière notable la durée de l'opération : pour calculer points d'évaluation sur , le coût est réduit à opérations élémentaires, où est le coût d'une FFT classique. Cela permet de réduire les effets de saut de complexité dans les algorithmes d'évaluation-interpolation (typiquement pour la multiplication de polynômes). Dans la formulation initiale de la TFT, on suppose que est une puissance de , mais certaines applications, par exemple pour des corps finis, peuvent nécessiter une forme plus générale pour . Après avoir rappelé rapidement le principe de la FFT, et celui de la TFT quand est une puissance de , nous verrons comment ces techniques peuvent être adaptées pour quelconque.

2016, May, 23 — Control theory day

Michel Fliess

Commande sans modèle : a-t-on toujours besoin d'un modèle pour appliquer les mathématiques à l'industrie ?

Time: 10h30, Room: Marcel-Paul Schützenberger

On expose les principes généraux de la « commande sans modèle », qui permet de réguler avec précision et facilité bien des dispositifs concrets sans recourir à une modélisation mathématique, toujours difficile, voire impossible, à obtenir. On passe en revue de nombreux exemples. En conclusion, quelques considérations générales sur les mathématiques appliquées, notamment en automatique, tentent de placer cet exposé dans un cadre plus général.

— Lunch break from 12h until 13h30 —

John Masse

L'apport du calcul formel dans une démarche système

Time: 14h, Room: Marcel-Paul Schützenberger

Exemples d'applications du calcul formel pour le CNES, l'analyse de sensibilité des modèles Simulink, et d'autres applications.

Cédric Join

Commande sans modèle : de la théorie à la pratique

Time: 15h30, Room: Marcel-Paul Schützenberger

On détaille la mise en oeuvre de la commande sans modèle. Des méthodes nouvelles d'estimation, d'essence algébrique et faciles à implanter, en sont le fil conducteur. On étudiera les contraintes pratiques qu'elles doivent satisfaire. La conclusion portera sur la complexité actuelle de l'algorithme.

2016, May, 9

Guillermo Matera

Estimates on the number of solutions of equations over a finite field and applications

Time: 10h30, Room: Paul Schützenberger

The set of rational solutions of polynomial systems over a finite field is a classical subject of study, whose origins can be traced back to works of Gauss and Jacobi, and has contributions of Hardy, Littlewood, Chevalley, Davenport, Weil, Lang and Deligne, among others. In this talk we shall discuss recent results of existence of solutions and estimates on the number of solutions of polynomial systems over a finite field. We shall also comment on applications of these estimates to problems in coding theory and combinatorics.

2015, September, 21 — Mathemagix day

Philippe Trébuchet


Time: 10h30, Room: Grace Hopper

Border bases form an alternative method to Groebner bases for polynomial system solving. The advantage is an increased flexibility for the choice of critical pairs, which is particularly useful for increasing the numerical stability of numerical solvers. In this talk, I will present the Borderbasix library, which is dedicated to the resolution of polynomial systems in this way.

Grégoire Lecerf

Advances in the C++ libraries Numerix, Algebramix, Multimix and Factorix

Time: 11h, Room: Grace Hopper

I will present recent implementations added to the C++ Mathemagix libraries Numerix, Algebramix, Multimix and Factorix. In particular these libraries now benefit from an efficient support of AVX2 instruction set for numeric and modular arithmetic. I will report on applications and performances. Parts of these works are joint with Joris van der Hoeven and Guillaume Quintin.

— Lunch break from 11h30 until 14h —

Bernard Mourrain

Geometric computation with Mathemagix

Time: 14h, Room: Grace Hopper

I will describe the packages Realroot and Shape, and their integration as plugin in the algebraic-geometric modeler Axel. The first package realroot is dedicated to the isolation of real roots of polynomial equations. It contains several implementations of subdivision methods in different bases (monomial and Bernstein bases), which are key ingredients in geometric computation. The second package shape is dedicated to the manipulation and analysis of semi-algebraic curves and surfaces. It provides tools for the computation of intersection points of curves and surfaces, singular points, intersection curves of two surfaces, topology analysis, … The integration of these packages as a plugin of Axel will also be described.

Suzy Maddah

Lindalg: Mathemagix package for symbolic resolution of linear differential systems with singularities

Time: 14h30, Room: Grace Hopper

Lindalg is dedicated to the local analysis of -th order linear differential equations and first order linear differential systems. At ordinary points, it suffices to consider Taylor series (power series). Any engineering student or scientist is familiar with their resolution procedure and popular computer systems always consider a package for this goal. However, singular points require further investigation based on an analysis of a Newton polygon and matricial manipulations. Differential equations with singularities arise from countless applications and encompass a vast body of contemporary academic literature. The package Isolde written in the computer algebra system Maple is dedicated to the symbolic resolution of such systems and more generally linear functional matrix equations (e.g. difference equations).

On the other hand, the new package Lindalg sets a first milestone in providing the two-decade span of Isolde content in an open source software. Mathemagix provides a new high level general purpose language for symbolic and certified numeric algorithms, that can be both interpreted by a shell or compiled.

— Coffee break from 15h until 15h30 —

Joris van der Hoeven

Programming symbolic expressions using the Mathemagix language

Time: 15h30, Room: Grace Hopper

We will show how to program symbolic expressions using the Mathemagix language and its compiler. The Caas package contains a concrete implementation and forms a nice illustration of how to use some new language features such as extendable abstract datatypes, pattern matching, and fast dispatching.

Bruno Grenet

Lacunaryx : calcul des facteurs de degré borné de polynômes lacunaires

Time: 16h, Room: Grace Hopper

Mon exposé présentera une nouvelle bibliothèque Mathemagix appelée Lacunaryx. Elle fournit une implantation d'algorithmes de factorisation pour les polynômes creux ou lacunaires : ces algorithmes prennent en entrée un polynôme en représentation creuse et une borne de degré et retournent la liste des facteurs de degré au plus de . La complexité de ces algorithmes est polynomiale en la taille de la représentation creuse, c'est-à-dire en particulier poly-logarithmique en le degré.

2014, November, 24

Pablo Solerno

Un algorithme de décision pour l'intégrabilité de systèmes de Pfaff

Time: 11h, Room: Philippe Flajolet

On montre un critère qui permet de décider si un système différentiel-algébrique de Pfaff a une solution. La méthode induit un algorithme de décision dont sa complexité est doublement exponentielle dans le nombre d'inconnues et de variables indépendantes, et polynomial dans le degrés et le nombre des polynômes qui apparaissent dans le système.

Luis-Miguel Pardo

Un résumé subjectif sur le 17-ième problème de Smale: les quatre pattes de SUMO

Time: 15h, Room: Marcel-Paul Schützenberger

L'exposé contiendra une vision personnelle sur les quatre pattes de la résolution du Problème 17-ième de Smale :

“Can a zero of complex polynomial equations in unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?”

Ses quatre pattes, à mon avis, sont : le conditionnement, l'opérateur, l'homotopie et la géométrie intégrale (voire probabilité). La dernière étant la plus efficace à donner des bonnes réponses jusqu'à présent.

Pdf version

2014, November, 17

Éric Schost (joint work with Esmaeil Mehrabi)

On the Complexity of Solving Bivariate Systems

Time: 11h, Room: Philippe Flajolet

We present an algorithm for the symbolic solution of bivariate polynomial systems with coefficients in with essentially optimal bit complexity. The core of the algorithm is a classical Newton iteration procedure. New ingredients are needed, though, such as Kedlaya-Umans' modular composition algorithm and deflation techniques due to Lecerf.

This webpage is part of the MAX project. Verbatim copying and distribution of it is permitted in any medium, provided this notice is preserved. For more information or questions, please contact Joris van der Hoeven.