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

Consider a zero-dimensional ideal I in K[X1,…,Xn]. 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 Coppersmit...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2020-05, Vol.98, p.163-191
Main Authors: Hyun, Seung Gyu, Neiger, Vincent, Rahkooy, Hamid, Schost, Éric
Format: Article
Language:English
Subjects:
Block-Krylov algorithms
Polynomial systems
Sparse FGLM
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a zero-dimensional ideal I in K[X1,…,Xn]. 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 Eigen, LinBox and NTL.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2019.07.010