Fast multivariate multi-point evaluation revisited

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

zbMATH Keywords

algorithmcomplexity boundmodular compositionpower projectionmulti-point evaluationKedlaya-Umans algorithm

Mathematics Subject Classification ID

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 (14)

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 ⋮ Bivariate polynomial reduction and elimination ideal over finite fields ⋮ Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities ⋮ Sparse tensors and subdivision methods for finding the zero set of polynomial equations ⋮ Amortized bivariate multi-point evaluation ⋮ 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

• Unnamed Item

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

This page was built for publication: Fast multivariate multi-point evaluation revisited