This seminar focuses mainly on computer algebra algorithms and implementations for solving mathematical problems exactly, with a special focus on polynomial system solving and its broad range of applications.
Among others, topics which are covered are:To receive further anouncements, register for the mailing list here:
Elimination problem for ODE systems and parameter identifiability,
Gleb Pogudin, LIX (Ecole polytechnique, France).
TBA,
Rémi Imbach, Courant Inst. (NYU, USA).
Structured algorithms for algebraic curves,
Simon Abelard, LIX (Ecole Polytechnique, France).
TBA,
Thibaut Verron, Inst. for Algebra (Univ. J. Kepler, Austria).
TBA,
Ilaria Zapatore, Inria
Paris Saclay, (France).
ITN POEMA 2nd workshop. Oct. Nov. Dec. 2020
Thematic program at Institut Henri Poincaré on post-quantum algebraic cryptogaphy.
4 dec. 2020
11:00-12:00
online
Elimination of unknowns in systems of polynomial equations is a standard tool of computational algebra and algebraic geometry going back to the pioneers of the subject. An analogous question of elimination of unknowns in differential-algebraic equations can be stated as follows: given a system of nonlinear differential equations in two groups of variables, $x$'s and $y$'s, describe all the consequences of the system depending solely on $x$'s. Such a differential elimination problem has been studied already by Joseph Ritt, the founder of differential algebra, who proposed the first algorithm for solving it in 1930's. Collective effort of many researchers in the field aimed at understanding and improving this algorithm culminated in modern differential elimination algorithms such as the Rosenfeld-Gröbner algorithm which is now a part of the Maple standard library.
I will talk about differential elimination from the point of view of applications to modeling. Differential elimination is the key step in one of the approaches to the parameter identifiability problem (to decide whether or not parameters can in principle be recovered from the observations). A big portion of dynamical models used in sciences are ODE system, that is, are of the form $x' = f(x)$. General algorithms like the Rosenfeld-Gröbner algorithm are applicable in this situation but there is a price to pay for their generality and versatility: many interesting instances cannot be tackled by them in reasonable time. I will describe a new projection-based elimination algorithm tailored to ODE systems which allows to perform elimination (and then assess parameter identifiability) for systems that could not be tackled before. I will conclude by speculating about potential applications of this algorithm in other domains where ODE systems often appear, for example, for computations with differential-algebraic functions.
This is based on joint work in progress with Ruiwen Dong, Emilie Dufresne, Christian Goodbrake, and Heather Harrington.
LIX, Ecole Polytechnique (France)
5 feb. 2021
online
In this talk we will discuss two different algorithmic problems related to algebraic curves : counting points and computing Riemann-Roch spaces, both of them having applications in various fields of computer science such as cryptography and coding theory. These tasks are actually closely related to well-known problems from computer algebra.
The first problem mostly boils down to solving polynomial systems. We will see how the underlying structure of these systems helps to derive better complexity bounds and to perform practical computations.
For the second problem, previous algorithms (Khuri-Makdisi in 2007, Le Gluher and Spaenlehauer in 2018) compute Riemann-Roch spaces through the use of linear algebra. The main novelty of our work is to rely on a $K[X]$-module structure instead so that we can replace linear algebra by faster algorithms for computing interpolation bases (such as the one of Neiger in 2016), thus deriving a subquadratic complexity bound. We will also talk about the ongoing implementation of this algorithm.
The first part of the talk contains joint work with P. Gaudry and P.-J. Spaenlehauer, the second part is joint work with A. Couvreur and G. Lecerf.
LIX, Ecole Polytechnique (France)
13 nov. 2020
15-16:30
online
The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks. In particular, the notion of chordality and treewidth play a pivotal role in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. Our main contribution is the introduction of a new representation of structured polynomial systems: “chordal networks”. Chordal networks provide a computationally convenient decomposition of the system into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. We illustrate through examples from different application domains that algorithms based on chordal networks can significantly outperform existing techniques.
MIT (USA)
6 nov. 2020
11:00-12:00
Room 25-26/105 + online
This talk presents joint work with J. Rosenkilde and G. Solomatov, about new algorithms for bivariate multi-point evaluation, interpolation and modular composition, which under certain assumptions have quasi-linear complexity. For multi-point evaluation and interpolation we assume that the set of points is generic and available for precomputation. In the case of modular composition, similar assumptions are made on a bivariate ideal which depends on part of the input. The key tool is an algorithm that reshapes the degree bounds of a given bivariate polynomial while preserving its membership in a coset of some fixed bivariate ideal available for precomputation.
XLIM, Univ. Limoges.
9 oct. 2020
11:00-12:00
Online seminar
Set positive invariance is an important concept in the theory of dynamical systems and one which also has practical applications in areas of computer science, such as formal verification, as well as in control theory. Great progress has been made in understanding positively invariant sets in continuous dynamical systems and powerful computational tools have been developed for reasoning about them; however, many of the insights from recent developments in this area have largely remained folklore and are not elaborated in existing literature. This presentation contributes an explicit development of modern methods for checking positively invariant sets of ordinary differential equations and describes two possible characterizations of positive invariants: one based on the real induction principle, and a novel alternative based on topological notions. The two characterizations, while in a certain sense equivalent, lead to two different decision procedures for checking whether a given semi-algebraic set is positively invariant under the flow of a system of polynomial ordinary differential equations.
This is a joint work with Andrew Sogokon from University of Southampton, UK.
Inria, Univ. Rennes 1 (France)
11 sep. 2020
15:00-16:00
Online seminar
Given a nonsingular matrix polynomial $A$ whose coefficients are floating point numbers, we discuss a number of "nearest" approximation algebra problems. This includes finding the nearest singular matrix polynomial, the nearest polynomial matrix having a specified rank and finding a nearest interesting Smith normal form. We show that solving such problems are amenable to numeric computation as optimization problems. This includes determining the geometry and existence of nearest solutions and providing iterative numerical methods for computing these solutions.
This is joint work with Mark Giesbrecht and Joseph Haraldson
Univ. Waterloo, Canada
3 july 2020
10:30-11:30
Online seminar
In 1977, Strassen invented a famous baby-step / giant-step algorithm that computes the factorial $N!$ in arithmetic complexity quasi-linear in $\sqrt{N}$. In 1988, the Chudnovsky brothers generalized Strassen’s algorithm to the computation of the $N$-th term of any holonomic sequence in the same arithmetic complexity. We design $q$-analogues of these algorithms.
We first extend Strassen's algorithm to the computation of the $q$-factorial of $N$, then Chudnovskys' algorithm to the computation of the $N$-th term of any $q$-holonomic sequence. Both algorithms work in arithmetic complexity quasi-linear in $\sqrt{N}$.
We describe various algorithmic consequences, including the acceleration of polynomial and rational solving of linear $q$-differential equations, and the fast evaluation of large classes of polynomials including a family recently considered by Nogneng and Schost.
INRIA.
19 june 2020
11:00-12:00
Online seminar
Given elements $f_1, \ldots, f_m$ in a quotient $R^n / N$ of finite dimension as a $K$-vector space, where $R = K[X_1,\ldots,X_r]$ and $N$ is an $R$-submodule of $R^n$, we consider the problem of computing a Gröbner basis of the module of syzygies of $(f_1, \ldots, f_m)$, that is, of the set of vectors $(p_1, \ldots, p_m) \in R^m$ such that $p_1 f_1+\cdots+p_m f_m = 0$.
An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of the base module as the kernel of a collection of linear functionals. Following this viewpoint, we design a divide-and-conquer algorithm, which can be interpreted as a generalization to several variables of Beckermann-Labahn's recursive approach for matrix Padé and rational interpolation problems.
To highlight the interest of this method, we focus on the specific case of bivariate Padé approximation and show that it improves upon the best known complexity bounds.
Joint work with Vincent Neiger.
XLIM, Univ. Limoges.
13 mars 2020
11:00-12:30
26-00/332
In 2001, Lasserre introduced a nowadays famous hierarchy of relaxations, called the moment-sums of squares hierarchy, allowing one to obtain a converging sequence of lower bounds for the minimum of a polynomial over a compact semialgebraic set. Each lower bound is computed by solving a semidefinite program (SDP).
There are two common drawbacks related to this hierarchy. First, the size of the SDP problems arising from the hierarchy grows rapidly. Second, one relies on numerical SDP solvers, implemented in finite-precision, thus providing only approximate certificates.
In this talk, we explain how to address these two efficiency and certification issues.
In the first part, we recall how to exploit the sparsity pattern arising in polynomial optimization problems. We present one application for an optimization problem in commuting variables, which is a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. Then we present one application for optimization problems in non-commuting variables, which is a converging hierarchy of SDP relaxations for eigenvalue and trace optimization.
In the second part, we provide a hybrid symbolic-numeric algorithm computing exact rational sums of squares (SOS) decompositions for polynomials lying in the interior of the SOS cone. This algorithm computes an approximate decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact decomposition is obtained thanks to the perturbation terms. Then, we apply this algorithm to compute exact Polya and Putinar’s representations respectively for positive definite forms and polynomials positive over basic compact semialgebraic sets.
LAAS
28 fev. 2020
15:00-17:00
26-00/332
In the first part of the talk, we present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E8 is the unique solution for the kissing number problem on the hemisphere in dimension 8.
However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, we explain how, via our rounding procedure, we can obtain an exact rational solution of semidefinite program from an approximate solution in floating point given by the solver.
Joint work with Maria Dostert and David de Laat.
Univ. of Tromso, Norway.
14 nov. 2019
10:30-12:00
24-25/405
This talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials $a$ and $g$ over a commutative field, modular composition asks to compute $h(a) \mod g$ for some given $h$, while the minimal polynomial problem is to compute h of minimal degree such that $h(a) = 0 \mod g$. For generic $g$ and $a$, 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 $g$ and $a$ 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.
Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard
XLIM, Univ. Limoges.
25 sep. 2019
13:00-14:00
24-25/405
3D reconstruction of points and lines from images is an important and frequently studied problem. So-called minimal problems are essential ingredients in the structure-from-motion pipeline used for 3D reconstruction. We produce complete catalogs of minimal problems in two natural settings.
The first catalog consists of 30 minimal problems assuming complete visibility. The second one lists more than 100,000 classes of equivalence of nonreducible noncollinear problems in the partial visibility setting. Using fast implementations of Groebner bases and homotopy continuation methods we computed the degrees (numbers of solutions) of the problems in the first catalog. Finding interesting problems and their degrees in the second catalog is an ongoing project --- some of these provide a challenge to the aforementioned computational methods.
(Joint work with Tim Duff, Kathlen Kohn, and Tomas Pajdla.)Georgia Tech., USA.