Nearly Optimal Sparse Polynomial Multiplication

DOI10.1109/TIT.2020.2989385MaRDI QIDQ5138887zbMATH OpenOpenAlexWikidataFDO

Authors Vasileios Nakos

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Abstract: In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials f and g in time that is proportional to the size of the input plus the size of the output. The polynomials are given via lists of their coefficients F and G, respectively. Cole and Hariharan (STOC 02) have given a nearly optimal algorithm when the coefficients are positive, and Arnold and Roche (ISSAC 15) devised an algorithm running in time proportional to the "structural sparsity" of the product, i.e. the set supp(F)+supp(G). The latter algorithm is particularly efficient when there not "too many cancellations" of coefficients in the product. In this work we give a clean, nearly optimal algorithm for the sparse polynomial multiplication problem.

Recommendations

• Essentially optimal sparse polynomial multiplication
• Computing sparse multiples of polynomials
• Computing sparse multiples of polynomials
• Sparse multiplication for skew polynomials
• Space- and time-efficient polynomial multiplication
• Sparse polynomial approximation in finite fields
• Comparing the speed of programs for sparse polynomial multiplication
• On optimizing multiplications of sparse matrices
• Fast multiplication and sparse structures
• On the bit-complexity of sparse polynomial and series multiplication

Cited in

(12)

• Dense polynomial multiplication with reduced array manipulation overhead
• Polynomial modular product verification and its implications
• Sparse multiplication for skew polynomials
• Fast multiplication and sparse structures
• Pseudo 8–Sparse Multiplication for Efficient Ate–Based Pairing on Barreto–Naehrig Curve
• Bit-twiddling hacks for gamma matrices
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Removing additive structure in 3SUM-based reductions
• On exact division and divisibility testing for sparse polynomials
• Solving a family of multivariate optimization and decision problems on classes of bounded expansion
• Fast interpolation and multiplication of unbalanced polynomials
• Fast n-fold Boolean convolution via additive combinatorics

This page was built for publication: Nearly Optimal Sparse Polynomial Multiplication

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