Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants - Université de Limoges Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants

Résumé

Complexity bounds for many problems about matrices with univariate polynomial entries have been improved in the last few years. Still, for most recent algorithms, efficient implementations are not yet available. This leaves open the question of the practical impact of these algorithms on potential applications, which include decoding some error-correcting codes and solving polynomial systems or structured linear systems. In this paper, we describe the implementation of some of the most fundamental algorithms for polynomial matrices: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, and determinant. Our work currently focuses on prime fields with a word-size modulus and is based on Shoup's C++ library NTL. We combine these new tools to implement variants of Villard's recent algorithm for the resultant of generic bivariate polynomials (ISSAC 2018), and exhibit parameter ranges for which they outperform previous state of the art.
Fichier principal
Vignette du fichier
pml.pdf (806.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01995873 , version 1 (27-01-2019)
hal-01995873 , version 2 (10-05-2019)

Identifiants

Citer

Seung Gyu Hyun, Vincent Neiger, Éric Schost. Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants. 2019. ⟨hal-01995873v2⟩
238 Consultations
480 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More