Amortized multi-point evaluation of multivariate polynomials

DOI10.1016/J.JCO.2022.101693MaRDI QIDQ2099269zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

complexitymultivariate polynomialmulti-point evaluationGröbner bases

Mathematics Subject Classification ID

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)

Recommendations

• Algorithms – ESA 2004
• Multi-point evaluation in higher dimensions
• Evaluation of Multivariate Polynomials and Their Derivatives
• Fast multivariate multi-point evaluation revisited
• Efficient evaluation of large polynomials

Cites work

• scientific article; zbMATH DE number 3935185 (Why is no real title available?)
• scientific article; zbMATH DE number 3539809 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• Accelerated tower arithmetic
• Algorithme de Brill-Noether et codes de Goppa
• Algorithms – ESA 2004
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• Fast amortized multi-point evaluation
• Fast modular transforms
• Fast multiplication of large numbers
• Fast multiplication of polynomials over fields of characteristic 2
• Fast multivariate multi-point evaluation revisited
• Fast polynomial factorization and modular composition
• Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
• Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• On fast multiplication of polynomials over arbitrary algebras
• On the bit-complexity of sparse polynomial and series multiplication
• On the complexity exponent of polynomial system solving
• On the complexity of multivariate polynomial division
• Polynomial multiplication over finite fields in time \(O(n\log n)\)
• Relax, but don't be too lazy
• What can (and can't) we do with sparse polynomials?

Cited in

(4)

• Algorithms – ESA 2004
• Efficient evaluation of large polynomials
• Fast multivariate multi-point evaluation revisited
• Sparse tensors and subdivision methods for finding the zero set of polynomial equations

This page was built for publication: Amortized multi-point evaluation of multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099269)