International audience

International audience

In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in$\tilde {\mathcal {O}} (s^{2}\ell ^{\omega -1}\mu ^{\omega -1}(n+g) + \ell ^{\omega } \mu ^{\omega })$operations in the underlying finite field, wherenis the code length,gis the genus of the function field used to construct the code,sis the multiplicity parameter,$\ell $is the designed list size and$\mu $is the smallest positive element in the Weierstrass semigroup of some chosen place.

International audience

Krylov methods rely on iterated matrix-vector products $A^k u_j$ for an $n\times n$ matrix $A$ and vectors $u_1,\ldots,u_m$. The space spanned by all iterates $A^k u_j$ admits a particular basis -- the \emph{maximal Krylov basis} -- which consists of iterates of the first vector $u_1, Au_1, A^2u_1,\ldots$, until reaching linear dependency, then iterating similarly the subsequent vectors until a basis is obtained. Finding minimal polynomials and Frobenius normal forms is closely related to computing maximal Krylov bases. The fastest way to produce these bases was, until this paper, Keller-Gehrig's 1985 algorithm whose complexity bound $O(n^\omega \log(n))$ comes from repeated squarings of $A$ and logarithmically many Gaussian eliminations. Here $\omega>2$ is a feasible exponent for matrix multiplication over the base field. We present an algorithm computing the maximal Krylov basis in $O(n^\omega\log\log(n))$ field operations when $m \in O(n)$, and even $O(n^\omega)$ as soon as $m\in O(n/\log(n)^c)$ for some fixed real $c>0$. As a consequence, we show that the Frobenius normal form together with a transformation matrix can be computed deterministically in $O(n^\omega (\log\log(n))^2)$, and therefore matrix exponentiation~$A^k$ can be performed in the latter complexity if $\log(k) \in O(n^{\omega-1-\varepsilon})$ for some fixed $\varepsilon>0$. A key idea for these improvements is to rely on fast algorithms for $m\times m$ polynomial matrices of average degree $n/m$, involving high-order lifting and minimal kernel bases.

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.

The Nth power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in N. When Fast Fourier Transform (FFT) is available, the resulting complexity is softly linear in N, i.e. linear in N with extra logarithmic factors. We show that it is possible to beat binary powering, by an algorithm whose complexity is purely linear in N, even in absence of FFT. The key result making this improvement possible is that the entries of the Nth power of a polynomial matrix satisfy linear differential equations with polynomial coefficients whose orders and degrees are independent of N. Similar algorithms are proposed for two related problems: computing the Nth term of a C-finite sequence of polynomials, and modular exponentiation to the power N for bivariate polynomials.

We consider the problem of computing a grevlex Gröbner basis for the set Fr(M) of minors of size r of an n × n matrix M of generic linear forms over a field of characteristic zero or large enough. Such sets are not regular sequences; in fact, the ideal ⟨Fr(M)⟩ cannot be generated by a regular sequence. As such, when using the general-purpose algorithm F5 to find the sought Gröbner basis, some computing time is wasted on reductions to zero. We use known results about the first syzygy module of Fr(M) to refine the F5 algorithm in order to detect more reductions to zero. In practice, our approach avoids a significant number of reductions to zero. In particular, in the case r = n − 2, we prove that our new algorithm avoids all reductions to zero, and we provide a corresponding complexity analysis which improves upon the previously known estimates.

Solving zero-dimensional polynomial systems using Gröbner bases is usually done by, first, computing a Gröbner basis for the degree reverse lexicographic order, and next computing the lexicographic Gröbner basis with a change of order algorithm. Currently, the change of order now takes a significant part of the whole solving time for many generic instances. Like the fastest known change of order algorithms, this work focuses on the situation where the ideal defined by the system satisfies natural properties which can be recovered in generic coordinates. First, the ideal has a shape lexicographic Gröbner basis. Second, the set of leading terms with respect to the degree reverse lexicographic order has a stability property; in particular, the multiplication matrix can be read on the input Gröbner basis. The current fastest algorithms rely on the sparsity of this matrix. Actually, this sparsity is a consequence of an algebraic structure, which can be exploited to represent the matrix concisely as a univariate polynomial matrix. We show that the Hermite normal form of that matrix yields the sought lexicographic Gröbner basis, under assumptions which cover the shape position case. Under some mild assumption implying n≤t, the arithmetic complexity of our algorithm is O~(tω-1D), where n is the number of variables, t is a sparsity indicator of the aforementioned matrix, D is the degree of the zero-dimensional ideal under consideration, and ω is the exponent of matrix multiplication. This improves upon both state-of-the-art complexity bounds O~(tD2) and O~(Dω, since ω<3 and t≤D. Practical experiments, based on the libraries msolve and PML, confirm the high practical benefit.

Consider a matrix F ε K [x]^mxn of univariate polynomials over a field K. We study the problem of computing the column rank profile of F. To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of F with a rank-sensitive complexity of O~ (rw-2n(m+d)) operations in K. Here, D is the sum of row degrees of F, w is the exponent of matrix multiplication, and O~ (.) hides logarithmic factors.

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 𝔸=𝕂[x] /{xd} 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 𝔸. 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 𝔸 via a minimal approximant basis, and one based on bivariate Padé 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.

Let f1, ..., fm be elements in a quotient Rn/N which has finite dimension as a K-vector space, where R = K[X1, ..., Xr] and N is an R-submodule of Rn. We address the problem of computing a Gröbner basis of the module of syzygies of (f1, ..., fm), that is, of vectors (p1, ..., pm) ∈ Rm such that p1f1 + ... + pm fm = 0.

Suppose K is a large enough field and P ⊂ K2 is a fixed, generic set of points which is available for precomputation. We introduce a technique called reshaping which allows us to design quasi-linear algorithms for both: computing the evaluations of an input polynomial f ∈ K [x, y] at all points of P and computing an interpolant f ∈ K[x, y] which takes prescribed values on P and satisfies an input y-degree bound. Our genericity assumption is explicit and we prove that it holds for most point sets over a large enough field. If P violates the assumption, our algorithms still work and the performance degrades smoothly according to a distance from being generic. To show that the reshaping technique may have an impact on other related problems, we apply it to modular composition: suppose generic polynomials M ∈ K[x] and A ∈ K[x] are available for precomputation, then given an input f ∈ K[x, y] we show how to compute f (x, A(x)) rem M(x) in quasi-linear time.

Complexity bounds for many problems on matrices with univariate polynomial entries have been improved in the last few years. Still, for most related algorithms, efficient implementations are not available, which leaves open the question of the practical impact of these algorithms, e.g. on applications such as decoding some error-correcting codes and solving polynomial systems or structured linear systems. In this paper, we discuss implementation aspects for most fundamental operations: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, determinant, and basis reduction. We focus on prime fields with a word-size modulus, relying on Shoup's C++ library NTL. Combining these new tools to implement variants of Villard's algorithm for the resultant of generic bivariate polynomials (ISSAC 2018), we get better performance than the state of the art for large parameters.

For a given computational problem, a certificate is a piece of data that one (the prover) attaches to the output with the aim of allowing efficient verification (by the verifier) that this output is correct. Here, we consider the minimal approximant basis problem, for which the fastest known algorithms output a polynomial matrix of dimensions m x m and average degree D/m using O~(mømega D/m) field operations. We propose a certificate which, for typical instances of the problem, is computed by the prover using O(mømega D/m) additional field operations and allows verification of the approximant basis by a Monte Carlo algorithm with cost bound O(mømega + m D). Besides theoretical interest, our motivation also comes from the fact that approximant bases arise in most of the fastest known algorithms for linear algebra over the univariate polynomials; thus, this work may help in designing certificates for other polynomial matrix computations. Furthermore, cryptographic challenges such as breaking records for discrete logarithm computations or for integer factorization rely in particular on computing minimal approximant bases for large instances: certificates can then be used to provide reliable computation on outsourced and error-prone clusters.

We consider the computation of two normal forms for matrices over the univariate polynomials: the Popov form and the Hermite form. For matrices which are square and nonsingular, deterministic algorithms with satisfactory cost bounds are known. Here, we present deterministic, fast algorithms for rectangular input matrices. The obtained cost bound for the Popov form matches the previous best known randomized algorithm, while the cost bound for the Hermite form improves on the previous best known ones by a factor which is at least the largest dimension of the input matrix.

We improve previously known lower bounds for the minimum distance of certain two-point AG codes constructed using a Generalized Giulietti-Korchmaros curve (GGK). Castellanos and Tizziotti recently described such bounds for two-point codes coming from the Giulietti-Korchmaros curve. Our results completely cover and in many cases improve on their results, using different techniques, while also supporting any GGK curve. Our method builds on the order bound for AG codes: to enable this, we study certain Weierstrass semigroups. This allows an efficient algorithm for computing our improved bounds. We find several new improvements upon the MinT minimum distance tables.

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field K. More precisely, given a precision d, and a polynomial Q whose coefficients are power series in x, the algorithm computes a representation of all power series f(x) such that Q(f(x)) = 0 mod xd. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled. The cost bound for our algorithm matches the worst-case input and output size d deg(Q), up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of d and deg(Q). Our algorithm is a refinement of a divide & conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.

We study the computation of canonical bases of sets of univariate relations (p1,...,pm) ∈ K[x]m such that p1 f1 + ⋯ + pm fm = 0; here, the input elements f1,...,fm are from a quotient K[x]n/M, where M is a K[x]-module of rank n given by a basis M ∈ K[x]n x n in Hermite form. We exploit the triangular shape of M to generalize a divide-and-conquer approach which originates from fast minimal approximant basis algorithms. Besides recent techniques for this approach, we rely on high-order lifting to perform fast modular products of polynomial matrices of the form P F mod M.

We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Pade approximation and constrained multivariate interpolation, and has applications in coding theory and security. This problem asks to find univariate polynomial relations between m vectors of size σ; these relations should have small degree with respect to an input degree shift. For an arbitrary shift, we propose an algorithm for the computation of an interpolation basis in shifted Popov normal form with a cost of O~(mω-1 σ) field operations, where ω is the exponent of matrix multiplication and the notation O~(·) indicates that logarithmic terms are omitted.

We give a Las Vegas algorithm which computes the shifted Popov form of an m x m nonsingular polynomial matrix of degree d in expected ~O(mω d) field operations, where ω is the exponent of matrix multiplication and ~O(·) indicates that logarithmic factors are omitted. This is the first algorithm in ~O(mω d) for shifted row reduction with arbitrary shifts.

The interpolation step in the Guruswami-Sudan algorithm is a bivariate interpolation problem with multiplicities commonly solved in the literature using either structured linear algebra or basis reduction of polynomial lattices. This problem has been extended to three or more variables; for this generalization, all fast algorithms proposed so far rely on the lattice approach. In this paper, we reduce this multivariate interpolation problem to a problem of simultaneous polynomial approximations, which we solve using fast structured linear algebra. This improves the best known complexity bounds for the interpolation step of the list-decoding of Reed-Solomon codes, Parvaresh-Vardy codes, and folded Reed-Solomon codes. In particular, for Reed-Solomon list-decoding with re-encoding, our approach has complexity O~(ℓω-1m2(n - k)), where ℓ, m, n, and k are the list size, the multiplicity, the number of sample points, and the dimension of the code, and ω is the exponent of linear algebra; this accelerates the previously fastest known algorithm by a factor of ℓ/m.