Fast multivariate multi-point evaluation revisited
From MaRDI portal
Publication:2283121
DOI10.1016/j.jco.2019.04.001zbMath1469.68169OpenAlexW2941649468WikidataQ128004135 ScholiaQ128004135MaRDI QIDQ2283121
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
algorithmcomplexity boundmodular compositionpower projectionmulti-point evaluationKedlaya-Umans algorithm
Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Numerical methods for discrete and fast Fourier transforms (65T50) Finite fields (field-theoretic aspects) (12E20) Computational methods for problems pertaining to field theory (12-08)
Related Items
On the complexity exponent of polynomial system solving, On Isolating Roots in a Multiple Field Extension, Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, Elimination ideal and bivariate resultant over finite fields, Directed evaluation, Univariate polynomial factorization over finite fields with large extension degree, Fast amortized multi-point evaluation, Fast computation of generic bivariate resultants, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Amortized multi-point evaluation of multivariate polynomials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Even faster integer multiplication
- Modular composition via factorization
- Efficient \(p\)th root computations in finite fields of characteristic \(p\)
- A fast numerical algorithm for the composition of power series with complex coefficients
- On fast multiplication of polynomials over arbitrary algebras
- Composing power series over a finite ring in essentially linear time
- Fast rectangular matrix multiplication and applications
- On the complexity of the Lickteig-Roy subresultant algorithm
- Relax, but don't be too lazy
- On the bit-complexity of sparse polynomial and series multiplication
- Multi-point evaluation in higher dimensions
- Polynomial evaluation and interpolation on special sets of points
- Fast computation of continued fraction expansions.
- Approximate formulas for some functions of prime numbers
- Faster sparse multivariate polynomial interpolation of straight-line programs
- Faster deterministic integer factorization
- Modern Computer Algebra
- Faster Polynomial Multiplication over Finite Fields
- Fast Polynomial Factorization and Modular Composition
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Searching for Primitive Roots in Finite Fields
- Fast Multiple-Precision Evaluation of Elementary Functions
- Fast Algorithms for Manipulating Formal Power Series
- The truncated fourier transform and applications
- Faster integer multiplication using plain vanilla FFT primes
- Composition Modulo Powers of Polynomials
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Algorithms – ESA 2004
- A fast algorithm for reversion of power series
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- A Gröbner free alternative for polynomial system solving
- Faster integer multiplication using short lattice vectors
