Search

We design and analyze new protocols to verify the correctness of various computations on matrices over the ring F [ x ] of univariate polynomials over a field F. For the sake of efficiency, and because many of the properties we verify are specific to matrices over a principal ideal domain, we cannot simply rely on previously-developed linear algebra protocols for matrices over a field. Our protocols are interactive , often randomized, and feature a constant number of rounds of communication between the Prover and Verifier. We seek to minimize the communication cost so that the amount of data sent during the protocol is significantly smaller than the size of the result being verified, which can be useful when combining protocols or in some multi-party settings. The main tools we use are reductions to existing linear algebra verification protocols and a new protocol to verify that a given vector is in the F [ x ] -row space of a given matrix. [ABSTRACT FROM AUTHOR]

Consider a zero-dimensional ideal I in K [ X 1 , ... , X n ]. Inspired by Faugère 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. [ABSTRACT FROM AUTHOR]

In this article, we design fast algorithms for the computation of approximant bases in shifted Popov normal form. We first recall the algorithm known as PM-Basis , which will be our second fundamental engine after polynomial matrix multiplication: most other fast approximant basis algorithms basically aim at efficiently reducing the input instance to instances for which PM-Basis is fast. Such reductions usually involve partial linearization techniques due to Storjohann, which have the effect of balancing the degrees and dimensions in the manipulated matrices. Following these ideas, Zhou and Labahn gave two algorithms which are faster than PM-Basis for important cases including Hermite-Padé approximation, yet only for shifts whose values are concentrated around the minimum or the maximum value. The three mentioned algorithms were designed for balanced orders and compute approximant bases that are generally not normalized. Here, we show how they can be modified to return the shifted Popov basis without impact on their cost bound; besides, we extend Zhou and Labahn's algorithms to arbitrary orders. Furthermore, we give an algorithm which handles arbitrary shifts with one extra logarithmic factor in the cost bound compared to the above algorithms. To the best of our knowledge, this improves upon previously known algorithms for arbitrary shifts, including for particular cases such as Hermite-Padé approximation. This algorithm is based on a recent divide and conquer approach which reduces the general case to the case where information on the output degree is available. As outlined above, we solve the latter case via partial linearizations and PM-Basis. [ABSTRACT FROM AUTHOR]

We consider the problem of computing univariate polynomial matrices over a field that represent minimal solution bases for a general interpolation problem, some forms of which are the vector M-Padé approximation problem in Van Barel and Bultheel (1992) and the rational interpolation problem in Beckermann and Labahn (2000) . Particular instances of this problem include the bivariate interpolation steps of Guruswami–Sudan hard-decision and Kötter–Vardy soft-decision decodings of Reed–Solomon codes, the multivariate interpolation step of list-decoding of folded Reed–Solomon codes, and Hermite–Padé approximation. In the mentioned references, the problem is solved using iterative algorithms based on recurrence relations. Here, we discuss a fast, divide-and-conquer version of this recurrence, taking advantage of fast matrix computations over the scalars and over the polynomials. This new algorithm is deterministic, and for computing shifted minimal bases of relations between m vectors of size σ it uses O ˜ ( m ω − 1 ( σ + | s | ) ) field operations, where ω is the exponent of matrix multiplication, and | s | is the sum of the entries of the input shift s , with min ⁡ ( s ) = 0 . This complexity bound improves in particular on earlier algorithms in the case of bivariate interpolation for soft decoding, while matching fastest existing algorithms for simultaneous Hermite–Padé approximation. [ABSTRACT FROM AUTHOR]

Given a nonsingular n × n matrix of univariate polynomials over a field K , we give fast and deterministic algorithms to compute its determinant and its Hermite normal form. Our algorithms use O ˜ ( n ω ⌈ s ⌉ ) operations in K , where s is bounded from above by both the average of the degrees of the rows and that of the columns of the matrix and ω is the exponent of matrix multiplication. The soft- O notation indicates that logarithmic factors in the big- O are omitted while the ceiling function indicates that the cost is O ˜ ( n ω ) when s = o ( 1 ) . Our algorithms are based on a fast and deterministic triangularization method for computing the diagonal entries of the Hermite form of a nonsingular matrix. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices. [ABSTRACT FROM AUTHOR]

We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a K X 1 , ... , X r -module M of finite dimension D as a K -vector space, and given elements f 1 , ... , f m in M , the problem is to compute syzygies between the f i 's, that is, polynomials (p 1 , ... , p m) in K X 1 , ... , X r m such that p 1 f 1 + ⋯ + p m f m = 0 in M. Assuming that the multiplication matrices of the r variables with respect to some basis of 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 K , where ω is the exponent of matrix multiplication. Furthermore, assuming that M is itself given as M = K X 1 , ... , X r n ∕ N , under some assumptions on N we show that these multiplication matrices can be computed from a Gröbner basis of N within the same complexity bound. In particular, taking n = 1 , m = 1 and f 1 = 1 in 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. [ABSTRACT FROM AUTHOR]

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 \mathcal O^\sim(\ell ^\omega -1m^2(n-k)) , where $\ell, m,n$ , and $k$ are the list size, the multiplicity, the number of sample points, and the dimension of the code, and $\omega $ is the exponent of linear algebra; this accelerates the previously fastest known algorithm by a factor of $\ell / m$ . [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]