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

Abstract : 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.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [55 références]  Voir  Masquer  Télécharger

https://hal-unilim.archives-ouvertes.fr/hal-01995873
Contributeur : Vincent Neiger <>
Soumis le : vendredi 10 mai 2019 - 21:32:57
Dernière modification le : vendredi 5 juillet 2019 - 12:02:43

Fichier

pml.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

101