Solving Linear Systems over Cyclotomic Fields

Liang Chen, Masters thesis defense, Computing Science, SFU

Tuesday August 7th, 2007, 4:30 p.m. TASC 1 room 9204.

Abstract:

Let $A \in \Q^{n\times n}[z]$ be a matrix of polynomials and $b \in \QQ^n[z]$ be a vector of polynomials. Let $m(z) = \Phi_k[z]$ be the
$k^{th}$ cyclotomic polynomial. We want to find the solution vector $x \in \Q^n[z]$ such that the equation $Ax \equiv b$ mod $m(z)$ holds. One
may obtain $x$ using Gaussian elimination, however, it is inefficient
because of the large rational numbers that appear in the coefficients of
the polynomials in the matrix during the elimination. In this thesis, we
present two modular algorithms namely, Chinese remaindering and linear
$p$-adic lifting. We have implemented both algorithms in Maple and have
determined the time complexity of both algorithms. We present timing
comparison tables on two sets of data, firstly, systems with random
generated coefficients and secondly real systems given to us by Vahid
Dabbaghian which arise from computational group theory. The results show
that both of our algorithms are much faster than Gaussian elimination.