
Three Problems in Computer AlgebraMichael Monagan, CECM, Simon Fraser University
Abstract: I will present three problems and sketch possible solutions. The first problem involves the KaltofenTrager black box model computation. Suppose f is a rational function in x1, x2, ..., xn over Q. I will show how to reconstruct the sparse representation of f from samples points without knowing the degree of f or coefficient size in time proportional to the number of nonzero terms in f. I will give two applications. This is joint with with Jennifer de Kleine and Allan Wittkopf. The second problem is solving large linear systems over Q(e) where e is a primitive n'th root of unity. I will describe a modular algorithm which uses Allan's LinearAlgebra:Modular package and rational reconstruction and demonstrate the algorithm on two problems given to me by Vahid. The third, is a presentation of the SchoenhageStrassen fast integer multiplication algorithm. The ``obvious'' way to apply the FFT to multiply two long integers is to use a Fourier prime p of the form p = 2^k q + 1 which fits on the machine (a 64 bit prime) so that the Fourier transform can be computed using machine integer arithmetic only. The SchoenhageStrassen algorithm uses instead a very large ``prime'' of the form p = 2^(2^k)+1 instead. 