On the bit-complexity of sparse polynomial and series multiplication

DOI10.1016/j.jsc.2012.06.004zbMath1261.65017OpenAlexW2010953531MaRDI QIDQ1930169

Joris van der Hoeven, Grégoire Lecerf

Publication date: 10 January 2013

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2012.06.004

zbMATH Keywords

algorithmcomputational complexitypolynomial factorizationpower seriessparse multiplicationmulti-point evaluation

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Polynomials, factorization in commutative rings (13P05) Complexity and performance of numerical algorithms (65Y20)

Related Items (12)

Multi-key Homomorphic Authenticators ⋮ Multi-point evaluation in higher dimensions ⋮ On the Complexity of Multivariate Polynomial Division ⋮ Fast amortized multi-point evaluation ⋮ A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ⋮ A fast parallel sparse polynomial GCD algorithm ⋮ Multilinear polynomial systems: root isolation and bit complexity ⋮ Fast multivariate multi-point evaluation revisited ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ Accelerated tower arithmetic ⋮ Amortized multi-point evaluation of multivariate polynomials ⋮ Polynomial modular product verification and its implications

Uses Software

• gmp
• TRIP

This page was built for publication: On the bit-complexity of sparse polynomial and series multiplication