Parallel Sparse Polynomial Multiplication.

Roman Pearce, CECM.

Wednesday February 11th, 3:30pm, in K9509.


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.