Skip to Main content Skip to Navigation
Master thesis

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.
Document type :
Master thesis
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01516249
Contributor : Jérémy Berthomieu <>
Submitted on : Saturday, April 29, 2017 - 3:43:39 PM
Last modification on : Friday, May 21, 2021 - 3:38:23 PM
Long-term archiving on: : Sunday, July 30, 2017 - 12:17:23 PM

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01516249, version 1

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⟩

Share

Metrics

Record views

252

Files downloads

329