Arrêt de service lundi 11 juillet de 12h30 à 13h : tous les sites du CCSD (HAL, Epiciences, SciencesConf, AureHAL) seront inaccessibles (branchement réseau à modifier)
Accéder directement au contenu Accéder directement à la navigation

# Block-Krylov techniques in the context of sparse-FGLM algorithms

Abstract : Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faugère and Mou's Sparse FGLM algorithm, we use Krylov sequences based on multiplication matrices of $I$ in order to compute a description of its zero set by means of univariate polynomials. Steel recently showed how to use Coppersmith's block-Wiedemann algorithm in this context; he describes an algorithm that can be easily parallelized, but only computes parts of the output in this manner. Using generating series expressions going back to work of Bostan, Salvy, and Schost, we show how to compute the entire output for a small overhead, without making any assumption on the ideal I other than it having dimension zero. We then propose a refinement of this idea that partially avoids the introduction of a generic linear form. We comment on experimental results obtained by an implementation based on the C++ libraries LinBox, Eigen and NTL.
Keywords :
Type de document :
Pré-publication, Document de travail
Domaine :

Littérature citée [49 références]

https://hal-unilim.archives-ouvertes.fr/hal-01661690
Contributeur : Vincent Neiger Connectez-vous pour contacter le contributeur
Soumis le : mardi 15 janvier 2019 - 13:23:45
Dernière modification le : dimanche 26 juin 2022 - 02:36:39

### Fichier

blockKrylov-sparseFGLM.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01661690, version 2

### Citation

Seung Gyu Hyun, Vincent Neiger, Hamid Rahkooy, Éric Schost. Block-Krylov techniques in the context of sparse-FGLM algorithms. 2019. ⟨hal-01661690v2⟩

### Métriques

Consultations de la notice

## 251

Téléchargements de fichiers