Search

A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by $n$, the algorithm uses $O(n^{1.43})$ field operations, breaking through the $3/2$ barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require $O(n^{1.63})$ field operations in general, and ${n^{3/2+o(1)}}$ field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in ${n^{5/3+o(1)}}$ operations, while previous ones run in $O(n^2)$ operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation., 78 pages

In this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal is to compute a compact representation of a basis of the nullspace of this matrix.We propose several algorithms in accordance with the structure of the multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.; Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relationsà une ou plusieurs variables. Il généralise celui de calculer une solution à un systèmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution,nous nous attacherons à calculer un ensemble de générateurs possédant de bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses,nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariészéro-dimensionnels.

In this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal is to compute a compact representation of a basis of the nullspace of this matrix.We propose several algorithms in accordance with the structure of the multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.; Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relationsà une ou plusieurs variables. Il généralise celui de calculer une solution à un systèmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution,nous nous attacherons à calculer un ensemble de générateurs possédant de bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses,nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariészéro-dimensionnels.

Linear recurrent sequences are those whose elements are defined as linear combinations of preceding elements, and finding recurrence relations is a fundamental problem in computer algebra. In this paper, we focus on sequences whose elements are vectors over the ring $\mathbb{A} = \mathbb{K}[x]/(x^d)$ of truncated polynomials. Finding the ideal of their recurrence relations has applications such as the computation of minimal polynomials and determinants of sparse matrices over $\mathbb{A}$. We present three methods for finding this ideal: a Berlekamp-Massey-like approach due to Kurakin, one which computes the kernel of some block-Hankel matrix over $\mathbb{A}$ via a minimal approximant basis, and one based on bivariate Pad\'e approximation. We propose complexity improvements for the first two methods, respectively by avoiding the computation of redundant relations and by exploiting the Hankel structure to compress the approximation problem. Then we confirm these improvements empirically through a C++ implementation, and we discuss the above-mentioned applications., Comment: 8 pages, ISSAC 2021

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faug\`ere and Mou's Sparse FGLM algorithm, we use Krylov sequences based on multiplication matrices of $I$ in order to compute a description of its zero set by means of univariate polynomials. Steel recently showed how to use Coppersmith's block-Wiedemann algorithm in this context; he describes an algorithm that can be easily parallelized, but only computes parts of the output in this manner. Using generating series expressions going back to work of Bostan, Salvy, and Schost, we show how to compute the entire output for a small overhead, without making any assumption on the ideal $I$ other than it having dimension zero. We then propose a refinement of this idea that partially avoids the introduction of a generic linear form. We comment on experimental results obtained by an implementation based on the C++ libraries Eigen, LinBox and NTL., Comment: 32 pages, 7 algorithms, 2 tables