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:Characterizing Positively Invariant Sets: Inductive and Topological Methods,
Khalil Ghorbal, Inria, Univ. Rennes 1 (France).
Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation,
Vincent Neiger, Univ. Limoges (France).
TBA,
Gleb Pogudin, LIX (Ecole polytechcnique, France).
ITN POEMA Online Learning Weeks.
Thematic program at Institut Henri Poincaré on post-quantum algebraic cryptogaphy.
To receive further anouncements, register for the mailing list here:
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)
6 nov. 2020
10:30-12:00
Room ?
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.
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.