Output-sensitive algorithms for sumset and sparse polynomial multiplication

DOI10.1145/2755996.2756653MaRDI QIDQ2819733zbMATH OpenOpenAlexFDO

Authors Andrew Arnold, Daniel S. Roche

Publication date 29 September 2016

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

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

zbMATH Keywords

computational complexityMinkowski sumpolynomial multiplicationsparse interpolationsumset

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: We present randomized algorithms to compute the sumset (Minkowski sum) of two integer sets, and to multiply two univariate integer polynomials given by sparse representations. Our algorithm for sumset has cost softly linear in the combined size of the inputs and output. This is used as part of our sparse multiplication algorithm, whose cost is softly linear in the combined size of the inputs, output, and the sumset of the supports of the inputs. As a subroutine, we present a new method for computing the coefficients of a sparse polynomial, given a set containing its support. Our multiplication algorithm extends to multivariate Laurent polynomials over finite fields and rational numbers. Our techniques are based on sparse interpolation algorithms and results from analytic number theory.

Recommendations

• On the bit-complexity of sparse polynomial and series multiplication
• What can (and can't) we do with sparse polynomials?
• Computing sparse multiples of polynomials
• On the complexity of multivariate blockwise polynomial multiplication
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

Cited in

(12)

• Multilinear polynomial systems: root isolation and bit complexity
• Polynomial modular product verification and its implications
• Sparse polynomial interpolation based on derivatives
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
• Sparse polynomials in FLINT
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Removing additive structure in 3SUM-based reductions
• Sparse multiplication of multivariate linear differential operators
• On exact division and divisibility testing for sparse polynomials
• Fast interpolation and multiplication of unbalanced polynomials
• Fast n-fold Boolean convolution via additive combinatorics
• Output sensitive algorithms for approximate incidences and their applications

This page was built for publication: Output-sensitive algorithms for sumset and sparse polynomial multiplication

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