矩阵的Hermite标准型是代数学与计算数论等领域的基本工具，在密码学与算法设计等领域具有重要应用。目前，关于Hermite标准型的研究都是在域及主理想整环（Z、Q[x]等）上。本文研究了最简单与基本的非主理想整环Z[x]上矩阵的广义Hermite标准型，给出了计算此标准型的一种多项式时间的高效算法。这一算法在差分代数研究中有重要应用。主要结果介绍如下。　　1.我们给出两种算法计算Z[x]-矩阵的广义Hermite标准型。第一种算法通过提出一种新颖的延拓方法与对Z[x]上线性方程解的次数与数据大小的精确估计方法，使得运算过程中系统的次数不会膨胀，从而有效的控制整体算法的复杂度，得到一个多项式复杂度的算法。第二种算法为模算法，它充分利用Z[x]-矩阵的广义Hermite标准型首项系数的整除性质及Hensel提升来还原所需的广义Hermite标准型。此算法需要分解大整数，但在输入系统次数较低时具有很高的效率。　　2.本文还研究了Z上一组线性不等式系统的整数解问题，首次给出求解这一问题的Omega Test的复杂度分析。Omega Test方法主要用来判断一个给定的多面体中是否存在整数点，若有，给出其中一个整数点。我们基于Omega Test提出算法，将一个给定的多面体分解成一系列“简单”多面体，其中每个“简单”多面体的代数表示系统有类似于“正则链”的投射性质。在符合实际的假设条件下，我们证明此算法关于输入系统的变量个数具有单指数的复杂度。此复杂度结果也即为Omega Test的复杂度。