Kohel, David

We develop a computational framework for the statistical characterization of Galois characters with finite image, with application to characterizing Galois groups and establishing equivalence of characters of finite images of $\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$.

Berthomieu, Jérémy Faugère, Jean-Charles

The Berlekamp–Massey–Sakata algorithm and the Scalar-FGLM algorithm both compute the ideal of relations of a multidimensional linear recurrent sequence.Whenever quering a single sequence element is prohibitive, the bottleneck of these algorithms becomes the computation of all the needed sequence terms. As such, having adaptive variants of these alg...

Busé, Laurent Mantzaflaris, Angelos Tsigaridas, Elias

The construction of optimal resultant formulae for polynomial systems is one of the main areas of research in computational algebraic geometry. However, most of the constructions are restricted to formulae for unmixed polynomial systems, that is, systems of polynomials which all have the same support. Such a condition is restrictive, since mixed sy...

Grunspan, Cyril Van Der Hoeven, Joris

It is known that an adaptation of Newton's method allows for the computation of functional inverses of formal power series. We show that it is possible to successfully use a similar algorithm in a fairly general analytical framework. This is well suited for functions that are highly tangent to identity and that can be expanded with respect to asymp...

Dumas, Jean-Guillaume Kaltofen, Erich

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size $N$, meanin...

Emiris, Ioannis Mourrain, Bernard Tsigaridas, Elias

We rely on aggregate separation bounds for univariate polynomials to introduce novel bounds for the isolated roots of zero-dimensional, as well as positive-dimensional and overdetermined, polynomial systems. We exploit the structure of the given system, as well as bounds on the height of the sparse (or toric) resultant, by means of mixed volume, th...

Hauenstein, Jonathan D. Safey El Din, Mohab Schost, Éric Vu, Thi Xuan

Let $\K$ be a field of characteristic zero and $\Kbar$ be an algebraic closure of $\K$. Consider a sequence of polynomials$G=(g_1,\dots,g_s)$ in $\K[X_1,\dots,X_n]$, a polynomial matrix $\F=[f_{i,j}] \in \K[X_1,\dots,X_n]^{p \times q}$, with $p \leq q$,and the algebraic set $V_p(F, G)$ of points in $\KKbar$ at which all polynomials in $\G$ and all ...

Boulier, François Lemaire, François Rosenkranz, Markus Ushirobira, Rosane Verdière, Nathalie

Recent progress in computer algebra has opened new opportunities for the parameter estimation problem in nonlinear control theory, by means of integro-differential input-output equations. This paper recalls the origin of integro-differential equations. It presents new opportunities in nonlinear control theory. Finally, it reviews related recent the...

Van Der Hoeven, Joris

The class of reduction-based algorithms was introduced recently as a new approach towards creative telescoping. Starting with Hermite reduction of rational functions, various reductions have been introduced for increasingly large classes of holonomic functions. In this paper we show how to construct reductions for general holonomic functions, in th...

Van Der Hoeven, Joris Larrieu, Robin

Let A, B ∈ K[X, Y] be two bivariate polynomials over an effective field K, and let G be the reduced Gröbner basis of the ideal I ≔ ⟨A, B⟩ generated by A and B with respect to the usual degree lexicographic order. Assuming A and B sufficiently generic, we design a quasi-optimal algorithm for the reduction of P ∈ K[X, Y] modulo G, where "quasi-optima...