论文标题
在矩阵乘法时期特征多项式的确定性计算
Deterministic computation of the characteristic polynomial in the time of matrix multiplication
论文作者
论文摘要
本文介绍了一种算法，该算法计算同一渐近复杂性内的磁场上的矩阵的特征多项式，直至恒定因子，如两个平方矩阵的乘法。以前，这仅是通过诉诸通用假设或随机技术来实现的，而凯勒·盖里格（Keller-Gehrig）在1985年获得了与一般确定性算法结合的最著名的复杂性，并涉及对数因素。我们的算法更普遍地计算出降低形式的单变量多项式矩阵的决定因素，并依靠新的子例程将偏移的矩阵转化为移动的弱Popov矩阵，并将弱的Popov矩阵转移到移位的Popov矩阵中。
This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices.
