Title: Solving Linear Systems over Cyclotomic Fields
Speaker: Michael Monagan, CECM.

Abstract:

We present some analysis and improvements to a modular algorithm
that uses Chinese remaindering and rational reconstruction
to solve a linear system $A x = b$ over a cyclotomic field.
If $m(z)$ is the minimal polynomial for the field, 
a cyclotomic polynomial of degree $d$, we exploit the fact that
it is relatively easy (we give a fast algorithm for this) to find
primes which split $m(z)$ into linear factors.  This means we can
solve $Ax = b$ modulo a prime $p$ at each root of $m(z)$ using
machine arithmetic (which makes this fast in practice) and
potentially in parallel.

One if the questions we address is how large the integers in the
solution vector $x$ can be and what is the best way to do the
reconstruction.  If $n = \dim A$ and $d = \deg m(z)$, it turns out
that in general, the integers in $x$ can be $n d$
times longer than those in the input $A,b.$
If we are permitted to output the solution $x$ as a ratio of
determinants, which we can do using Chinese remaindering, we can
reduce the size of the output by a factor of $d$ in general.

We present timings comparing the two algorithms and a linear $p$-adic
lifting algorithm on three sets of benchmarks.  Two of the sets from
are real problems where the size of the integers in $x$ is much
smaller than expected, the other benchmark is randomly generated input.

This is joint work with Liang Chen.