Three Problems in Computer Algebra

Michael Monagan, CECM, Simon Fraser University

Friday October 21th, 2005 at 10:30am in K9509.

Abstract: 

I will present three problems and sketch possible solutions.

The first problem involves the Kaltofen-Trager 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 non-zero 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 Schoenhage-Strassen 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 Schoenhage-Strassen algorithm uses instead a very large ``prime''
of the form p = 2^(2^k)+1 instead.