Algorithms for zero-dimensional ideals using linear recurrent sequences

2017/07/06 by Neiger, Vincent, Rahkooy, Hamid, Schost, Éric
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1707.01971

Abstract

Inspired by Faugère and Mou's sparse FGLM algorithm, we show how using linear recurrent multi-dimensional sequences can allow one to perform operations such as the primary decomposition of an ideal, by computing the annihilator of one or several such sequences.

Related

• Block-Krylov techniques in the context of sparse-FGLM algorithms
• In-depth comparison of the Berlekamp -- Massey -- Sakata and the Scalar-FGLM algorithms: the non adaptive variants
• Algorithms for Linearly Recurrent Sequences of Truncated Polynomials
• On Recurrence Relations of Multi-dimensional Sequences
• An Alternative Method for Primary Decomposition of Zero-dimensional Ideals over Finite Fields