Sparse polynomial powers using heaps.
Roman Pearce, Center for Experimental and Constructive Mathematics, Simon Fraser University
We discuss powering of sparse polynomials, which is surprisingly complicated. In most computer algebra systems, the best algorithm for expanding f^k is to repeatedly multiply by f. Repeated squaring, as in f^4 = (f^2)^2, is much worse for sparse polynomials. In this talk we describe a new method which expands f^k for about the cost of multiplying f^(k-1) and f. It has much better complexity and lower space for powering dense polynomials which makes it more attractive for use as a general purpose routine. We show how to parallelize the method, and compare its performance on a series of benchmark problems to other methods and the Magma, Maple and Singular computer algebra systems. This is joint work with Michael Monagan.