Mutliplication of Dense Polynomials in Q(a_1,...,a_t)[x]

Cory Ahn, Department of Mathematics, SFU.

Talk slides

Abstract. 

In this talk, we will discuss ways in which we can speed up multiplication
of dense polynomials f(x) and g(x) in Q(a_1,...,a_t)[x].

In particular, the following improvements on the "naive" multiplication
method are made:

1. Simplify the recden data structure used to represent the
   polynomials by reducing multiple extensions to one extension.
2. Use the fast Fourier Transform to perform the multiplication.
3. Map the rational coefficient to finite field(s) Z_p for suitable
   prime(s) p, multiply in the finite field(s), then recover the rational
   coefficients of the product via rational number reconstruction.