Mutliplication of Dense Polynomials in Q(a_1,...,a_t)[x]
Cory Ahn, Department of Mathematics, SFU.Wednesday July 7th, in K9509 at 3:30pm.
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.