Parallel Sparse Polynomial Multiplication.
Roman Pearce, CECM.
Abstract: Given two sparse polynomials f and g we want to compute their product. One of the fastest methods is Johnson's algorithm (1974), which uses a binary heap to simultaneously merge each f_i*g for i=1..#f. In this talk we will describe how Johnson's algorithm may be parallelized for multicore processors with very high performance. Our program is up to 6x faster with 4 cores than with 1.