Fast multivariate multi-point evaluation revisited
DOI10.1016/J.JCO.2019.04.001zbMATH Open1469.68169OpenAlexW2941649468WikidataQ128004135 ScholiaQ128004135MaRDI QIDQ2283121FDOQ2283121
Authors: Joris van der Hoeven, Grégoire Lecerf 
Publication date: 30 December 2019
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2019.04.001
Recommendations
algorithmcomplexity boundmodular compositionpower projectionmulti-point evaluationKedlaya-Umans algorithm
Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Finite fields (field-theoretic aspects) (12E20) Numerical methods for discrete and fast Fourier transforms (65T50) Computational methods for problems pertaining to field theory (12-08)
Cites Work
- Title not available (Why is that?)
- On fast multiplication of polynomials over arbitrary algebras
- Relax, but don't be too lazy
- Polynomial evaluation and interpolation on special sets of points
- Searching for Primitive Roots in Finite Fields
- Fast polynomial factorization and modular composition
- Fast Algorithms for Manipulating Formal Power Series
- A Gröbner free alternative for polynomial system solving
- Approximate formulas for some functions of prime numbers
- Modern computer algebra
- Faster deterministic integer factorization
- Even faster integer multiplication
- Fast Multiple-Precision Evaluation of Elementary Functions
- Title not available (Why is that?)
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Fast rectangular matrix multiplication and applications
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Title not available (Why is that?)
- On the bit-complexity of sparse polynomial and series multiplication
- Fast computation of continued fraction expansions.
- Multi-point evaluation in higher dimensions
- Title not available (Why is that?)
- A fast numerical algorithm for the composition of power series with complex coefficients
- The truncated fourier transform and applications
- Efficient \(p\)th root computations in finite fields of characteristic \(p\)
- Composing power series over a finite ring in essentially linear time
- Faster polynomial multiplication over finite fields
- Composition modulo powers of polynomials
- A fast algorithm for reversion of power series
- Modular composition via factorization
- Faster integer multiplication using plain vanilla FFT primes
- On the complexity of the Lickteig-Roy subresultant algorithm
- Algorithms – ESA 2004
- Faster sparse multivariate polynomial interpolation of straight-line programs
- Faster integer multiplication using short lattice vectors
Cited In (21)
- Amortized multi-point evaluation of multivariate polynomials
- Algorithms – ESA 2004
- Fast computation of generic bivariate resultants
- Multi-point evaluation in higher dimensions
- Modular composition via factorization
- On the complexity exponent of polynomial system solving
- Fast polynomial factorization and modular composition
- Bivariate polynomial reduction and elimination ideal over finite fields
- A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
- Composition modulo powers of polynomials
- Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
- Fast amortized multi-point evaluation
- Elimination ideal and bivariate resultant over finite fields
- On Isolating Roots in a Multiple Field Extension
- Directed evaluation
- Sparse tensors and subdivision methods for finding the zero set of polynomial equations
- Amortized bivariate multi-point evaluation
- Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology
- Univariate polynomial factorization over finite fields with large extension degree
Uses Software
This page was built for publication: Fast multivariate multi-point evaluation revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283121)
