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

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.

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

Borderbasix

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.