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.