Solving linear systems over cyclotomic field.
Michael Monagan, CECM, Simon Fraser.
Monday May 28th, 2007, 3:30pm, IRMACS 10908.
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 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.