5 papers · 1 filter
A complexity analysis of the F4 Gröbner basis algorithm with tracer data
Robin Kouba, Vincent Neiger, Mohab Safey El Din
We provide a new complexity bound for the computation of grevlex Gröbner bases in the generic zero-dimensional case, relying on Moreno-SocÃas' conjecture. We first formalize a pr…
Matrices with displacement structure: a deterministic approach for linear systems and nullspace bases
Sara Khichane, Vincent Neiger
The fastest known algorithms for dealing with structured matrices, in the sense of the displacement rank measure, are randomized. For handling classical displacement structures, th…
Computing submatrices of the Hermite normal form of a structured polynomial matrix
Jérémy Berthomieu, Vincent Neiger, Hugo Passe
Following several decades of successive algorithmic improvements, works from the 2010s have showed how to compute the Hermite normal form (HNF) of a univariate polynomial matrix wi…
Faster modular composition using two relation matrices
Vincent Neiger, Bruno Salvy, Ãric Schost +1
Modular composition is the problem of computing the composition of two univariate polynomials modulo a third one. For a long time, the fastest algebraic algorithm for this problem…
Computing Krylov iterates in the time of matrix multiplication
Vincent Neiger, Clément Pernet, Gilles Villard
Krylov methods rely on iterated matrix-vector products for an matrix and vectors . The space spanned by all iterates admits a pa…