Computing Hermite Forms of Polynomial Matrices

被引：0

作者：

Gupta, Somit ^{[1
]}

Storjohann, Arne ^{[1
]}

机构：

[1] Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

ISSAC 2011: PROCEEDINGS OF THE 36TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION | 2011年

关键词：

Hermite form; Polynomial matrices; COMPUTATION;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n x n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A using an expected number of (n(3)d)(1+0(1)) field operations. This is the first algorithm that is both softly linear in the degree d and softly cubic in the dimension n. The algorithm is randomized of the Las Vegas type.

引用

页码：155 / 162

页数：8

共 28 条

[11] ASYMPTOTICALLY FAST TRIANGULARIZATION OF MATRICES OVER RINGS
HAFNER, JL
MCCURLEY, KS
[J]. SIAM JOURNAL ON COMPUTING, 1991, 20 (06) : 1068 - 1083
[12] WORST CASE COMPLEXITY-BOUNDS ON ALGORITHMS FOR COMPUTING THE CANONICAL STRUCTURE OF FINITE ABELIAN-GROUPS AND THE HERMITE AND SMITH NORMAL FORMS OF AN INTEGER MATRIX
ILIOPOULOS, CS
[J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (04) : 658 - 669
[13] Essentially optimal computation of the inverse of generic polynomial matrices
Jeannerod, CP
Villard, G
[J]. JOURNAL OF COMPLEXITY, 2005, 21 (01) : 72 - 86
[14] On the complexity of computing determinants
Kaltofen, E
Villard, G
[J]. COMPUTATIONAL COMPLEXITY, 2005, 13 (3-4) : 91 - 130
[15] Labhalla S. E., 1991, THESIS U CADI AYYAD
[16] Micciancio D., 2001, ISSAC 2001. Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, P231, DOI 10.1145/384101.384133
[17] On lattice reduction for polynomial matrices
Mulders, T
Storjohann, A
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2003, 35 (04) : 377 - 401
[18] Storjohann A., 2002, ISSAC 2002. Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, P246, DOI 10.1145/780506.780538
[19] High-order lifting and integrality certification
Storjohann, A
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2003, 36 (3-4) : 613 - 648
[20] Storjohann A., 1996, ISSAC 96. Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, P259, DOI 10.1145/236869.237083

← 1 2 3 →