In-place arithmetic for univariate polynomials over an algebraic number field.
Michael Monagan, CECM.
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.