Popov Form Computation for Matrices of Ore Polynomials
Popov Form Computation for Matrices of Ore Polynomials
复制标题
矿石多项式矩阵的波波夫形式计算
DOI：
10.1145/3087604.3087650
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Arne Storjohann
中科院分区：
文献类型：
--
作者：
Mohamed Khochtali;Johan Rosenkilde né Nielsen;Arne Storjohann
设F[f; σ，δ]是域上的Ore多项式环.本文给出了一个计算非奇异矩阵A ∈ F[f; σ，δ]n × n的Popov型P的新的确定性算法.我们的主要重点是确保在F = K（z），甚至K = Q的情况下，系数的大小从F受控增长。我们的算法是基于从A构建一个线性系统F和执行结构化的分数免费高斯消除。该算法是输出敏感的，其代价取决于输入矩阵的正交性缺陷：A中的行度之和减去P中的行度之和。Q（z）上的差分和移位多项式情况的所得位复杂度改进了先前的最佳值。
Let F[∂ ; σ, δ] be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form P of a non-singular matrix A ∈ F[∂ ; σ, δ]n x n. Our main focus is to ensure controlled growth in the size of coefficients from F in the case F = K(z), and even K = Q. Our algorithms are based on constructing from A a linear system over F and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in A minus the sum of the row degrees in P. The resulting bit-complexity for the differential and shift polynomial case over Q(z) improves upon the previous best.
登录
查看更多内容
稀疏矩阵的无分数高斯消元法
DOI：
10.1006/jsco.1995.1022
发表时间：
1995
期刊：
J. Symb. Comput.
影响因子：
--
作者：
Hong R. Lee;B. D. Saunders
通讯作者：
B. D. Saunders
多项式行列式系数的哈达玛型界（A. J. Goldstein 和 R. L. Graham）
影响因子：
10.2
作者：
O. Lossers
通讯作者：
O. Lossers
计算 Ore 多项式矩阵的 Hermite 形式
DOI：
10.1016/j.jalgebra.2012.11.033
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
M. Giesbrecht;Myung Sub Kim
通讯作者：
Myung Sub Kim
关于整数矩阵乘法的复杂度
DOI：
10.1016/j.jsc.2017.11.001
发表时间：
2017
期刊：
J. Symb. Comput.
影响因子：
--
作者：
David Harvey;J. Hoeven
通讯作者：
J. Hoeven
Ore 多项式矩阵的无分数行约简
DOI：
10.1016/j.jsc.2005.10.002
发表时间：
2006
期刊：
J. Symb. Comput.
影响因子：
--
作者：
B. Beckermann;Howard Cheng;G. Labahn
通讯作者：
G. Labahn