Let $AinQ^{ntimes n}[z]$ be a matrix of polynomials and $binQ^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 $xinQ^n[z]$ such that the equation $Ax equiv b bmod{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.
展开▼
机译：令$ AinQ ^ {ntimesn} [z] $为多项式矩阵，而$ binQ ^ n [z] $为多项式向量。令$ m（z）= Phi_k [z] $是$ k ^ {th} $个环多项式。我们想要找到解矢量$ xinQ ^ n [z] $，使得等式$ Ax equiv b bmod {m（z）} $成立。可以使用高斯消去法获得$ x $，但是它效率不高，因为在消除过程中矩阵的多项式系数中会出现较大的有理数。在本文中，我们提出了两种模块化算法，即中文余数和线性$ p $ -adic提升。我们已经在Maple中实现了这两种算法，并确定了这两种算法的时间复杂度。我们提供关于两组数据的时序比较表，首先是具有随机生成系数的系统，其次是Vahid Dabbaghian由计算组理论产生的实系统。结果表明，我们的两种算法都比高斯消除快得多。
展开▼
