POLY: A new polynomial data structure for Maple 17.
Michael Monagan, CECM, Simon Fraser University
In this talk we present our parallel algorithm for polynomial multiplication and a benchmark that shows that we get good parallel speedup for multiplication. However conversion and other overhead limits parallel speedup and we find little parallel speedup in polynomial factorization. We then demonstrate how a new polynomial data structure for sparse distributed polynomials in the Maple kernel significantly accelerates a large subset of Maple library routines and leads to real parallel speedup in polynomial factorization. The POLY data structure and its associated kernel operations including degree, coeff, subs, has, diff, eval, taylor, indets, etc., are programmed for high scalability, allowing polynomials to have hundreds of millions of terms, with very low overhead, increasing parallel speedup in existing routines and improving the performance of high level Maple library routines. This is joint work with Roman Pearce.