Amortized multi-point evaluation of multivariate polynomials
From MaRDI portal
Publication:2099269
DOI10.1016/j.jco.2022.101693OpenAlexW4225642243MaRDI QIDQ2099269
Joris van der Hoeven, Grégoire Lecerf
Publication date: 23 November 2022
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2022.101693
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On fast multiplication of polynomials over arbitrary algebras
- Fast modular transforms
- Fast multiplication of polynomials over fields of characteristic 2
- Relax, but don't be too lazy
- On the bit-complexity of sparse polynomial and series multiplication
- Fast amortized multi-point evaluation
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast multivariate multi-point evaluation revisited
- Accelerated tower arithmetic
- Fast multiplication of large numbers
- On the complexity exponent of polynomial system solving
- Fast Polynomial Factorization and Modular Composition
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- On the Complexity of Multivariate Polynomial Division
- Polynomial Multiplication over Finite Fields in Time \( O(n \log n \)
- What Can (and Can't) we Do with Sparse Polynomials?
- Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
- Algorithms – ESA 2004
- Algorithme de Brill-Noether et codes de Goppa
