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

Vincent Guisse (1)

1 PolSys - Polynomial Systems

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.

Domaines: Calcul formel [cs.SC]

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⟩