Nearly Optimal Algorithms for Canonical Matrix Forms
Nearly Optimal Algorithms for Canonical Matrix Forms
复制标题
规范矩阵形式的近乎最优算法
DOI：
10.1137/s0097539793252687
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
M. Giesbrecht
中科院分区：
文献类型：
--
作者：
M. Giesbrecht
本文给出了一个Las-Vegas型概率算法，用于求任意域$\KK$上的$n\times n$矩阵$T$的Frobenius标准形。该算法需要在$\KK$中进行$\softO（\MM（n））=\MM（n）\cdot（\log n）^{O（1）}$操作，其中$\KK$中的$O（\MM（n））$操作足以在$\KK$上乘以两个$n\times n$矩阵。该算法在$\KK$上的运算量为O（n^4）$，与$\Omega（\MM（n））$运算量的下界基本一致，并且在PRAM上实现了Frobenius形式的快速并行算法.作为一个应用，我们给出了一个计算多项式g\in\KK[x]$ at $T$的算法，该算法在$\deg g\leq n ^2 $时只需要$\softO（\MM（n））$操作。其他应用包括顺序和并行算法计算的最小和特征多项式的矩阵，合理约旦形式的矩阵（用于测试是否两个矩阵是相似的），并为矩阵供电，这是大大快于那些以前已知的。
A Las-Vegas-type probabilistic algorithm is presented for finding the Frobenius canonical form of an $n\times n$ matrix $T$ over any field $\KK$. The algorithm requires $\softO(\MM(n))=\MM(n)\cdot(\log n)^{O(1)}$ operations in $\KK$, where $O(\MM(n))$ operations in $\KK$ are sufficient to multiply two $n\times n$ matrices over $\KK$. This nearly matches the lower bound of $\Omega(\MM(n))$ operations in $\KK$ for this problem, and improves on the $O(n^4)$ operations in $\KK$ required by the previously best known algorithms.A fast parallel implementation of the algorithm is also demonstrated for the Frobenius form, which is processor-efficient on a PRAM. As an application we give an algorithm to evaluate a polynomial $g\in\KK[x]$ at $T$ which requires only $\softO(\MM(n))$ operations in $\KK$ when $\deg g\leq n^2$. Other applications include sequential and parallel algorithms for computing the minimal and characteristic polynomials of a matrix, the rational Jordan form of a matrix (for testing whether two matrices are similar), and for matrix powering which are substantially faster than those previously known.