Source author record

Éric Schost

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Symbolic Computation math.NT Mathematical Software math.AG math.NA Numerical Analysis

Catalog footprint

Research overview

16works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Computing critical points for invariant algebraic systems

Let $\mathbf{K}$ be a field and $ϕ$ , $\mathbf{f} = (f_1, \ldots, f_s)$ in $\mathbf{K}[x_1, \dots, x_n]$ be multivariate polynomials (with $s < n$ ) invariant under the action of $\mathcal{S}_n$ , the group of permutations of $\{1, \dots, n\}$ . We consider the problem of computing the points at which $\mathbf{f}$ vanish and the Jacobian matrix associated to $\mathbf{f}, ϕ$ is rank deficient provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of $\mathcal{S}_n$ . This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in $d^s$ , ${{n+d}\choose{d}}$ and $\binom{n}{s+1}$ where $d$ is the maximum degree of the input polynomials. When $d,s$ are fixed, this is polynomial in $n$ while when $s$ is fixed and $d \simeq n$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.

preprint2020arXiv

Computing syzygies in finite dimension using fast linear algebra

We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a $\mathbb{K}[X_1,\dots,X_r]$ -module $\mathcal{M}$ of finite dimension $D$ as a $\mathbb{K}$ -vector space, and given elements $f_1,\dots,f_m$ in $\mathcal{M}$ , the problem is to compute syzygies between the $f_i$ 's, that is, polynomials $(p_1,\dots,p_m)$ in $\mathbb{K}[X_1,\dots,X_r]^m$ such that $p_1 f_1 + \dots + p_m f_m = 0$ in $\mathcal{M}$ . Assuming that the multiplication matrices of the $r$ variables with respect to some basis of $\mathcal{M}$ are known, we give an algorithm which computes the reduced Gröbner basis of the module of these syzygies, for any monomial order, using $O(m D^{ω-1} + r D^ω\log(D))$ operations in the base field $\mathbb{K}$ , where $ω$ is the exponent of matrix multiplication. Furthermore, assuming that $\mathcal{M}$ is itself given as $\mathcal{M} = \mathbb{K}[X_1,\dots,X_r]^n/\mathcal{N}$ , under some assumptions on $\mathcal{N}$ we show that these multiplication matrices can be computed from a Gröbner basis of $\mathcal{N}$ within the same complexity bound. In particular, taking $n=1$ , $m=1$ and $f_1=1$ in $\mathcal{M}$ , this yields a change of monomial order algorithm along the lines of the FGLM algorithm with a complexity bound which is sub-cubic in $D$ .

preprint2020arXiv

Homotopy techniques for solving sparse column support determinantal polynomial systems

Let $\mathbf{K}$ be a field of characteristic zero with $\overline{\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials $\mathbf{g} = (g_1, \ldots, g_s) \in \mathbf{K}[x_1, \ldots , x_n]^s$ and a polynomial matrix $\mathbf{F} = [f_{i,j}] \in \mathbf{K}[x_1, \ldots, x_n]^{p \times q}$ , with $p \leq q$ , we are interested in determining the isolated points of $V_p(\mathbf{F},\mathbf{g})$ , the algebraic set of points in $\overline{\mathbf{K}}$ at which all polynomials in $\mathbf{g}$ and all $p$ -minors of $\mathbf{F}$ vanish, under the assumption $n = q - p + s + 1$ . Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry. We design a randomized sparse homotopy algorithm for computing the isolated points in $V_p(\mathbf{F},\mathbf{g})$ which takes advantage of the determinantal structure of the system defining $V_p(\mathbf{F}, \mathbf{g})$ . Its complexity is polynomial in the maximum number of isolated solutions to such systems sharing the same sparsity pattern and in some combinatorial quantities attached to the structure of such systems. It is the first algorithm which takes advantage both on the determinantal structure and sparsity of input polynomials. We also derive complexity bounds for the particular but important case where $\mathbf{g}$ and the columns of $\mathbf{F}$ 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.

preprint2017arXiv

Computing isomorphisms and embeddings of finite fields

Let $\mathbb{F}_q$ be a finite field. Given two irreducible polynomials $f,g$ over $\mathbb{F}_q$ , with $\mathrm{deg} f$ dividing $\mathrm{deg} g$ , the finite field embedding problem asks to compute an explicit description of a field embedding of $\mathbb{F}_q[X]/f(X)$ into $\mathbb{F}_q[Y]/g(Y)$ . When $\mathrm{deg} f = \mathrm{deg} g$ , this is also known as the isomorphism problem. This problem, a special instance of polynomial factorization, plays a central role in computer algebra software. We review previous algorithms, due to Lenstra, Allombert, Rains, and Narayanan, and propose improvements and generalizations. Our detailed complexity analysis shows that our newly proposed variants are at least as efficient as previously known algorithms, and in many cases significantly better. We also implement most of the presented algorithms, compare them with the state of the art computer algebra software, and make the code available as open source. Our experiments show that our new variants consistently outperform available software.

preprint2016arXiv

A Fast Algorithm for Computing the Truncated Resultant

Let P and Q be two polynomials in K[x, y] with degree at most d, where K is a field. Denoting by R $\in$ K[x] the resultant of P and Q with respect to y, we present an algorithm to compute R mod x^k in O~(kd) arithmetic operations in K, where the O~ notation indicates that we omit polylogarithmic factors. This is an improvement over state-of-the-art algorithms that require to compute R in O~(d^3) operations before computing its first k coefficients.

preprint2015arXiv

A Fast Algorithm for Computing the p-Curvature

We design an algorithm for computing the $p$ -curvature of a differential system in positive characteristic $p$ . For a system of dimension $r$ with coefficients of degree at most $d$ , its complexity is $\softO (p d r^ω)$ operations in the ground field (where $ω$ denotes the exponent of matrix multiplication), whereas the size of the output is about $p d r^2$ . Our algorithm is then quasi-optimal assuming that matrix multiplication is (\emph{i.e.} $ω= 2$ ). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.

preprint2014arXiv

A baby step-giant step roadmap algorithm for general algebraic sets

Let $\mathrm{R}$ be a real closed field and $\mathrm{D} \subset \mathrm{R}$ an ordered domain. We give an algorithm that takes as input a polynomial $Q \in \mathrm{D}[X_1,\ldots,X_k]$ , and computes a description of a roadmap of the set of zeros, $\mathrm{Zer}(Q,\mathrm{R}^k)$ , of $Q$ in $\mathrm{R}^k$ . The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain $\mathrm{D}$ , is bounded by $d^{O(k \sqrt{k})}$ , where $d = \mathrm{deg}(Q)\ge 2$ . As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, $\mathrm{Zer}(Q,\mathrm{R}^k)$ , whose complexity is also bounded by $d^{O(k \sqrt{k})}$ , where $d = \mathrm{deg}(Q)\ge 2$ . The best previously known algorithm for constructing a roadmap of a real algebraic subset of $\mathrm{R}^k$ defined by a polynomial of degree $d$ has complexity $d^{O(k^2)}$ .

preprint2014arXiv

A fast algorithm for computing the characteristic polynomial of the p-curvature

We discuss theoretical and algorithmic questions related to the $p$ -curvature of differential operators in characteristic $p$ . Given such an operator $L$ , and denoting by $\Chi(L)$ the characteristic polynomial of its $p$ -curvature, we first prove a new, alternative, description of $\Chi(L)$ . This description turns out to be particularly well suited to the fast computation of $\Chi(L)$ when $p$ is large: based on it, we design a new algorithm for computing $\Chi(L)$ , whose cost with respect to $p$ is $\softO(p^{0.5})$ operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the $p$ -curvature, had merely slightly subquadratic complexity $\softO(p^{1.79})$.

preprint2014arXiv

A Quadratically Convergent Algorithm for Structured Low-Rank Approximation

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix $M$ , the goal is to compute a matrix $M'$ of given rank $r$ in a linear or affine subspace $E$ of matrices (usually encoding a specific structure) such that the Frobenius distance $\lVert M-M'\rVert$ is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank $r$ and the linear/affine subspace $E$ . We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank $r$ matrices in $E$ . To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank Matrix completion (coordinate spaces) and denoising procedures (Hankel matrices). Experimental results give evidence that this all-purpose algorithm is competitive with state-of-the-art numerical methods dedicated to these problems.

preprint2013arXiv

Fast algorithms for ell-adic towers over finite fields

Inspired by previous work of Shoup, Lenstra-De Smit and Couveignes-Lercier, we give fast algorithms to compute in (the first levels of) the ell-adic closure of a finite field. In many cases, our algorithms have quasi-linear complexity.

preprint2012arXiv

Power Series Solutions of Singular (q)-Differential Equations

We provide algorithms computing power series solutions of a large class of differential or $q$ -differential equations or systems. Their number of arithmetic operations grows linearly with the precision, up to logarithmic terms.

preprint2011arXiv

On the complexity of computing with zero-dimensional triangular sets

We study the complexity of some fundamental operations for triangular sets in dimension zero. Using Las-Vegas algorithms, we prove that one can perform such operations as change of order, equiprojectable decomposition, or quasi-inverse computation with a cost that is essentially that of modular composition. Over an abstract field, this leads to a subquadratic cost (with respect to the degree of the underlying algebraic set). Over a finite field, in a boolean RAM model, we obtain a quasi-linear running time using Kedlaya and Umans' algorithm for modular composition. Conversely, we also show how to reduce the problem of modular composition to change of order for triangular sets, so that all these problems are essentially equivalent. Our algorithms are implemented in Maple; we present some experimental results.

preprint2010arXiv

Bit-size estimates for triangular sets in positive dimension

We give bit-size estimates for the coefficients appearing in triangular sets describing positive-dimensional algebraic sets defined over Q. These estimates are worst case upper bounds; they depend only on the degree and height of the underlying algebraic sets. We illustrate the use of these results in the context of a modular algorithm. This extends results by the first and last author, which were confined to the case of dimension 0. Our strategy is to get back to dimension 0 by evaluation and inter- polation techniques. Even though the main tool (height theory) remains the same, new difficulties arise to control the growth of the coefficients during the interpolation process.

preprint2010arXiv

Fast Arithmetics in Artin-Schreier Towers over Finite Fields

An Artin-Schreier tower over the finite field F_p is a tower of field extensions generated by polynomials of the form X^p - X - a. Following Cantor and Couveignes, we give algorithms with quasi-linear time complexity for arithmetic operations in such towers. As an application, we present an implementation of Couveignes' algorithm for computing isogenies between elliptic curves using the p-torsion.

preprint2008arXiv

Fast Conversion Algorithms for Orthogonal Polynomials

We discuss efficient conversion algorithms for orthogonal polynomials. We describe a known conversion algorithm from an arbitrary orthogonal basis to the monomial basis, and deduce a new algorithm of the same complexity for the converse operation.

preprint2008arXiv

Power Series Composition and Change of Basis

Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential, ...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Éric Schost

Research overview

Is this your work?

16 publications

Computing critical points for invariant algebraic systems

Computing syzygies in finite dimension using fast linear algebra

Homotopy techniques for solving sparse column support determinantal polynomial systems

Computing isomorphisms and embeddings of finite fields

A Fast Algorithm for Computing the Truncated Resultant

A Fast Algorithm for Computing the p-Curvature

A baby step-giant step roadmap algorithm for general algebraic sets

A fast algorithm for computing the characteristic polynomial of the p-curvature

A Quadratically Convergent Algorithm for Structured Low-Rank Approximation

Fast algorithms for ell-adic towers over finite fields

Power Series Solutions of Singular (q)-Differential Equations

On the complexity of computing with zero-dimensional triangular sets

Bit-size estimates for triangular sets in positive dimension

Fast Arithmetics in Artin-Schreier Towers over Finite Fields

Fast Conversion Algorithms for Orthogonal Polynomials

Power Series Composition and Change of Basis

See the researcher in context

Building this map preview