Fast interpolation of multivariate polynomials with sparse exponents

DOI10.1016/J.JCO.2024.101922MaRDI QIDQ6665433zbMATH OpenFDO

Authors Joris van der Hoeven, Grégoire Lecerf

Publication date 17 January 2025

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCO.2024.101922

zbMATH Keywords

algorithmcomplexitycomputer algebrasparse polynomial interpolation

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Numerical interpolation (65D05) General topics in the theory of algorithms (68W01)

Cites work

• A fast parallel sparse polynomial GCD algorithm
• A partial Bombieri-Vinogradov theorem with explicit constants
• Approximate formulas for some functions of prime numbers
• Dagwood
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Faster sparse multivariate polynomial interpolation of straight-line programs
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• scientific article; zbMATH DE number 871950 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Interpolation of polynomials given by straight-line programs
• Majorations Explicites Pour le Nombre de Diviseurs de N
• Modern computer algebra
• Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation
• Modular SIMD arithmetic in \textsc{Mathemagix}
• Multivariate sparse interpolation using randomized Kronecker substitutions
• On the bit-complexity of sparse polynomial and series multiplication
• PRIMES is in P
• Randomized root finding over finite FFT-fields using tangent Graeffe transforms
• Simultaneous conversions with the residue number system using linear algebra
• Sparse interpolation over finite fields via low-order roots of unity
• Sparse multivariate Hensel lifting: a high-performance design and implementation
• Sparse polynomial arithmetic with the BPAS library
• Sparse polynomial interpolation over fields with large or zero characteristic
• Sparse polynomials in FLINT
• The complexity of sparse polynomial interpolation over finite fields
• Using sparse interpolation to solve multivariate Diophantine equations
• What can (and can't) we do with sparse polynomials?

Cited in

(2)

• A new black box GCD algorithm using Hensel lifting
• Factoring sparse polynomials fast

This page was built for publication: Fast interpolation of multivariate polynomials with sparse exponents

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