International audience

Computing recurrence relations for sequences is a central problem in computer algebra, with applications in error-correcting codes, Gröbner basis computation, and sparse interpolation. While uni-indexed C-recursive sequences benefit from quasi-linear algorithms leveraging the half-gcd method, the extension to multi-indexed sequences remains computationally challenging. Existing methods for bi-indexed sequences achieve quadratic complexity at best, limiting their practical use.

In this paper, we deal with the problem of simultaneous reconstruction of a vector of rational numbers, given modular reductions containing errors (SRNRwE). Our methods apply as well to the simultaneous reconstruction of rational functions given evaluations containing errors (SRFRwE), improving known results [7, 9]. In the latter case, one can take advantage of techniques from coding theory [4, 10] and provide an algorithm that extends classical Reed-Solomon decoding. In recent works [7, 9], interleaved Reed-Solomon codes [3, 19] are used to correct beyond the unique decoding capability in the case of random errors at the price of positive but small failure probability. Our first contribution is to extend these works to the simultaneous reconstruction with errors of rational numbers instead of functions. Thus considering rational number codes [16], we provide an algorithm decoding beyond the unique decoding capability and, as a central result of this paper, we analyze in detail its failure probability. Our analysis generalizes for the first time the best known analysis for interleaved Reed-Solomon codes [19] to SRFRwE, improving on the existing bound [8], to interleaved Chinese remainder codes, also improving the known bound [1], and finally for the first time to SRNRwE.

To date, Li et al. have presented the only decoder for Interleaved Chinese Remainder (ICR) codes [1]. The core of their ICR decoder is to find a short vector in a lattice using the LLL algorithm [2]. However, their analysis of the decoding failure is partially heuristic. In this work, we present a new analysis of their LLL-based decoder that gives a proved upper bound on its decoding failure probability.

This paper deals with the polynomial linear system solving with errors (PLSwE) problem. More specifically, we solve linear systems with univariate polynomial coefficients via an evaluation-interpolation technique assuming that errors can occur before the interpolation step. In this framework, the number of evaluations needed to recover the solution depends on the parameters of the linear system (degrees, size) and on the number of errors.

This paper focuses on the problem of reconstructing a vector of rational functions given some evaluations, or more generally given their remainders modulo different polynomials. The special case of rational functions sharing the same denominator, a.k.a. Simultaneous Rational Function Reconstruction (SRFR), has many applications from linear system solving to coding theory, provided that SRFR has a unique solution. The number of unknowns in SRFR is smaller than for a general vector of rational function. This allows one to reduce the number of evaluation points needed to guarantee the existence of a solution, possibly losing its uniqueness. In this work, we prove that uniqueness is guaranteed for a generic instance.

In this paper we present a new algorithm for Polynomial Linear System Solving (via evaluation/interpolation) with errors. In this scenario, errors can occur in the black box evaluation step. We improve the bound on the number of errors that we can correct, using techniques inspired by the decoding procedure of Interleaved Reed-Solomon Codes.

We present an algorithm for simultaneous conversions between a given set of integers and their Residue Number System representations based on linear algebra. We provide a highly optimized implementation of the algorithm that exploits the computational features of modern processors. The main application of our algorithm is matrix multiplication over integers. Our speed-up of the conversions to and from the Residue Number System significantly improves the overall running time of matrix multiplication.

There exists a vast literature dedicated to algorithms for structured matrices, but relatively few descriptions of actual implementations and their practical performance in symbolic computation. In this paper, we consider the problem of solving Cauchy-like systems, and its application to mosaic Toeplitz systems, in two contexts: first in the unit cost model (which is a good model for computations over finite fields), then over Q. We introduce new variants of previous algorithms and describe an implementation of these techniques and its practical behavior. We pay a special attention to particular cases such as the computation of algebraic approximants.

Order bases are a fundamental tool for linear algebra with polynomial coefficients. In particular, block Wiedemann methods are nowadays able to tackle large sparse matrix problems because they benefit from fast order basis algorithms. However, such fast algorithms suffer from two practical drawbacks: they are not designed for early termination and often require more knowledge on the input than necessary. In this paper, we propose an online algorithm for order basis which allows for both early termination and minimal input requirement while keeping quasi-optimal complexity in the order. Using this algorithm inside block Wiedemann methods leads to an improvement of their practical performance by a constant factor.

In this paper, we consider the problem of efficient computations with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for multiplying polynomials supported on a lattice.

We give an algorithm for solving bivariate polynomial systems over either k(T)[X,Y] or Q[X,Y] using a combination of lifting and modular composition techniques.

In a previous article [1], an implementation of lazy p-adic integers with a multiplication of quasi-linear complexity, the so-called relaxed product, was presented. Given a ring R and an element p in R, we design a relaxed Hensel lifting for algebraic systems from R/ (p) to the p-adic completion Rp of R. Thus, any root of linear and algebraic regular systems can be lifted with a quasi-optimal complexity. We report our implementations in C++ within the computer algebra system Mathemagix and compare them with Newton operator. As an application, we solve linear systems over the integers and compare the running times with Linbox and IML.

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.

Let k be a field and let f ∈ k [T] be a polynomial of degree n. The universal decomposition algebra A is the quotient of k [X1,...,Xn] by the ideal of symmetric relations (those polynomials that vanish on all permutations of the roots of f). We show how to obtain efficient algorithms to compute in A. We use a univariate representation of A, i.e. an isomorphism of the form A k[T]/Q(T), since in this representation, arithmetic operations in A are known to be quasi-optimal. We give details for two related algorithms, to find the isomorphism above, and to compute the characteristic polynomial of any element of A.