In-place arithmetic for univariate polynomials over an algebraic number field.

Michael Monagan, CECM.

Wednesday November 25th, 2009, 3:30pm, in K9509.

Abstract: 

We have developed a C library of in-place subroutines for doing
univariate polynomial multiplication, division and GCD in Lp[x]
where Lp is an algebraic number field L with multiple field
extensions reduced modulo a machine prime p.  We use a recursive
dense representation for storing elements of Lp and L. 

The main idea of our algorithms is that we eliminate the storage 
management overhead which is significant compared to the cost of
the integer arithmetic.  We do this by pre-allocating the exact 
amount of storage needed for both the output and working storage.
The amount of working storage needed is linear in D the degree
of the number field L.

We will present benchmarks demonstrating the efficiency of our library.
This work improves the performance of polynomial GCD computation
over algebraic number fields and algebraic function fields.
In the talk I will also give a demo of a GCD computation done in L[x]
using the Magma computer algebra system to motivate this work.

This is joint with with Mahdi Javadi.