69 citations · 167 across the 27 of their papers we have counts for
34 papers
Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants
Vincent Neiger, Mohab Safey El Din, Kevin Tran
When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the h…
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 prop…
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…
Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computations
Sriram Gopalakrishnan, Vincent Neiger, Mohab Safey El Din
Given polynomials and , all in for some field , we consider the problem of computing the critical points of the restriction of …