Parallel Integer Polynomial Multiplication

2016/12/17 by Chen, Changbo, Covanov, Svyatoslav, Mansouri, Farnam +3
#FOS: Computer and information sciences #Mathematical Software (cs.MS) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1612.05778

Abstract

We propose a new algorithm for multiplying dense polynomials with integer coefficients in a parallel fashion, targeting multi-core processor architectures. Complexity estimates and experimental comparisons demonstrate the advantages of this new approach.

Related

• Fast multiplication by two's complement addition of numbers represented as a set of polynomial radix 2 indexes, stored as an integer list for massively parallel computation
• Highly Scalable Multiplication for Distributed Sparse Multivariate Polynomials on Many-core Systems
• Faster polynomial multiplication via multipoint Kronecker substitution
• Multiplication of sparse Laurent polynomials and Poisson series on modern hardware architectures
• A Fully Pipelined FIFO Based Polynomial Multiplication Hardware Architecture Based On Number Theoretic Transform