Fast amortized multi-point evaluation
From MaRDI portal
Publication:2238846
DOI10.1016/j.jco.2021.101574OpenAlexW3046897419MaRDI QIDQ2238846
Joris van der Hoeven, Grégoire Lecerf
Publication date: 2 November 2021
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2021.101574
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Computational aspects and applications of commutative rings (13Pxx)
Related Items
Univariate polynomial factorization over finite fields with large extension degree, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Amortized multi-point evaluation of multivariate polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Modular composition via factorization
- Solving structured linear systems with large displacement rank
- On fast multiplication of polynomials over arbitrary algebras
- Fast modular transforms
- Fast multiplication of polynomials over fields of characteristic 2
- Efficient computation of zero-dimensional Gröbner bases by change of ordering
- Computing ideals of points
- On the bit-complexity of sparse polynomial and series multiplication
- Polynomial interpolation in several variables
- Computing syzygies in finite dimension using fast linear algebra
- Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
- Fast multivariate multi-point evaluation revisited
- Gröbner bases of ideals defined by functionals with an application to ideals of projective points
- Fast multiplication of large numbers
- On the complexity exponent of polynomial system solving
- Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
- Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations
- Fast Polynomial Factorization and Modular Composition
- Powers of tensors and fast matrix multiplication
- Faster relaxed multiplication
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- On the Complexity of Multivariate Polynomial Division
- What Can (and Can't) we Do with Sparse Polynomials?
- Fast Reduction of Bivariate Polynomials with Respect to Sufficiently Regular Gröbner Bases
- Sub-quadratic time for riemann-roch spaces
- Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
- Algorithms – ESA 2004
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Algorithme de Brill-Noether et codes de Goppa
- Computing generic bivariate Gröbner bases with Mathemagix
