论文标题
一种用于计算非词组矩阵的Hermite正常形式的立方算法
A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix
论文作者
论文摘要
给出了拉斯维加斯随机算法，以计算非整数矩阵$ a $ dimension $ n $的HERMITE正常形式。 The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by $O(n^3 (\log n + \log ||A||)^2(\log n)^2)$ bit operations, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry of $A$ in absolute value.给出了使用伪内性整数乘法的算法的变体，该变体具有运行时间$（n^3 \ log || || a || a ||）^{1+o（1）} $ bit Operations，其中指数$“+o（o（1）” $对于正真实常数$ C_1，C_2，C_3 $。
A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix $A$ of dimension $n$. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by $O(n^3 (\log n + \log ||A||)^2(\log n)^2)$ bit operations, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry of $A$ in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time $(n^3 \log ||A||)^{1+o(1)}$ bit operations, where the exponent $"+o(1)"$ captures additional factors $c_1 (\log n)^{c_2} (\log \log ||A||)^{c_3}$ for positive real constants $c_1,c_2,c_3$.
