Solving linear systems over cyclotomic field.

Michael Monagan, CECM, Simon Fraser.

Talk Slides (.pdf)

Monday May 28th, 2007, 3:30pm, IRMACS 10908.


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 padic
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.