What can (and can't) we do with sparse polynomials?

DOI10.1145/3208976.3209027MaRDI QIDQ5120174zbMATH OpenOpenAlexWikidataFDO

Authors Daniel S. Roche

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.08289

zbMATH Keywords

arithmeticfactorizationinterpolationsparse polynomial

Mathematics Subject Classification ID

Computational methods for problems pertaining to field theory (12-08) Symbolic computation and algebraic computation (68W30)

Abstract: Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.

Recommendations

• scientific article; zbMATH DE number 503193
• Sparse polynomials in FLINT
• Computing sparse multiples of polynomials
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Computing sparse multiples of polynomials

Cited in

(26)

• Amortized multi-point evaluation of multivariate polynomials
• Polynomial modular product verification and its implications
• Termination of polynomial loops
• Fast amortized multi-point evaluation
• Factoring multivariate polynomials represented by black boxes: a Maple + C implementation
• Output-sensitive algorithms for sumset and sparse polynomial multiplication
• scientific article; zbMATH DE number 503193 (Why is no real title available?)
• On the evaluation of some sparse polynomials
• Implementing the tangent Graeffe root finding method
• Sparse polynomials in FLINT
• A New Black Box Factorization Algorithm - the Non-monic Case
• Methodologies of Symbolic Computation
• Removing additive structure in 3SUM-based reductions
• Interpolation by decomposable univariate polynomials
• Practical algebraic calculus and Nullstellensatz with the checkers Pacheck and Pastèque and Nuss-Checker
• Fast interpolation of multivariate polynomials with sparse exponents
• Sparse multiplication of multivariate linear differential operators
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Sparse polynomial interpolation: faster strategies over finite fields
• Termination of triangular polynomial loops
• Factoring sparse polynomials fast
• New bounds on quotient polynomials with applications to exact division and divisibility testing of sparse polynomials
• A new bound on cofactors of sparse polynomials
• Towards a library for straight-line programs
• Fast n-fold Boolean convolution via additive combinatorics
• Parallel evaluation of sparse polynomials; based on Estrin's algorithm: conception and analysis of schedulings

This page was built for publication: What can (and can't) we do with sparse polynomials?

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