Algèbre linéaire dédiée pour les algorithmes Scalar-FGLM et Berlekamp-Massey-Sakata

Vincent Guisse 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : Le contexte général L'algorithme de Berlekamp-Massey ([1], [11]) a été inventé par Berlekamp pour décoder les codes BCH ([5]), puis Massey a montré qu'il permettait de résoudre le problème de devinette de récurrence linéaire pour les suites à un indice. Il a ensuite été étendu par Sakata ([13]) pour résoudre le même problème pour les suites à plusieurs indices (algorithme de Berlekamp-Massey-Sakata, ou BMS). La solution prend alors la forme d'une base de Gröbner de l'idéal des relations d'une table de valeurs de la suite. Il a enfin été légèrement adapté pour permettre le décodage des codes d'évaluations sur un domaine ordonné ([6]). Récemment, dans [3], Faugère, Berthomieu et Boyer on présenté un al-gorithme, Scalar-FGLM, généralisant la version matricielle de l'algorithme de Berlekamp-Massey pour les suites à plusieurs indices. Cette dernière consiste à résoudre un système linéaire de Hankel de taille d, l'ordre de la récurrence. Ceci est possible en complexité en temps O (M(d) log d), où M(d) est le coût du produit de polynômes de degré d (voir [7]). Dans le cas de Scalar-FGLM, on extrait une sous matrice de rang maximal d'une matrice multi-Hankel puis on résout des systèmes faisant intervenir directement cette matrice. Cela est possible en complexité O (M(d) log d) pour l'ordre lexicographique et dans le cas générique (shape position). Cependant, sans cette hypothèse de généricité on ne sait pas résoudre le système linéaire aussi efficacement. Dans [4], les auteurs de Scalar-FGLM l'étendent aux suites linéaires récu-rentes à coefficients polynomiaux, les suites P-récurrentes. Le problème ouvert de savoir si certaines marches de l'espaces sont P-récurrentes ou non pourrait se voir apporter des réponses en cas de progrès pratiques ou théoriques dans la gestion des matrices générées par Scalar-FGLM. Le problème étudié Un premier objectif du stage était d'obtenir une algèbre linéaire plus rapide en pratique ou en théorie pour Scalar-FGLM et ses dérivés. Un second était de rapprocher les descriptions de Scalar-FGLM et de BMS, puisque ces deux algorithmes ont des sorties équivalentes.
Type de document :
Mémoires d'étudiants -- Hal-inria+
Calcul formel [cs.SC]. 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01516249
Contributeur : Jérémy Berthomieu <>
Soumis le : samedi 29 avril 2017 - 15:43:39
Dernière modification le : mardi 17 avril 2018 - 11:25:10
Document(s) archivé(s) le : dimanche 30 juillet 2017 - 12:17:23

Fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01516249, version 1

Collections

Citation

Vincent Guisse. Algèbre linéaire dédiée pour les algorithmes Scalar-FGLM et Berlekamp-Massey-Sakata. Calcul formel [cs.SC]. 2016. 〈hal-01516249〉

Partager

Métriques

Consultations de la notice

160

Téléchargements de fichiers

26